Moving particles: A parallel optimal Multilevel Splitting method with application in quantiles estimation and meta-model based algorithms

• Sequential sampling of a real random variable is given a Poisson Process analysis.
• Probability of an event is related to its expected arrival time in the Point Process.
• Events of probability p are reached within log(1/p) simulations.
• This framework brings full parallelisation of optimal Multilevel Splitting methods.
• A parallel algorithm for quantile estimation is introduced and analyzed.

Considering the issue of estimating small probabilities p, i.e. measuring a rare   domain F={x|g(x)>q}F={x|g(x)>q} with respect to the distribution of a random vector XX, Multilevel Splitting strategies (also called Subset Simulation) aim at writing F as an intersection of less rare events (nested subsets) such that their measures are conditionally easily computable. However the definition of an appropriate sequence of nested subsets remains an open issue.We introduce here a new approach to Multilevel Splitting methods in terms of a move of particles in the input space. This allows us to derive two main results: (1) the number of samples required to get a realisation of XX in F   is drastically reduced, following a Poisson law with parameter log1/plog1/p (to be compared with a Geometric law with parameter p for naive Monte-Carlo); and (2) we get a parallel optimal Multilevel Splitting algorithm where there is indeed no subset to define any more.We also apply result (1) in quantile estimation producing a new parallel algorithm and derive a new strategy for the construction of first Design of Experiments in meta-model based algorithms.