Rare event simulation and splitting for discontinuous random variables

Walter, Clément

ESAIM: Probability and Statistics, Tome 19 (2015), pp. 794-811.

Multilevel Splitting methods, also called Sequential Monte−Carlo or Subset Simulation, are widely used methods for estimating extreme probabilities of the form $P\left[S\right(𝐔)>q]$ where $S$ is a deterministic real-valued function and $𝐔$ can be a random finite- or infinite-dimensional vector. Very often, $X:=S\left(𝐔\right)$ is supposed to be a continuous random variable and a lot of theoretical results on the statistical behaviour of the estimator are now derived with this hypothesis. However, as soon as some threshold effect appears in $S$ and/or $𝐔$ is discrete or mixed discrete/continuous this assumption does not hold any more and the estimator is not consistent. In this paper, we study the impact of discontinuities in the cdf of $X$ and present three unbiased corrected estimators to handle them. These estimators do not require to know in advance if $X$ is actually discontinuous or not and become all equal if $X$ is continuous. Especially, one of them has the same statistical properties in any case. Efficiency is shown on a 2-D diffusive process as well as on the Boolean SATisfiability problem (SAT).

Classification : 65C05 65C60 62L12 62N02
Mots clés : Rare event simulation, multilevel splitting, RESTART, sequential Monte Carlo, extreme event estimation, counting, Last Particle Algorithm

M. Amrein and H.R. Künsch, A variant of importance splitting for rare event estimation: Fixed number of successes. ACM Trans. Model. Comput. Simul. (TOMACS) (2011).

S.-K. Au and J.L. Beck, Estimation of small failure probabilities in high dimensions by subset simulation. Probab. Eng. Mech. 16 (2001) 263–277.

A. Beskos, A. Jasra, N. Kantas and A. Thiery, On the convergence of adaptive sequential Monte Carlo methods. To appear in Ann. Appl. Probab. (2015).

I. Bezáková, D. Štefankovic, V.V. Vazirani and E. Vigoda, Accelerating simulated annealing for the permanent and combinatorial counting problems. SIAM J. Comput. 37 (2008) 1429–1454. | Zbl

Z.I. Botev and D.P. Kroese, An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting. Methodology Comput. Appl. Probab. 10 (2008) 471–505. | Zbl

Z.I. Botev and D.P. Kroese, Efficient Monte Carlo simulation via the generalized splitting method. Stat. Comput. 22 (2012) 1–16. | Zbl

C.-E. Brérhier, T. Leliévre and M. Rousset, Analysis of adaptive multilevel splitting algorithms in an idealized case. ESAIM: PS 19 (2015) 361–394. | Zbl

F. Cerou, P. Del Moral, A. Guyader and F. Malrieu, Fluctuation analysis of adaptive multilevel splitting. Preprint arXiv:1408.6366 (2014).

F. Cérou and A. Guyader, Adaptive multilevel splitting for rare event analysis. Stoch. Anal. Appl. 25 (2007) 417–443. | Zbl

F. Cérou, A. Guyader, R. Rubinstein and R. Vaisman, On the use of smoothing to improve the performance of the splitting method. Stochastic Models 27 (2011) 629–650. | Zbl

F. Cérou, P. Del Moral, T. Furon and A. Guyader, Sequential Monte Carlo for rare event estimation. Stat. Comput. 22 (2012) 795–808. | Zbl

B. Charles-Edouard, G. Maxime, G. Ludovic, L. Tony and R. Mathias, Unbiasedness of some generalized adaptive multilevel splitting algorithms. e-prints Preprint arXiv:1505.02674 (2015).

P. Del Moral, A. Doucet and A. Jasra, Sequential Monte Carlo samplers. J. Roy. Statist. Soc.: Ser. B (Statistical Methodology) 68 (2006) 411–436. | Zbl

A. Froda, Sur la Distribution des Propriétés de Voisinage des Fonctions de Variables Réelles. Ph.D. thesis, Université de Paris (1929). | JFM

M.J.J. Garvels, The splitting method in rare event simulation. Universiteit Twente (2000).

P. Glasserman, P. Heidelberger, P. Shahabuddin and T. Zajic, Multilevel splitting for estimating rare event probabilities. Oper. Res. 4 (1999) 585–600. | Zbl

A. Guyader, N. Hengartner and E. Matzner-Løber, Simulation and estimation of extreme quantiles and extreme probabilities. Appl. Math. Optim. 64 (2011) 171–196. | Zbl

H. Hoos and T. Stiitzle, SATLlB: An online resource for research on SAT. Sat2000: highlights of satisfiability research in the year 2000 (2000) 283. | Zbl

M. Huber and S. Schott, Using TPA for Bayesian Inference. Bayesian Statistics 9 (2011) 257–282.

H. Kahn and T.E. Harris, Estimation of Particle Transmission by Random Sampling. National Bureau of Standards Applied Mathematics Series 12 (1951) 27–30.

M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press (2005). | Zbl

R. Motwani and P. Raghavan, Randomized Algorithms. Chapman & Hall/CRC (2010). | Zbl

M. Rosenbluth and A. Rosenbluth, Monte Carlo calculation of the average extension of molecular chains. J. Chem. Phys. 23 (2004) 356–359.

R. Rubinstein, The Gibbs cloner for combinatorial optimization, counting and sampling. Methodol. Comput. Appl. Probab. 11 (2009) 491–549. | Zbl

R. Rubinstein, Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work. Methodol. Comput. Appl. Probab. 12 (2010) 1–50. | Zbl

R. Rubinstein, A. Dolgin and R. Vaisman, The splitting method for decision making. Commun. Statistics-Simul. Comput. 41 (2012) 905–921. | Zbl

R.Y. Rubinstein and D.P. Kroese, Simulation and the Monte Carlo method. In vol. 707. John Wiley & Sons (2011). | Zbl

E. Simonnet, Combinatorial analysis of the adaptive last particle method. To appear in Stat. Comput. (2014). Doi: . | DOI

J. Skilling, Nested sampling for general bayesian computation. Bayesian Analysis 1 (2006) 833–859. | Zbl

C. Walter, Moving particles: A parallel optimal multilevel splitting method with application in quantiles estimation and meta-model based algorithms. Structural Safety 55 (2015) 10–25.

C. Walter, Point process-based Monte Carlo estimation. To appear in Stat. Comput. (2015) Doi: . | DOI

C. Walter and G. Defaux, Rare event simulation: a point process interpretation with application in probability and quantile estimation. Proc. of the 12$th$ International Conference on Applications of Statistics and Probability (2015).