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

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

0.00 Avg rating0 Votes
Article ID: iaor20119388
Volume: 189
Issue: 1
Start Page Number: 63
End Page Number: 102
Publication Date: Sep 2011
Journal: Annals of Operations Research
Authors: ,
Keywords: rare events
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.