Stochastic Simulation
Stochastic Simulation Notes
by
Kevin D. Donohue
Department of Electrical Engineering
University of Kentucky
Lexington, KY 40506
These notes were developed to provide basic understanding, rules, and practical tricks for obtaining reliable answers from computer simulations, particularly for evaluating the performance of communication and signal processing systems. Performance measures examined include integral performance measures such as mean square error, bias, and variance/efficiency, and probability measures such as probability of detection and false alarm.
Stochastic Simulation:
Purpose:
Stochastic simulations can establish relationships between system inputs, outputs, and parameters in a statistically reliable manner. (Simulations are especially helpful when a closed-form relationship cannot be derived.)
For signal processing and communication systems, simulations can be useful for:
➢ comparing performances of systems under statistically similar conditions
➢ optimizing processing and system parameters
➢ developing an algorithm through identifying its limitations in a given application
.
Components of Simulation Design:
➢ Problem Definition:
Be as quantitative as possible. Identify quantities to be determined. Determine system conditions and inputs affecting these quantities.
➢ System Model:
Develop a system model suitable for computer implementation that includes the interactions of all critical phenomena whose inputs, outputs, and model parameters are consistent with ones in the defined problem.
➢ Experimental Design:
Statistically design/analyze the simulation (i.e. ensemble of runs) to determine the reliability of the estimated quantities from a finite number of runs.
➢ Implementation:
Design programs to implement simulation model. Consider required computing resources (processing time and memory) in developing code so program will finish in a reasonable amount of time.
Example of Monte Carlo Simulation:
The classic example of a Monte Carlo simulation is evaluating a multiple integral. Obviously, the best place to use it is where the dimensions are so high that a direct iterative technique will take too many years to compute and a closed form solution cannot be found. However, for the sake of illustration and comparison, the following example can be solved quite easily by all 3 methods (closed-form solution, iteration, and Monte Carlo).
Problem Definition:
Find the probability that 2 identical and independent Rayleigh distributed signal values, [pic] are bounded such that [pic]
System Model:
Express probability in terms of Rayleigh distribution and limits indicated in problem statement.
[pic]
Solution 1 (Exact Solution): Evaluate integral in terms of b and r.
[pic]
Solution 2 (Numerical Solution): Illustration of surface representing the integrand for b=1.
[pic]
Develop iterative program to break the double integral down into smaller volumes, using [pic] increments along the [pic] axes, respectively:
The evaluation of the integrand on a finer the resolution grid results in a more accurate the solution (provided there are no singularities over the region of integration); however, the number of iterations increases as a function of grid resolution according to:
Number of iterations [pic]
Solution 3 (Stochastic or Monte Carlo Simulation):
The integration problem can be reformulated as follows. The volume under the integrand's surface equals its mean value times the area of the integration region. (This is true! Think about it for a while, if it is not obvious. You may want to think in terms of some simple one-dimensional examples first, or recall the mean-value theorem from Calculus).
So now the problem can be reformulated in terms of estimating the mean based on a finite number of samples taken from an infinite (continuous surface) population.
In some sense, this is done with numerical approach where the sampling strategy is a uniform grid over the region of integration. For the Monte Carlo approach however, points are chosen at random in the integration region (random sampling). Thus, a critical simulation issue relates to the design of the random experiment (i.e. how reliable is the answer for the given number of samples taken?). This will be addressed later, for now let's compare the 3 solutions for accuracy and efficiency.
Solve Problem for r = 1 and b=1.
Exact solution: Evaluate closed from expression to obtain 0.09020401043105
Numerical solution: Matlab Code:
% The following code numerically evaluates the double integral of:
% x1*x2*exp(-((x1)^2+(x2)^2)/2) over the range 0 < x1^2 + x2^2 < r^2
% It used different increments on the evaluation grid to compare accuracy
% Loop through exponentially decreasing increments for evaluation grid
for k=1:3
d1 = .1^k; % Increment along x1
d2 = .1^k; % Increment along x2
r = 1; % Bound on integration region
true_value = (2*b-2*b*exp(-r^2/2)-r^2*exp(-r^2/(2*b)))/(2*b); % Closed-form solution
probability_value(k) = 0; % Clear value to accumulate
% summation of volumes
% Step through x2 axis until limit reached
n2=0; % Initialize increment on x2 axis
while (n2 ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- free online city building simulation games
- stock market simulation for students
- photosynthesis simulation lab
- history simulation games
- elodea simulation lab
- protein synthesis simulation lab answers
- best stock market simulation game
- protein synthesis simulation lab
- photosynthesis simulation worksheet
- protein synthesis simulation answer key
- business tycoon simulation games
- best city simulation games