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

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)