
|
Basic Notions
Cross Referencing: |
Infinite Horizon EstimationAn 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.
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:
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.
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.
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 MethodThis 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.
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. |
|
SimSpiders Main Page |