Multilevel splitting for estimating rare event probabilities

We analyze the performance of a splitting technique for the estimation of r are event probabilities by simulation. A straightforward estimator of the p robability 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 p roduce little information about its probability using this approach. The me thod we study reinforces promising paths at intermediate thresholds by spli tting them into subpaths which then evolve independently. If implemented ap propriately, this has the effect of dedicating a greater fraction of the co mputational effort to informative runs. We analyze the method for a class o f models in which, roughly speaking, the number of states through which eac h threshold can be crossed is bounded. Under additional assumptions, we ide ntify the optimal degree of splitting at each threshold as the rarity of th e event increases: It should be set so that the expected number of subpaths reaching each threshold remains roughly constant. Thus implemented, the me thod 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 queuein g models.