SimSpiders
by Felisa J. Vázquez-Abad and Yanick Champoux


Output Analysis



Basic Notions
Stochastic Processes:
- Finite Horizon
- Infinite Horizon
     - Batch Means
     - Regenerative

Cross Referencing:
- Topics Index
- SimSpiders Main Page


Infinite Horizon Estimation

An infinite horizon simulation consists of a simulation of a stochastic process where we are interested in a long term behaviour. Mathematically, our problem consists in estimating the expectation of a function of the process over an infinite horizon. In most applications we suppose that the process eventually settles down to a steady state or stationary behaviour.

In some special cases, the long term profit rate is well defined even if the distribution of the process does not possess a well defined limit, as in our Wine Provisioning example.

Since we should never attempt to run a program over an infinite period of time, in practice we choose a simulation length to approximate the stationary distribution. When the process simulated is not stationary, we generally warm up the simulation and assume that the process is "nearly stationary" from then on.

ESTIMATING THE ERROR: In order to approximate the estimation error, we could:

  • Replicate the simulation several times and use the CLT for independent random variables, or
  • Try to estimate the confidence interval over one single simulation.
The first approach is the most commonly used and invoques the methods used for finite horizon simulation. Since long simulations are generally required to better estimate stationary averages, the problem with this approach is the tremendous amount of computation and time required to estimate the confidence interval.

The second approach uses a couple of theorems that extend the CLT for stochastic processes.

The Batch Means Method

INITIAL BIAS: When the process is NOT stationary from the begining, we must first simulate the system to warm it up. Choosing m to avoid the transient period is often a hard problem and pilot simulations have to be performed. Welch's Method is based on smoothing the process through window averages that helps visualize when the distribution seems to be approximately stationary.

The Batch Means Method is based on regrouping the sums into K "batches" of length N each one, so that n=NK is the total simulation length. Our estimator is viewed then as an average of averages per batch, and these will be approximately normally distributed when N is sufficiently large.

THE LIMIT THEOREM WHEN K IS FIXED: In order to approximate the estimation error, we can use the asymptotic distribution of the sample average, as the batch size increases.


Graph showing the distribution of the estimator (dotted line) against the limiting t-student distribution (solid line).

THE CONFIDENCE INTERVAL: We can use the limit theorem above to give an approximate confidence interval, using:

The coverage of the above confidence is the area below the dotted line btween the two red vertical lines as shown in the plot above. It may be a poor one (smaller than the desired confidence level) if the simulation length is not sufficiently long. You can visit the inventory example to test for yourself.

THE GENERAL LIMIT THEOREM: In order to approximate the estimation error, we can use the asymptotic distribution of the sample average, as the simulation length increases.


Graph showing the distribution of the estimator (dotted line) against the limiting normal distribution (solid line).

THE CONFIDENCE INTERVAL: We can use the limit theorem above to give an approximate confidence interval, using:

The coverage of the above confidence is the area below the dotted line between the two red vertical lines as shown in the plot above. It may be a poor one (smaller than the desired confidence level) if the simulation length is not sufficiently long, or if we have made the wrong choice of batch size and number of batches. You can visit the inventory example to test for yourself.

The Regenerative Method

This method is applicable when a process "regenerates". In many problems of interest, when the process reaches a particular state, its future evolution no longer depends on the past. In this sense we say that it regenerates, which in no way implies that it repeats itself: since the evolution is in general random, then starting at the same conditions may give different outcomes, even if the distribution is common. The following depicts a typical regenerative process, arising in Queueing Theory, Risk Theory, and other areas.

Using the Renewal Theorem above, we must estimate both numerator and denominator separately. Therefore our estimator will in general use a fixed number M of regenerative cycles.

INITIAL BIAS: When we use Regenerative Estimation, it is no longer necessary to warm up the simulation. Therefore we may save computational time. However, as we shall presently see, the estiamtion of the variance requires more computations to be performed, which can sometimes offset the gain.

THE LIMIT THEOREM FOR RATIOS: In order to approximate the estimation error, we can use the asymptotic distribution of the sample average for i.i.d. random variables by transforming our estimator.


THE CONFIDENCE INTERVAL: We can use the limit theorem above to give an approximate confidence interval, using:

The coverage of the above confidence is the area below the dotted line between the two red vertical lines as shown in the plot above. It may be a poor one (smaller than the desired confidence level) if the simulation length is not sufficiently long. Notice that this confidence interval is given in terms of a fixed number of cycles and therefore we can't control the simulation length unless we know E[T], which is not generally the case. You can visit the inventory example to test for yourself.


Previous - finite horizon estimation SimSpiders Main Page

© Copyright 1998 Felisa J. Vázquez-Abad and Yanick Champoux. All rights reserved.