Rare event simulation and splitting for discontinuous random variables

DOI10.1051/PS/2015017MaRDI QIDQ2786505zbMATH OpenOpenAlexFDO

Authors Clément Walter

Publication date 12 February 2016

Published in European Series in Applied and Industrial Mathematics (ESAIM): Probability and Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.00919

zbMATH Keywords

countingextreme event estimationlast particle algorithmmultilevel splittingrare event simulationsequential Monte Carlo

Mathematics Subject Classification ID

Sequential estimation (62L12) Estimation in survival analysis and censored data (62N02) Monte Carlo methods (65C05)

Abstract: Multilevel Splitting methods, also called Sequential Monte-Carlo or emph{Subset Simulation}, are widely used methods for estimating extreme probabilities of the form $P[S(mathbfU)>q]$ where $S$ is a deterministic real-valued function and $mathbfU$ can be a random finite- or infinite-dimensional vector. Very often, $X:=S(mathbfU)$ 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 $mathbfU$ 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 emph{cdf} of $X$ and present three unbiased emph{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 emph{Boolean SATisfiability problem} (SAT).

Review text

The authors study the impact of discontinuities in the cdf of a random variable \(X\) by means of three unbiased and corrected estimators. The particularity of the constructed estimators is the fact that they did not require in advance the variable \(X\) to be actually discontinuous or not. Existing studies as declared from the authors did not require the continuity of the cdf of \(X\). This was one first motivation behind the developments in the present paper. The authors studied both the distribution of the number of iterations and the MVUE estimator in the case with strict inequality and the one with non-strict inequality. Efficiency of the theoretical results has been shown also on some numerical examples based on a 2-dimensional diffusive process as well as on the well-known Boolean satisfiability problem.

Recommendations

• Unbiased simulation of rare events in continuous time
• Rare events, splitting, and quasi-Monte Carlo
• Analysis of adaptive multilevel splitting algorithms in an idealized case
• RARE EVENT SIMULATION
• Some recent results in rare event estimation

Cites work

• A combined splitting-cross entropy method for rare-event probability estimation of queueing networks
• A variant of importance splitting for rare event estimation: fixed number of successes
• Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
• Adaptive Multilevel Splitting for Rare Event Analysis
• An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting
• Analysis of adaptive multilevel splitting algorithms in an idealized case
• Combinatorial analysis of the adaptive last particle method
• Efficient Monte Carlo simulation via the generalized splitting method
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Multilevel splitting for estimating rare event probabilities
• Nested sampling for general Bayesian computation
• On the convergence of adaptive sequential Monte Carlo methods
• On the use of smoothing to improve the performance of the splitting method
• Probability and Computing
• Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work
• Sequential Monte Carlo for rare event estimation
• Sequential Monte Carlo Samplers
• Simulation and estimation of extreme quantiles and extreme probabilities
• Simulation and the Monte Carlo Method
• The Gibbs cloner for combinatorial optimization, counting and sampling
• The splitting method for decision making

Cited in

(4)

• Discontinuity detection in multivariate space for stochastic simulations
• A rare event approach to high-dimensional approximate Bayesian computation
• Rare events, splitting, and quasi-Monte Carlo
• Nested sampling methods

This page was built for publication: Rare event simulation and splitting for discontinuous random variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2786505)