Importance sampling for queueing simulations

Abstract

In a simulation it is desired to control variability and decrease the variance of experiments. So we can be aware of the accuracy of the constructed models and consequently can supply reliable results. Importance Sampling is one of the variance reduction techniques commonly used in Monte Carlo Methods. There are two types: Independent Importance Sampling (IIS) where iid random variables are used to calculate some expectations whereas the other one is Dependent Importance Sampling (DIS) where dependent random variables are used. This thesis includes a research to find the Importance Sampling density which gives the lowest variance. We illustrate the Importance Sampling method on an M/M/1 queueing problem with a finite upstreambuffer and solve it with an efficient C coded simulation program. We first execute naive simulation, afterwards we carry out Importance Sampling and reach a meaningful decrease in the estimated variance when calculating the probability that the queue length exceeds the buffer size. Thus, one can calculate any expectation with good confidence intervals that cannot be calculated analytically. Numerical results indicate that heavy tailed Importance Sampling distributions provide substantial variance reduction.