Skip to Main content Skip to Navigation
Reports

Adaptive multilevel splitting for rare event analysis

Frédéric Cérou 1 Arnaud Guyader 1
1 ASPI - Applications of interacting particle systems to statistics
UR1 - Université de Rennes 1, Inria Rennes – Bretagne Atlantique , CNRS - Centre National de la Recherche Scientifique : UMR6074
Résumé : The estimation of rare event probability is a crucial issue in areas such as reliability, telecommunications, aircraft management. In complex systems, analytical study is out of question and one has to use Monte Carlo methods. When rare is really rare, which means a probability less than 10ˉ9, naive Monte Carlo becomes unreasonable. A widespread technique consists in multilevel splitting, but this method requires enough knowledge about the system to decide where to put the levels at hand. This is unfortunately not always possible. In this paper, we propose an adaptive algorithm to cope with this problem: the estimation is asymptotically consistent, costs just a little bit more than classical multilevel splitting and has the same efficiency in terms of asymptotic variance. In the one dimensional case, we prove rigorously the a.s. convergence and the asymptotic normality of our estimator, with the same variance as with other algorithms that use fixed crossing levels. In our proofs we mainly use tools from the theory of empirical processes, which seems to be quite new in the field of rare events. // L'estimation de la probabilité d'un événement rare est un problème crucial dans des domaines tels que la fiabilité, les télécommunications, le contrôle aérien. Dans des systèmes complexes, l'étude analytique est hors de portée, et on doit utiliser une méthode de Monte Carlo. Lorsque l'événement est vraiment rare, disons ayant une probabilité plus petite que 10ˉ9, une approche Monte Carlo naïve ne marche pas. Une technique courante consiste à utiliser des niveaux de branchement, mais cette méthode nécessite une connaissance suffisante du système pour choisir où mettre les différents niveaux. Cela n'est malheureusement pas toujours possible. Dans cet article, nous proposons un nouvel algorithme adaptatif pour résoudre ce problème : l'estimateur est asymptotiquement consistant, est juste un peu plus coûteux que la méthode multi-niveaux classique, et a la même efficacité en terme de variance asymptotique. Dans le cas unidimensionnel, nous montrons rigoureusement la convergence presque sûre et la normalité asyptotique de notre estimateur, avec la même variance que les autre algorithmes utilisant des niveaux fixés. Les preuves utilisent des outils issus des processus empiriques, une approche qui semble nouvelle dans le champ des éénements rares.
Document type :
Reports
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00000403
Contributor : Anne Jaigu <>
Submitted on : Thursday, October 6, 2005 - 10:57:01 AM
Last modification on : Wednesday, May 16, 2018 - 11:23:02 AM
Long-term archiving on: : Thursday, April 1, 2010 - 10:39:22 PM

Identifiers

  • HAL Id : inria-00000403, version 1

Citation

Frédéric Cérou, Arnaud Guyader. Adaptive multilevel splitting for rare event analysis. [Research Report] PI 1747, 2005, pp.27. ⟨inria-00000403⟩

Share

Metrics

Record views

411

Files downloads

501