Output AnalysisDave GoldsmanMarch 4, 2002Outline of Presentation:• Introduction• Terminating Simulations• Initialization Problems• Steady-State Analysis• Comparison of Systems• Conclusions11. INTRODUCTIONInput processes driving a simulation are usually random variables(e.g., interarrival times, service times, and breakdown times).We must also regard the output from the simulation as random.Runs of the simulation only yield estimates of measures of systemperformance (e.g., the mean customer waiting time).These estimators are themselves random variables, and are there-fore subject to sampling error.Must take sampling error must be taken into account to makevalid inferences concerning system performance.2Problem: simulations almost never produce raw output that isindependent and identically distributed (i.i.d.) normal data.Example: Consecutive customer waiting times from a queueingsystem. . .(1) Are not independent — typically, they are serially correlated.If one customer at the post office waits in line a long time, thenthe next customer is also likely to wait a long time.(2) Are not identically distributed. Customers showing up earlyin the morning might have a much shorter wait than those whoshow up just before closing time.(3) Are not normally distributed — they are usually skewed tothe right (and are certainly never less than zero).3Thus, it’s difficult to apply “classical” statistical techniques tothe analysis of simulation output.Our purpose: Give methods to perform statistical analysis ofoutput from discrete-event computer simulations.To facilitate the presentation, we identify two types of simula-tions with respect to output analysis: Terminating and Steady-State simulations.4(1) Terminating (or transient) simulations. Here, the nature ofthe problem explicitly defines the length of the simulation run.For instance, we might be interested in simulating a bank thatcloses at a specific time each day.(2) Nonterminating (steady-state) simulations. Here, the long-run behavior of the system is studied. Presumedly this “steady-state” behavior is independent of the simulation’s initial condi-tions. An example is that of a continuously running productionline for which the experimenter is interested in some long-runperformance measure.5Techniques to analyze output from terminating simulations arebased on the method of indep. replications, (discussed in§2).Additional problems arise for steady-state simulations. . .Must now worry about the problem of starting the simulation —how should it be initialized at time zero, andHow long must it be run before data representative of steadystate can be collected?Initialization problems are considered in§3.§4 deals with point and confidence interval estimation for steady-state simulation performance parameters.§5 concerns the problem of comparing a number of competingsystems.62. TERMINATING SIMULATIONSHere we are we simulate some system of interest over a finitetime horizon.For now, assume we obtain discrete simulation output Y1,Y2,...,Ym,where the number of observations m can be a constant or a ran-dom variable.Example: The experimenter can specify the number m of cus-tomer waiting times Y1,Y2,...,Ymto be taken from a queueingsimulation.Or m could denote the random number of customers observedduring a specified time period [0,T].7Alternatively, we might observe continuous simulation output{Y (t)|0 ≤ t ≤ T } over a specified interval [0,T].Example: If we are interested in estimating the time-averagednumber of customers waiting in a queue during [0,T], the quan-tity Y (t) would be the number of customers in the queue attime t.8Easiest Goal: Estimate the expected value of the sample meanof the observations,θ ≡ E[¯Ym],where the sample mean in the discrete case is¯Ym≡1mmi=1Yi(with a similar expression for the continuous case).Example: We might be interested in estimating the expectedaverage waiting time of all customers at a shopping center duringthe period 10 a.m. to 2 p.m.9Although¯Ymis an unbiased estimator for θ, a proper statisticalanalysis requires that we also provide an estimate of Var(¯Ym).Since the Yi’s are not necessarily i.i.d. random variables, it is maybe that Var(¯Ym) =Var(Yi)/m for any i, a case not covered inelementary statistics textbooks.For this reason, the familiar sample variance,S2≡mi=1(Yi−¯Ym)2/(m − 1),is likely to be highly biased as an estimator of mVar(¯Ym).One should not use S2/m to estimate Var(¯Ym).10The way around the problem is via the method of independentreplications (IR).IR estimates Var(¯Ym) by conducting b independent simulationruns (replications) of the system under study, where each repli-cation consists of m observations.It is easy to make the replications independent — just re-initializeeach replication with a different pseudo-random number seed.11Notation and Stuff.Denote the sample mean from replication i byZi≡1mmj=1Yi,j,where Yi,jis observation j from replication i,fori =1, 2,...,band j =1, 2,...,m.If each run is started under the same operating conditions (e.g.,all queues empty and idle), then the replication sample meansZ1,Z2,...,Zbare i.i.d. random variables.12Then the obvious point estimator for Var(¯Ym)=Var(Zi)isˆVR≡1b − 1bi=1(Zi−¯Zb)2,where the grand mean is defined as¯Zb≡1bbi=1Zi.Notice how closely the forms ofˆVRand S2/m resemble eachother. But since the replicate sample means are i.i.d.,ˆVRisusually much less biased for Var(¯Ym)thanisS2/m.13In light of the above, we see thatˆVR/b is a reasonable estimatorfor Var(¯Zb).If the number of observations per replication, m, is large enough,a central limit theorem tells us that the replicate sample meansare approximately i.i.d. normal.Then we have an approximate 100(1−α)% two-sided confidenceinterval (CI) for θ,θ ∈¯Zb± tα/2,b−1ˆVR/b , (1)where tα/2,b−1is the 1 − α/2 quantile of the t-distribution withb − 1 degrees of freedom.14Example: Suppose we want to estimate the expected averagewaiting time for the first 5000 customers in a certain queueingsystem. We will make five independent replications of the sys-tem, with each run initialized empty and idle and consisting of5000 waiting times. The resulting replicate means are:i 12345Zi3.2 4.3 5.1 4.2 4.6Then¯Z5=4.28 andˆVR=0.487. For level α =0.05, we havet0.025,4=2.78, and (1) gives [3.41, 5.15] as a 95% CI for theexpected average waiting time for the first 5000