On synchronized Fleming–Viot particle systems
Authors:
Frédéric Cérou, Arnaud Guyader and Mathias Rousset
Journal:
Theor. Probability and Math. Statist. 102 (2020), 45-71
MSC (2020):
Primary 82C22, 82M60, 65C05; Secondary 60K35, 60K37
DOI:
https://doi.org/10.1090/tpms/1127
Published electronically:
March 29, 2021
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: This article presents a variant of Fleming–Viot particle systems, which are a standard way to approximate the law of a Markov process with killing as well as related quantities. Classical Fleming–Viot particle systems proceed by simulating $N$ trajectories, or particles, according to the dynamics of the underlying process, until one of them is killed. At this killing time, the particle is instantaneously branched on one of the $(N-1)$ other ones, and so on until a fixed and finite final time $T$. In our variant, we propose to wait until $K$ particles are killed and then rebranch them independently on the $(N-K)$ alive ones. Specifically, we focus our attention on the large population limit and the regime where $K/N$ has a given limit when $N$ goes to infinity. In this context, we establish consistency and asymptotic normality results. The variant we propose is motivated by applications in rare event estimation problems through its connection with Adaptive Multilevel Splitting and Subset Simulation.
References
- S.K. Au and J.L. Beck, Estimation of small failure probabilities in high dimensions by subset simulation, Probabilistic Engineering Mechanics 16 (2001), no. 4, 263–277.
- ---, Subset simulation and its application to seismic risk based on dynamic analysis, Journal of Engineering Mechanics 129 (2003), no. 8, 901–917.
- Mariusz Bieniek, Krzysztof Burdzy, and Sam Finch, Non-extinction of a Fleming-Viot particle model, Probab. Theory Related Fields 153 (2012), no. 1-2, 293–332. MR 2925576, DOI https://doi.org/10.1007/s00440-011-0372-5
- Charles-Edouard Bréhier and Tony Lelièvre, On a new class of score functions to estimate tail probabilities of some stochastic processes with adaptive multilevel splitting, Chaos 29 (2019), no. 3, 033126, 13. MR 3924366, DOI https://doi.org/10.1063/1.5081440
- K. Burdzy, R. Holyst, D. Ingerman, and P. March, Configurational transition in a Fleming-Viot-type model and probabilistic interpretation of Laplacian eigenfunctions, Journal of Physics A: Mathematical and General 29 (1996), no. 11, 2633.
- F. Cérou, P. Del Moral, T. Furon, and A. Guyader, Sequential Monte Carlo for rare event estimation, Stat. Comput. 22 (2012), no. 3, 795–808. MR 2909622, DOI https://doi.org/10.1007/s11222-011-9231-6
- Frédéric Cérou, Bernard Delyon, Arnaud Guyader, and Mathias Rousset, A central limit theorem for Fleming-Viot particle systems, Ann. Inst. Henri Poincaré Probab. Stat. 56 (2020), no. 1, 637–666 (English, with English and French summaries). MR 4059003, DOI https://doi.org/10.1214/19-AIHP976
- Frédéric Cérou, Bernard Delyon, Arnaud Guyader, and Mathias Rousset, On the asymptotic normality of adaptive multilevel splitting, SIAM/ASA J. Uncertain. Quantif. 7 (2019), no. 1, 1–30. MR 3895126, DOI https://doi.org/10.1137/18M1187477
- Frédéric Cérou, Bernard Delyon, Arnaud Guyader, and Mathias Rousset, A central limit theorem for Fleming-Viot particle systems, Ann. Inst. Henri Poincaré Probab. Stat. 56 (2020), no. 1, 637–666 (English, with English and French summaries). MR 4059003, DOI https://doi.org/10.1214/19-AIHP976
- F. Cérou, T. Furon, and A. Guyader, Experimental assessment of the reliability for watermarking and fingerprinting schemes, EURASIP J. Inf. Secur. 2008 (2008), 6:1–6:12.
- Frédéric Cérou and Arnaud Guyader, Adaptive multilevel splitting for rare event analysis, Stoch. Anal. Appl. 25 (2007), no. 2, 417–443. MR 2303095, DOI https://doi.org/10.1080/07362990601139628
- Frédéric Cérou and Arnaud Guyader, Fluctuation analysis of adaptive multilevel splitting, Ann. Appl. Probab. 26 (2016), no. 6, 3319–3380. MR 3582805, DOI https://doi.org/10.1214/16-AAP1177
- F. Cérou, A. Guyader, T. Lelièvre, and D. Pommier, A Multiple Replica Approach to Simulate Reactive Trajectories, The Journal of Chemical Physics 134 (2011), no. 5, 054108.
- Frédéric Cérou, Arnaud Guyader, and Mathias Rousset, Adaptive multilevel splitting: historical perspective and recent results, Chaos 29 (2019), no. 4, 043108, 12. MR 3937660, DOI https://doi.org/10.1063/1.5082247
- Pierre Del Moral, Feynman-Kac formulae, Probability and its Applications (New York), Springer-Verlag, New York, 2004. Genealogical and interacting particle systems with applications. MR 2044973
- ---, Mean field simulation for Monte Carlo integration, CRC Press, 2013.
- Stewart N. Ethier and Thomas G. Kurtz, Markov processes, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1986. Characterization and convergence. MR 838085
- Ilie Grigorescu and Min Kang, Hydrodynamic limit for a Fleming-Viot type system, Stochastic Process. Appl. 110 (2004), no. 1, 111–143. MR 2052139, DOI https://doi.org/10.1016/j.spa.2003.10.010
- Ilie Grigorescu and Min Kang, Immortal particle for a catalytic branching process, Probab. Theory Related Fields 153 (2012), no. 1-2, 333–361. MR 2925577, DOI https://doi.org/10.1007/s00440-011-0347-6
- Arnaud Guyader, Nicholas Hengartner, and Eric Matzner-Løber, Simulation and estimation of extreme quantiles and extreme probabilities, Appl. Math. Optim. 64 (2011), no. 2, 171–196. MR 2822407, DOI https://doi.org/10.1007/s00245-011-9135-z
- Jean Jacod and Albert N. Shiryaev, Limit theorems for stochastic processes, 2nd ed., Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 288, Springer-Verlag, Berlin, 2003. MR 1943877
- Thibault Lestang, Francesco Ragone, Charles-Edouard Bréhier, Corentin Herbert, and Freddy Bouchet, Computing return times or return periods with rare event algorithms, J. Stat. Mech. Theory Exp. 4 (2018), 043213, 33. MR 3801965, DOI https://doi.org/10.1088/1742-5468/aab856
- Jörg-Uwe Löbus, A stationary Fleming-Viot type Brownian particle system, Math. Z. 263 (2009), no. 3, 541–581. MR 2545857, DOI https://doi.org/10.1007/s00209-008-0430-6
- L.J.S. Lopes, C.G. Mayne, C. Chipot, and T. Lelièvre, Adaptive Multilevel Splitting Method: Isomerization of the alanine dipeptide, arXiv preprint arXiv:1707.00950 (2017).
- Philip E. Protter, Stochastic integration and differential equations, 2nd ed., Applications of Mathematics (New York), vol. 21, Springer-Verlag, Berlin, 2004. Stochastic Modelling and Applied Probability. MR 2020294
- I. Teo, C.G. Mayne, K. Schulten, and T. Lelièvre, Adaptive multilevel splitting method for molecular dynamics calculation of benzamidine-trypsin dissociation time, Journal of chemical theory and computation 12 (2016), no. 6, 2983–2989.
- Denis Villemonais, General approximation method for the distribution of Markov processes conditioned not to be killed, ESAIM Probab. Stat. 18 (2014), 441–467. MR 3333998, DOI https://doi.org/10.1051/ps/2013045
References
- S.K. Au and J.L. Beck, Estimation of small failure probabilities in high dimensions by subset simulation, Probabilistic Engineering Mechanics 16 (2001), no. 4, 263–277.
- ---, Subset simulation and its application to seismic risk based on dynamic analysis, Journal of Engineering Mechanics 129 (2003), no. 8, 901–917.
- M. Bieniek, K. Burdzy, and S. Finch, Non-extinction of a Fleming-Viot particle model, Probab. Theory Related Fields 153 (2012), no. 1-2, 293–332. MR 2925576
- C.-E. Bréhier and T. Lelièvre, On a new class of score functions to estimate tail probabilities of some stochastic processes with adaptive multilevel splitting, Chaos 29 (2019), no. 3, 033126, 13. MR 3924366
- K. Burdzy, R. Holyst, D. Ingerman, and P. March, Configurational transition in a Fleming-Viot-type model and probabilistic interpretation of Laplacian eigenfunctions, Journal of Physics A: Mathematical and General 29 (1996), no. 11, 2633.
- F. Cérou, P. Del Moral, T. Furon, and A. Guyader, Sequential Monte Carlo for Rare Event Estimation, Stat. Comput. 22 (2012), no. 3, 795–808. MR 2909622
- F. Cérou, B. Delyon, A. Guyader, and M. Rousset, A Central Limit Theorem for Fleming-Viot Particle Systems with Soft Killing, arXiv preprint arXiv:1611.00515 (2016). MR 4059003
- F. Cérou, B. Delyon, A. Guyader, and M. Rousset, On the Asymptotic Normality of Adaptive Multilevel Splitting, SIAM/ASA J. Uncertain. Quantif. 7 (2019), no. 1, 1–30. MR 3895126
- ---, A central limit theorem for Fleming–Viot particle systems, Ann. Inst. Henri Poincaré Probab. Stat. 56 (2020), no. 1, 637–666. MR 4059003
- F. Cérou, T. Furon, and A. Guyader, Experimental assessment of the reliability for watermarking and fingerprinting schemes, EURASIP J. Inf. Secur. 2008 (2008), 6:1–6:12.
- F. Cérou and A. Guyader, Adaptive Multilevel Splitting for Rare Event Analysis, Stoch. Anal. Appl. 25 (2007), no. 2, 417–443. MR 2303095
- F. Cérou and A. Guyader, Fluctuation Analysis of Adaptive Multilevel Splitting, Ann. Appl. Probab. 26 (2016), no. 6, 3319–3380. MR 3582805
- F. Cérou, A. Guyader, T. Lelièvre, and D. Pommier, A Multiple Replica Approach to Simulate Reactive Trajectories, The Journal of Chemical Physics 134 (2011), no. 5, 054108.
- F. Cérou, A. Guyader, and M. Rousset, Adaptive Multilevel Splitting: Historical Perspective and Recent Results, Chaos 29 (2019), no. 4, 043108, 12. MR 3937660
- P. Del Moral, Feynman-Kac formulae, genealogical and interacting particle systems with applications, Springer-Verlag, New York, 2004. MR 2044973
- ---, Mean field simulation for Monte Carlo integration, CRC Press, 2013.
- S.N. Ethier and T.G. Kurtz, Markov processes, John Wiley & Sons, Inc., New York, 1986. MR 838085
- I. Grigorescu and M. Kang, Hydrodynamic limit for a Fleming-Viot type system, Stochastic Process. Appl. 110 (2004), no. 1, 111–143. MR 2052139
- ---, Immortal particle for a catalytic branching process, Probab. Theory Related Fields 153 (2012), no. 1-2, 333–361. MR 2925577
- A. Guyader, N. Hengartner, and E. Matzner-Løber, Simulation and estimation of extreme quantiles and extreme probabilities, Applied Mathematics and Optimization 64 (2011), 171–196. MR 2822407
- J. Jacod and A.N. Shiryaev, Limit theorems for stochastic processes, second ed., vol. 288, Springer-Verlag, Berlin, 2003. MR 1943877
- T. Lestang, F. Ragone, C.-E. Bréhier, C. Herbert, and F. Bouchet, Computing return times or return periods with rare event algorithms, Journal of Statistical Mechanics: Theory and Experiment 2018 (2018), no. 4, 043213. MR 3801965
- J.-U. Löbus, A stationary Fleming-Viot type Brownian particle system, Math. Z. 263 (2009), no. 3, 541–581. MR 2545857
- L.J.S. Lopes, C.G. Mayne, C. Chipot, and T. Lelièvre, Adaptive Multilevel Splitting Method: Isomerization of the alanine dipeptide, arXiv preprint arXiv:1707.00950 (2017).
- P.E. Protter, Stochastic integration and differential equations, Springer-Verlag, Berlin, 2005. MR 2020294
- I. Teo, C.G. Mayne, K. Schulten, and T. Lelièvre, Adaptive multilevel splitting method for molecular dynamics calculation of benzamidine-trypsin dissociation time, Journal of chemical theory and computation 12 (2016), no. 6, 2983–2989.
- D. Villemonais, General approximation method for the distribution of Markov processes conditioned not to be killed, ESAIM Probab. Stat. 18 (2014), 441–467. MR 3333998
Similar Articles
Retrieve articles in Theory of Probability and Mathematical Statistics
with MSC (2020):
82C22,
82M60,
65C05,
60K35,
60K37
Retrieve articles in all journals
with MSC (2020):
82C22,
82M60,
65C05,
60K35,
60K37
Additional Information
Frédéric Cérou
Affiliation:
INRIA–Rennes & Université de Rennes, CNRS, IRMAR - UMR 6625, F-35000 Rennes, France
Email:
frederic.cerou@inria.fr
Arnaud Guyader
Affiliation:
LPSM, Sorbonne Université, 75005 Paris, France, and CERMICS, École des Ponts ParisTech, 77455 Marne la Vallée, France
Email:
arnaud.guyader@upmc.fr
Mathias Rousset
Affiliation:
INRIA–Rennes & Université de Rennes, CNRS, IRMAR - UMR 6625, F-35000 Rennes, France
Email:
mathias.rousset@inria.fr
Keywords:
Sequential Monte Carlo,
interacting particle systems,
process with killing.
Received by editor(s):
November 12, 2019
Published electronically:
March 29, 2021
Article copyright:
© Copyright 2020
Taras Shevchenko National University of Kyiv