Multilevel Splitting for Estimating Rare Event Probabilities
- 1 August 1999
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 47 (4), 585-600
- https://doi.org/10.1287/opre.47.4.585
Abstract
We analyze the performance of a splittingtechnique for the estimation of rare event probabilities by simulation. A straightforward estimator of the probability of an event evaluates the proportion of simulated paths on which the event occurs. If the event is rare, even a large number of paths may produce little information about its probability using this approach. The method we study reinforces promising paths at intermediate thresholds by splitting them into subpaths which then evolve independently. If implemented appropriately, this has the effect of dedicating a greater fraction of the computational effort to informative runs. We analyze the method for a class of models in which, roughly speaking, the number of states through which each threshold can be crossed is bounded. Under additional assumptions, we identify the optimal degree of splitting at each threshold as the rarity of the event increases: It should be set so that the expected number of subpaths reaching each threshold remains roughly constant. Thus implemented, the method is provably effective in a sense appropriate to rare event simulations. These results follow from a branching-process analysis of the method. We illustrate our theoretical results with some numerical examples for queueing models.Keywords
This publication has 22 references indexed in Scilit:
- A Look At Multilevel SplittingPublished by Springer Science and Business Media LLC ,1998
- A large deviations perspective on the efficiency of multilevel splittingIEEE Transactions on Automatic Control, 1998
- Splitting for rare event simulationPublished by Association for Computing Machinery (ACM) ,1996
- Analysis of an importance sampling estimator for tandem queuesACM Transactions on Modeling and Computer Simulation, 1995
- The Asymptotic Efficiency of Simulation EstimatorsOperations Research, 1992
- Optimally efficient estimation of the statistics of rare events in queueing networksIEEE Transactions on Automatic Control, 1991
- Optimizing cell importances using an extension of the DSA — theory, implementation, preliminary resultsProgress in Nuclear Energy, 1990
- Application of the Direct Statistical Approach on a Multisurface Splitting Problem in Monte Carlo CalculationsNuclear Science and Engineering, 1986
- General statistical model for geometrical splitting in Monte Carlo - ITransport Theory and Statistical Physics, 1985
- Monte Carlo MethodsPublished by Springer Science and Business Media LLC ,1964