Rare event simulation and splitting for discontinuous random variables

Walter, Clément^1, 2 

¹ CEA, DAM, DIF, 91297 Arpajon, France
² Laboratoire de Probabilités et Modèles Aléatoires, Université Paris Diderot, 75205 Paris cedex 05, France

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

Résumé

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).

Détail

Reçu le : 2015-07-03
DOI : 10.1051/ps/2015017

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