Estimating probabilities of rare events in regenerative systems via importance sampling

Abstract

In the high-speed networks currently being designed, the probability of packet loss required is very low, while the closed-form expressions for these events are usually not available. Therefore, one needs to estimate these probabilities via simulation. However, estimating probabilities of rare events via simulations can be computationally very expensive. Importance Sampling (IS) is a simulation technique which can improve the simulation efficiency by several orders of magnitude in many such instances. In this thesis, we develop some theory of IS in the context of regenerative simulation. Our framework is more general than most studies in IS available today. This is a natural setting for regenerative IS. In addition, it also provides the theoretical basis for comparing different IS schemes, which also incorporates the different regeneration lengths. In this setting, we consider two estimators to estimate stationary probabilities of rare events. We show the consistency, asymptotic normality, some rates of convergence, and convergence of moments. These results are easily obtainable from limit theorems available in the literature, but some of them are new in the context of IS. We also show, explicitly, the difficulty in estimating rare event probabilities in regenerative simulation. This was known previously in the i.i.d. case but assumed to be true in regenerative simulation. Next, we obtain theoretical results to provide some guidelines in selecting good IS measures. Again, these insights were previously available based only on the i.i.d. case. Finally, we suggest an improvement in a recent IS scheme of Asmussen et al. [5] for queueing systems. We show via simulations that we always obtain an improvement, and at times it can be substantial. We also suggest an adaptive IS scheme. The computational advantage of this needs to be carefully investigated.