Lecture Notes for Simulation

23 March 2005 - Output Analysis

Outline

A simple simulation problem.
Sample statistics.
- The Central Limit Theorem.
- Weakening CLT assumptions.
Dealing with means.
- Point and interval estimates
Other results.
- Variance, comparitive means, and success probabilities.

Simulation

Overall, a simulation has four phases:
1. Understand the problem to extract a system.
2. Abstract the system as a model.
3. Experiment with the model.
  - Design the experiments.
  - Run the experiments.
4. Analyze the experiment results.
Each phase has sub-phases, including be validation and verification.

The Problem

Given a simple, single server queue find the server utilization (server busy/total time).
That's not too hard:
- Write a simulation
- Run it.
```
$ ./mm1-utilization -a 1.0 -s 0.8
0.854407

$
```
- And we're done.

Are We?

Run it again.

$ ./mm1-utilization -a 1.0 -s 0.8
0.759872

$

Oops.

Run it a few more times.


$ j=1 ; while [ $j -lt 6 ] ; do 
  ./mm1-utilization -a 1.0 -s 0.8 ; (( j++ )) 
  done

0.824176
0.834251
0.723797
0.793702
0.777018

$

The Problem Revisited

Well, yes - server utilization is a statistic.

Compute some statistics over the server utilizations.

$ j=1 ; while [ $j -lt 11 ] ; do 
  ./mm1-utilization -a 1.0 -s 0.8 ; (( j++ )) 
  done | stats

min = 0.736751
max = 0.842563
n = 10
average = 0.790132
std dev = 0.0320734

$

Ah, now we're done.

Are We?

Calculate some more statistics.

$ j=1 ; while [ $j -lt 11 ] ; do 
  ./mm1-utilization -a 1.0 -s 0.8 ; (( j++ )) 
  done | stats

min = 0.748613
max = 0.894508
n = 10
average = 0.81606
std dev = 0.0485143

$

You can't outrun the problem down this path.
- You can't outrun this problem at all.
- You have to take a different approach.

Back to the Beginning

Every run of the simulation produces a server utilization value.
- The simulation is a random variable U.
- The underlying distribution for U exists but is unknown (usually).
  - The distribution has a mean and variance, both unknown.
When life gives you an undefined random variable, make statistics.
- In particular compute the mean and variance of the samples from U.
I though you said that doesn't work.
- We're going to attach a different, more useful interpretation to the results.

Sample Statistics

Run the server a bunch of times and find the average of the utilizations produced.

$ j=1 ; while [ $j -lt 41 ] ; do 
  ./mm1-utilization 1.0 0.8 ; (( j++ )) ; done |
  ./stats | grep ave | awk '{print $3}'

0.79177

$

Do that a bunch of times. What do you get?

The Central Limit Theorem

For any population (the sampled population) with known mean m and variance v²
- the population of n-IID-sample means has an approximately normal distribution (the sampling distribution) with mean m_n = m and variance v_n² = v²/n
and
- the random variable
  z = (x - m)/(v/n^0.5)
  has the standard normal distribution.
For good results, n should be at least 30.
- For quasi-normal sampled populations, n can be less than 30.
- For normal sampled populations, n doesn't matter and the sampling distribution is normal too.

CLT Example

Suppose the utilization population has 0.81 mean and 0.01 variance.
- Determined by measuring and estimating an existing queue with the proper parameters.
The simulation generates 40 utilizations with a 0.79 mean. Is this good?
Compute z = (x - m)/(v/n)^0.5 = (0.79 - 0.81)/(0.01/40)^0.5 = -1.27
From a standard-normal table, P(-1.27 <= z) = 0.102.
Around 10% of all samples should be less than 0.79. Is this good?

Weakening the CLT Assumption

The CLT assumption of known sampled population mean and variance is too strong.
How can it be weakened, and what happens when it is?
The CLT provides one equation and two unknowns, an unpleasant circumstance.
- It also provides estimates for the two unknowns.
- The m_n = mestimate is uncontrollable.
- The v_n² = v²/n estimate can be controlled via n.
Using v_n²/n to estimate v² leaves one equation with one unkown.

Variance Estimation Costs

What's the cost of estimating the sampled-population variance with the sampling-population variance?
If each member of the sampling population is formed from n >= 30 samples from the sampled population,
- the CLT still holds, that is,
- the inaccuracies introduced by the estimation are small enough to ignore.
- And gets smaller as n gets larger.
If n is less than 30, then the CLT no longer holds; that is, z is no longer normal.
- However, z is quasi-normal as determined by the Student's t-distribution.

The Student's t-Distribution

Let n samples be drawn from a normal distribution with mean m and (unknown) variance v².
If the n samples have mean x and variance s², then the random variable
t = (x - m)/(s/n^0.5)
is t-distributed with n - 1 degrees of freedom.

For example,

The utilization distribution has m = 0.81 and v² unknown.
With n = 10, x = 0.79 and v_n = 0.03.
t is (0.79 - 0.81)/(0.03/10^0.5) = -2.11.
From a t-distribution table, with 9 degrees of freedom P(t <= -2.11) = 0.034.

Recapitulation

Move from an arbitrary distribution to a quasi-normal distribution to a known distribution, all with known means and variances.
Replaced the unknown results variance with the results-mean variance.
Identified the mean-error distribution as a standard normal or Student's t depending on n.
All further work will be done with the mean-error distribution.

The Other Unknown

The results-distribution mean is still unknown.

point estimates

By the CLT, the mean of the results-mean distribution is equal to the results-distribution mean, but that's unknown too.
A sample x from the results-mean distribution may equal the results-distribution mean, but probably not for non-infinite values of n.

However, x may be near the results-distribution mean.
This raises the questions: how near and how likely?

Interval Estimates

The interval parameter k answers the question "How near?"
- m is near x if x - k < m < x + k.
The confidence interval a answers the question "How likely?"

a is the probability that m is near x: P(x - k < m < x + k) = a.
- The value 1 - a is called the significance.
- For example, a 95% confidence interval has 5% significance.
The trade-off is between k and a.
- k should be small but a should be large.
- Small variances make this more likely.

Bounding the Mean

An x distribution is approximately normal, which is not useful.

The CLT provides z = (X - m)/(s/n^0.5), a standard normal distribution.
A little algebra transforms
P(x - k < m < x + k) = a into
P(m - k < x < m + k) = a

m + k is a valid value for x; substitute it into the equation above:
z_{(1 - a)/2} = ((m + k) - m)/(s/n^0.5) = kn^0.5/s
For a given confidence interval a, find the associated k.
- Or, given k, find the associated confidence interval.

Bounding Mean Example

A 40-sample results-mean sample x has a value of 0.79 and a 0.03 standard deviation. How wide is the interval around x to make sure the true mean is close to x with 95% confidence?
- From a table of standard normals, z_{(1 - 0.95)/2} = z_0.025 = -2.
- Plugging the values into z_{(1 - a)/2} = kn^0.5/s gives
  -2 = k40^0.5/0.03 or k = -2(0.03)/40^0.5 = -0.009
- With a 1 in 20 chance of being wrong, the results mean is within the interval [0.79 - 0.009, 0.79 + 0.009].

Confidence Interval Example

A 10-sample results-mean sample x has a value of 0.81 and a 0.05 standard deviation. How much confidence is there in wanting to believe that the results mean is no more than 0.05 away from X on either side?
- k is 0.05.
- Plugging the given values into z_{(1 - a)/2} = kn^0.5/s gives
  z_{(1 - a)/2} = 0.05(10^0.5)/0.05 = 3.16
- With n = 10 z_{(1 - a)/2} has a t-distribution.
- A t-distribution table shows that, with 9 degrees of freedom, z_0.006 = 3.16.
- (1 - a)/2 = 0.006 or a = 1 - 0.006*2 = 0.988 for 98.8% confidence.

Recapitulation

The results-distribution mean is unknowable in general.
The best that can be done is bound the range within which the mean is likely to be found.
- The interval estimate provides the bound.
- The confidence level provides the definition of "likely".
There is a trade-off between the interval estimate and the confidence value.
- Smaller intervals are better, but tend to decrease the confidence levels.
- Larger confidence levels are better, but tend to increase the interval.
Typically the confidence level is fixed beforehand and the interval size is calculated.

Other Output Results

Within k of the mean m to confidence c% is not the only form of simulation output.
- Variance estimation.
- Estimating the difference of means.

Estimating Variance

Given a set of simulation results x₁, ... x_n find
- x = sum(i = 1 to n, x_i)/n
- an estimate s² of the variance of the sample x₁, ... x_n.
- s² can be a replacement for the bounds on x.
Generally speaking, dealing with x and a bounded s² is harder than dealing with a bounded x.
- x is still a random variable.

Variance Estimates

Given samples { x₁, ..., x_n }, the random variable
S = (n - 1)s²/v²
has a chi-square distribution with n - 1 degrees of freedom, where
- s² is the samples' variance.
- v² is the sampled distribution's variance.
Given 0 < a < 1, the (1 - a)100% confidence interval around v² is
P[ chi²((1-a)/2, n-1) <= (n-1)s²/v² <= chi²(1-a/2, n-1) = 1-a
With algebra, this becomes the bounds
[(n-1)s²/chi²(1-a/2, n-1), (n-1)s²/chi²((1 - a)/2, n-1)]

Variance Estimate Example

Given
n = 10,
x = 0.81606, and,
s² = 0.0485143² = 0.002354
estimate the sampled distribution's variance with 95% confidence (a = 0.05).
Turning the crank:
chi²(0.025, 10 - 1) = 2.7,
chi²(0.975, 10 - 1) = 19.0,
(n - 1)s² = (10 - 1)0.002354 = 0.021186, and
[ 0.021186/19.0, 0.021186/2.7 ] = [ 0.001115, 0.007847 ]

Comparitive Simulations

Transient Analysis

Sometimes system behavior under start-up is of interest.
In these cases, transient-phase samples should be kept, not tossed.
Transient-phase analysis is harder than is steady-state analysis.
- The transient phase is (usually) short.
- The associated distributions are non-stationary.
Transient analysis is usually concerned with non-moment statistics.
- The minimum, maximum, threshold, cardinal values, for example.
Because time-series is less reliable, spectral (that is, spatial) analysis becomes relatively more important.

Points to Remember

A single simulation run produces correct results with effectively zero probability.
At minimum, the results of a simulation should be
1. a mean for each value of interest,
2. an interval around the mean to bound the true value, and
3. a probability that interval actually bounds the true value.
- "The estimated server utilization has a mean 79% with a 95% chance that the true utilization is within 0.003 of the estimated mean."

This page last modified on 4 April 2005.