Fast Simulation of Markov Chains with Small Transition Probabilities

Consider a finite-state Markov chain where the transition probabilities differ by orders of magnitude. This Markov chain has an "attractor state," i.e., from any state of the Markov chain there exists a sample path of significant probability to the attractor state. There also exists a "rare set," which is accessible from the attractor state only by sample paths of very small probability. The problem is to estimate the probability that starting from the attractor state, the Markov chain hits the rare set before returning to the attractor state. Examples of this setting arise in the case of reliability models with highly reliable components as well as in the case of queueing networks with low traffic. Importance-sampling is a commonly used simulation technique for the fast estimation of rare-event probabilities. It involves simulating the Markov chain under a new probability measure that emphasizes the most likely paths to the rare set. Previous research focused on developing importance-sampling schemes for a special case of Markov chains that did not include "high-probability cycles." We show through examples that the Markov chains used to model many commonly encountered systems do have high-probability cycles, and existing importance-sampling schemes can lead to infinite variance in simulating such systems. We then develop the insight that in the presence of high-probability cycles care should be taken in allocating the new transition probabilities so that the variance accumulated over these cycles does not increase without bounds. Based on this observation we develop two importance-sampling techniques that have the bounded relative error property, i.e., the simulation run-length required to estimate the rare-event probability to a fixed degree of accuracy remains bounded as the event of interest becomes more rare.