Transcript Confidence Interval

Simulation &
Confidence Intervals
COMP5416
Advanced Network Technologies
Simulation Implementation Details
• Need to store
– Core variables such as event list, sim clock
– State variables such as packet queue
– Statistics such as packet arrived, departed
• Initialise for bootstrap
– E.g. Packet arrival
• Provide terminate condition
– End time or number of events to run
• Execute events from list
School of Information Technologies
COMP5416 Confidence - 2
E.G.: SSQ
Simulation
Start
Init
More
Events?
No
Yes
Arrvl?
Yes
Update vars
Schedule next
arrival
No
Dept?
Yes
Update vars
Schedule next
departure
Compute
performance
Display stats
End
School of Information Technologies
COMP5416 Confidence - 3
Transients in the Simulation
• Everything above assumes that the simulation data is
collected once the simulation has achieved steady
state, otherwise the tests are meaningless.
• There are many ways to determine this
– a pragmatic approach is to ensure that the simulation runs
for sufficiently long so that the transients have negligible
effect on the estimates of confidence interval.
• If data is available from only short runs (i.e. few data
points), then you will need to ensure that transient
data is discarded.
School of Information Technologies
COMP5416 Confidence - 4
Independent Samples
• Assume we have a sequence of n data points
{z1,z2,...,zn} which are known to be independent.
n
• Estimate mean:
 zi
zˆ  i 1
n
• Estimate Sample Variance:
2
2
 zi   n * zˆ 
n
Vˆ 
i 1
(n  1)
School of Information Technologies
COMP5416 Confidence - 5
Confidence Interval for Independent
Samples
• Assume that there are enough samples so that we can use
the Central Limit Theorem (i.e. approx Gaussian distributed)
• Make a hypothesis test – with (say) 95% probability, the true
mean lies within some interval
• From a Gaussian distribution, the 95% confidence interval is
the estimated mean, ±1.96 estimated standard deviations
• The standard deviation of the sample mean is Vˆ n
• Then we say that, with probability 95%, the true mean lies
within the range

Vˆ
Vˆ 
 zˆ  1.96

, zˆ  1.96
n
n


School of Information Technologies
COMP5416 Confidence - 6
Confidence Interval
Confidence Interval,
with probability x%,
true mean lies within
this range
Estimated Mean
School of Information Technologies
COMP5416 Confidence - 7
Effect of Correlation
• Simulation data is never independent – there is correlation
between successive samples.
– It is always a good idea to estimate the correlation – the
autocovariance of lag k is defined as:
R(k )  E( zi  z )( zi  k  z )
where
z is the true mean
• If the autocovariances are low, then an approximation of
independence is reasonable, otherwise we need to do
better.
School of Information Technologies
COMP5416 Confidence - 8
Method of Batch Means
• The idea here is to group the data into batches, so
that successive batches are approximately
independent.
• For example, if we have n data points , group them
into m batches of size p=n/m
• Calculate the m batch means
• Now treat the batches as if they were independent
School of Information Technologies
COMP5416 Confidence - 9
Batch Means
• Gives less bias in the estimator, at the expense of
more variability in the estimator of precision.
The difficult part is choosing the batch size
– too large a batch produces confidence intervals which are
much larger than is justified by the actual data
– too small a batch produces excessive correlation, which
produces misleadingly small confidence intervals
• Method is easy to implement, and is probably the
most widely-used method of estimating confidence
intervals.
School of Information Technologies
COMP5416 Confidence - 10
References
• B.D. Ripley, “Uses and abuses of statistical
simulation”, Mathematical Programming, Vol 42, pp
53-68, 1988
• K. Pawlikowski, “Steady-state simulation of queueing
processes: A survey of problems and solutions”, ACM
Computing Surveys, Vol 22, No 2, pp123-170, June
1990
• A.M. Law and W.D. Kelton, Simulation Modelling and
Analysis, McGraw-Hill, 1991
School of Information Technologies
COMP5416 Confidence - 11