Multilevel Splitting for Estimating Rare Event Probabilities

We analyze the performance of a splitting technique 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. Under some assumptions about the simulated process, 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 for rare event simulation. These results follow from a branching-process analysis of the method. We illustrate our theoretical results with some numerical examples for queueing models.

By: Paul Glasserman (Columbia Univ.), Philip Heidelberger, Perwez Shahabuddin (Columbia Univ.) and Tim Zajic (Columbia Univ.)

Published in: Operations Research, volume 47, (no 4), pages 585-600 in 1999

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .