Large deviations principle for the Adaptive Multilevel Splitting Algorithm in an idealized setting

作者：Brehier Charles Edouard^*

来源：Alea (Rio de Janeiro): Latin American Journal of Probability and Mathematical Statistics , 2015, 12(2): 717-742.

• Monte-Carlo simulation
• rare events
• multilevel splitting
• large deviations

The Adaptive Multilevel Splitting (AMS) algorithm is a powerful and versatile method for the simulation of rare events. It is based on an interacting (via a mutation-selection procedure) system of replicas, and depends on two integer parameters: n is an element of Z(+)* the size of the system and the number k is an element of {1,..., n - 1} of the replicas that are eliminated and resampled at each iteration.
In an idealized setting, we analyze the performance of this algorithm in terms of a Large Deviations Principle when n goes to infinity, for the estimation of the (small) probability P(X > a) where a is a given threshold and X is real-valued random variable. The proof uses the technique introduced in I Brehier et al. (2015c): in order to study the log-Laplace transform, we rely on an auxiliary functional equation.
Such Large Deviations Principle results are potentially useful to study the algorithm beyond the idealized setting, in particular to compute rare transitions probabilities for complex high-dimensional stochastic processes.

• 出版日期2015