The design and analysis of a generalized RESTART/DPR algorithm for rare event simulation

We consider a general class of branching methods with killing for the estimation of rare events. The class includes a number of existing schemes, including RESTART and DPR (Direct Probability Redistribution). A method for the design and analysis is developed when the quantity of interest can be embedded in a sequence whose limit is determined by a large deviation principle. A notion of subsolution for the related calculus of variations problem is introduced, and two main results are proved. One is that the number of particles and the total work scales subexponentially in the large deviation parameter when the branching process is constructed according to a subsolution. The second is that the asymptotic performance of the schemes as measured by the variance of the estimate can be characterized in terms of the subsolution. Some examples are given to demonstrate the performance of the method.