The RESTART method is a widely applicable simulation technique for the estimation of rare event probabilities. The method is based on the idea to restart the simulation at certain intermediate stages, in order to generate more occurrences of the rare event. In many cases we are interested in the (rare) event that a real-valued function of some Markov process exceeds a high level. We explore the possibility of speeding up the RESTART method for such models by using certain conditional distributions of the Markov process, called 'entrance distributions'. As a by-product, we show, for certain models, a remarkable relationship between the entrance distribution and the optimal exponential change of measure used in the Importance Sampling method, the other main rare event simulation technique.
We find that using the entrance distribution in the RESTART method will usually yield a significant reduction in simulation effort in situations where the method can be applied. The standard RESTART method is more robust, but is not as efficient as the new method since it does not use any information on the system we are simulating.
|CTIT technical reports series
|University of Twente, Centre for Telematics and Information Technology (CTIT)