Analysis of adaptive multilevel splitting algorithms in an idealized case

DOI10.1051/PS/2014029MaRDI QIDQ2786485zbMATH OpenOpenAlexFDO

Authors Charles-Edouard Bréhier, Tony Lelièvre, Mathias Rousset

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/1405.1352

zbMATH Keywords

algorithmMonte Carlo simulationmultilevel splittingrare events

Mathematics Subject Classification ID

Order statistics; empirical distribution functions (62G30) Monte Carlo methods (65C05) Stochastic particle methods (65C35)

Abstract: The Adaptive Multilevel Splitting algorithm is a very powerful and versatile method to estimate rare events probabilities. It is an iterative procedure on an interacting particle system, where at each step, the $k$ less well-adapted particles among $n$ are killed while $k$ new better adapted particles are resampled according to a conditional law. We analyze the algorithm in the idealized setting of an exact resampling and prove that the estimator of the rare event probability is unbiased whatever $k$. We also obtain a precise asymptotic expansion for the variance of the estimator and the cost of the algorithm in the large $n$ limit, for a fixed $k$.

Review text

The paper investigates the adaptive multilevel splitting algorithms in the context of an idealized case. One aim of the paper is to discuss the necessity of the assumption on the continuity of the cumulative distribution function of a given a real-valued positive random variable \(X\). The authors prove that such an assumption is only required locally near \(0\). Denote for \(a>0\), \(p=p(X>a)\) and for integers \(n,k\) where \(n\) designs the total number of particles and \(k\) the number of resampled particles at each iteration. Consider also an estimator NEWLINE\[NEWLINE \hat{p}^{n,k}=C^{n,k}(1-\frac{k}{n})^{J^{n,k}} NEWLINE\]NEWLINE of the probability \(p\), and where \(C^{n,k}\) and \(J^{n,k}\) are appropriate constants depending on \(n\) and \(k\). The authors prove that \(\hat{p}^{n,k}\) is an unbiased estimator of \(p\) and obtain an explicit asymptotic expression for the variance of such an estimator. The crucial idea is based on adapting the family of conditional probabilities \(P(X > a\mid X > x)\) and to consider corresponding estimators relatively to the adaptive multilevel splitting algorithm. The paper is achieved by the analysis of the computational cost by deriving functional equations for the variance and the mean number of iterations in the algorithm.

Recommendations

• On the asymptotic normality of adaptive multilevel splitting
• Large deviations principle for the Adaptive Multilevel Splitting Algorithm in an idealized setting
• Adaptive multilevel splitting: historical perspective and recent results
• Fluctuation analysis of adaptive multilevel splitting
• Unbiasedness of some generalized adaptive multilevel splitting algorithms
• scientific article; zbMATH DE number 1069510
• Statistical behaviour of adaptive multilevel splitting algorithms in simple models
• A large deviations perspective on the efficiency of multilevel splitting
• Application of adaptive multilevel splitting to high-dimensional dynamical systems
• On efficiency of multilevel splitting

Cites work

• Adaptive Multilevel Splitting for Rare Event Analysis
• Adaptive particle techniques and rare event estimation
• Functional Integration and Partial Differential Equations. (AM-109)
• scientific article; zbMATH DE number 3196612 (Why is no real title available?)
• Multilevel splitting for estimating rare event probabilities
• Nested sampling for general Bayesian computation
• Rare Event Simulation using Monte Carlo Methods
• Sequential Monte Carlo for rare event estimation
• Simulation and estimation of extreme quantiles and extreme probabilities
• Stochastic simulation: Algorithms and analysis
• Unbiasedness of some generalized adaptive multilevel splitting algorithms

Cited in

(19)

• Combinatorial analysis of the adaptive last particle method
• Rare event simulation and splitting for discontinuous random variables
• Central limit theorem for adaptive multilevel splitting estimators in an idealized setting
• Adaptive Multilevel Splitting for Rare Event Analysis
• Large deviations principle for the Adaptive Multilevel Splitting Algorithm in an idealized setting
• Spectral theory for random Poincaré maps
• On the asymptotic normality of adaptive multilevel splitting
• On a new class of score functions to estimate tail probabilities of some stochastic processes with adaptive multilevel splitting
• Computing return times or return periods with rare event algorithms
• An ergodic theorem for the weighted ensemble method
• Coupling rare event algorithms with data-based learned committor functions using the analogue Markov chain
• Optimizing Weighted Ensemble Sampling of Steady States
• Fluctuation analysis of adaptive multilevel splitting
• Unbiasedness of some generalized adaptive multilevel splitting algorithms
• Adaptive multilevel splitting: historical perspective and recent results
• Adaptive particle techniques and rare event estimation
• On the optimal importance process for piecewise deterministic Markov process
• Adaptive multilevel subset simulation with selective refinement
• Statistical behaviour of adaptive multilevel splitting algorithms in simple models

This page was built for publication: Analysis of adaptive multilevel splitting algorithms in an idealized case

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