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.

Google Online Preview   Download