Lecture Notes for Simulation

28 March 2005 - Simulation Accuracy

Outline

• Simulation accuracy and run length.

  • The KD Run-Length Algorithm

• Sample corruption and correlation.

  • Autocorrelation

• Repeating runs and batch means.

• Variance Reduction

  • Control variates.

  • Antithetic variates.

  • Positive correlation.

Simulation Accuracy

• Simulation accuracy can be measured in at least two ways:

  1. Comparison with system measurements.

  2. Tight interval bounds and large confidence levels.

• If simulation accuracy is inadequate, there are two steps to fix it:

  1. Make sure the simulation samples aren't being corrupted.

  2. Increase the number of samples.

Simulation Run Length

• In this case, simulation duration is measured in samples.

• The proper duration is "as long as possible."

  • But this may be wasteful or impractical.

• The simulation confidence bounds are given by
  [x - (sz_a/2)/n^0.5, x + (sz_a/2)/n^0.5]

• If bound (sz_a/2)/n^0.5 should be d, then set
  d = (sz_a/2)/n^0.5 and find n = (sz_a/2/d)².

  • Unfortunately n is a random variable because s is.

• The Karian and Dudewicz algorithm provides an alternative.

The KD Run-Length Algorithm

• Assume m should be bounded by b with confidence c.

• Set n₀ > 1 and w = t(n₀ - 1, (1 - c)/2)^-1/b.

• Collect samples x₁, ..., x_n0.

• Calculate x_n0 and s².

• Set n = max(n₀ + 1, ceil(w²s²)).

• Collect samples x_{n0 + 1}, ..., x_n.

• Calculate x.

• m is bounded by [x - b, x + b] with c% confidence.

Run-Length Example

• How many samples bound the server-utilization mean within d = 0.1 at c = 99% confidence?

• Let n₀ = 15 and
  w = t(15 - 1, (1 - 0.99)/2^-1/0.1 = t(14, 0.005))^-1/0.1 = 3/0.1 = 30.

• Collect 15 samples; x = 0.85 and s² = 0.003.

• n = max(15 + 1, ceil(30²0.003)) = max(16, ceil(2.7)) = 16.

• Collect one more sample and compute x = 0.851 and s² = 0.003.

• The mean is bounded by [0.851 - 0.1, 0.851 + 0.1] with 99% confidence.

• n₀ = 15 is too high.

Sample Corruption

• Many problems can corrupt samples.

  • Poor simulation implementation, including floating-point abuse.

  • Transient-phase samples.

  • Samples that are not independent.

• Independence is a statistical property of distributions.

  • Two random variables X and Y are independent if the value of X has no relation to the value of Y.

    • The time of day and temperature are not independent.

    • The temperature and day of the week are independent.

Correlation

• Correlation is a measure of independence between two random variables.

• The covariance of a pair of random variables is
  Cov(X, Y) = E[(X - m_x)(Y - m_y)]

• For independent random variables, the expectation of the product is the product of the expectation
  E[(X - m_x)(Y - m_y)] = E[X - m_x]E[Y - m_y]

  and the expectation of the difference between a random variable and its mean is 0.

• The correlation coefficient between two random variables is
  Cor(X, Y) = Cov(X, Y)/(s²(X)s²(Y))^0.5

  • -1 <= Cor(X, Y) <= 1

Example Correlations

Cor(X, Y) = 0.918871	Cor(X, Y) = -0.959546	Cor(X, Y) = 0.0771176

• Correlation only measures linear dependencies.

Autocorrelation

• A random variable may be correlated with itself, which is called autocorrelation.

  • Time series temperature readings are autocorrelated.

  • A random number sequence should not be autocorrelated.

• The autocorrelation for random variable X is

  Cor(p)	=	E[(xi - x)(xi + p - x)]
  	=	sum(i = 1 to n - p, (xi - x)(xi + p - x))/(n - p)

  • p is the lag.

Repeating Runs

• One obvious way to increase the number of samples is to run the simulation several times.

• Run a simulation k times, collecting n samples per run.

  x1,1 ... x1,n : x1 x2,1 ... x2,n : x2 . . . . . . . . . xk,1 ... xk,n : xk x

  xi = sum(j = 1 to n, xi,j)/n x = sum(j = 1 to k, xk)/k s2 = sum(j = 1 to k, (xk - x)2)/(k - 1) The sample variance estimate is s2/k.

• Each run has a separate transient phase.

Repetition with Correlation

• The previous analysis assumed no correlation between variables.

• If there is correlation, the sample variance estimate has to be adjusted.
  s²/n[1 + 2sum(p = 1 to n - 1, (1 - p/n)Cor(p)) ]

  • The correlation coefficients are computed off-line from the samples.

• If the correlations are negative, the variance estimate decreases.

Batch Means

• An alternative to several simulation runs is one long run chopped into pieces.

  • Each piece is called a batch.

  • Equivalent to repetition with initial conditions carried forward.

• There is obvious correlation, both within and between batches.

  • Batch sizes should be large enough to minimize correlation.

  • The Central Limit Theorem takes care of autocorrelation within a batch.

• The batch size can be computed by

  • Estimate, using the transient phase size, for example.

  • Reducing the autocorrelation to close to zero.

Computing Batch Means

• Run the simulation for the desired length.

• Toss the transient samples and divide the rest into batches.

• Compute the mean of each batch.

• Compute the mean of the batch means.

• Compute the batch-mean variance.

Repetition-Batch Comparison

• Repetitions:

  • Minimal variance estimates from minimal sample sizes.

  • Smaller variances than does the batch method.

  • Expensive, both in execution and analysis.

• The batch method:

  • On-line analysis

  • Simpler transient analysis

  • Batch aggregation loses accuracy

• Favor the batch method for low-accuracy simulations; otherwise favor repetitions.

Variance Reduction

• Increasing the samples reduces variance.

• There are other variance-reduction techniques:

  • Control variates.

  • Antithetic variates.

  • Positive correlates (for comparative analysis).

Control Variates

• A control variate is a model variable correlated with output variables.

• Differences in the control variates can be reflected in the output variables to improve accuracy.

• A simulation finds the mean server utilization for an M/M/1 queue with m_a = 1.0 and m_s = 0.8.

  • m_a and m_s are control variates for the mean utilization.

  • The simulation produces a result m_u.

  • m_a is assumed to be 1.0, but suppose it's measured to be 1.2.

  • The adjustments to correct m_a can be applied to m_u.

Antithetic Variates

• A standard uniform variate X should produce a sequence
  x₁, ..., x_n

  with 0 autocorrelation.

  • It probably doesn't.

• What about the sequence 1 - x₁, ..., 1 - x_n produced by 1 - X?

  • It's autocorrelation is opposite that of X.

• Averages produced from both sequences should be more accurate than when one sequence is used.

  • The opposite autocorrelations cancel in the average.

• 1 - X is an example of an antithetic variate.

Positive Correlation

• Comparative simulations can be run two ways:

  • Run simulations in isolation, compute results separately, and compare.

  • Run paired simulations, maintaining synchronization between simulations.

• The similarity and synchronization in paired simulation causes positive correlation between simulation results.

  • And positive correlation reduces variance.

Points to Remember

• The best way to improve simulation accuracy is increase the sample count.

  • But how hight is up?

• It also helps to have clean (non-correlated) data.

  • Although sometimes correlation can be exploited.

• Repeating runs and batch means are two ways of creating extra samples.

• Variance-reduction techniques can provide statistical aids for dodgy samples.

This page last modified on 6 April 2005.