Abstract

A number of schemes for Monte Carlo estimation of rare events are based on splitting particles when they reach certain thresholds. Among these is the interacting particle scheme introduced in [1] and also discussed at recent RESIM conferences. A feature of this approach that is considered attractive is that the total number of particles (and hence the total computational effort needed to generate a sample) is controlled. Although this scheme has been observed to perform well as the probability being estimated gets small, prior analysis has tended to focus on limits where the number of particles gets large with the probability held fixed. One reason is that all particles are statistically re-coupled at each threshold, and hence limits where the number of particles is fixed and the probability gets small are difficult to analyze. We introduce some new techniques for the large deviation analysis of such systems. Although the large deviation scaling for the probability of interest is what is known as a small noise large deviation limit, the analysis of interacting particles systems requires ideas from the large deviation theory for occupation measures of Markov chains. [1] P. Del Moral and J. Garnier. Genealogical particle analysis of rare events. Ann. Appl. Probab., 15:24962534, 2005.