Limit theorems for cloning algorithms
arXiv:1902.00509 · doi:10.1016/j.spa.2021.04.007
Abstract
Large deviations for additive path functionals of stochastic processes have attracted significant research interest, in particular in the context of stochastic particle systems and statistical physics. Efficient numerical `cloning' algorithms have been developed to estimate the scaled cumulant generating function, based on importance sampling via cloning of rare event trajectories. So far, attempts to study the convergence properties of these algorithms in continuous time have only led to partial results for particular cases. Adapting previous results from the literature of particle filters and sequential Monte Carlo methods, we establish a first comprehensive and fully rigorous approach to bound systematic and random errors of cloning algorithms in continuous time. To this end we develop a method to compare different algorithms for particular classes of observables, based on the martingale characterization of stochastic processes. Our results apply to a large class of jump processes on compact state space, and do not involve any time discretization in contrast to previous approaches. This provides a robust and rigorous framework that can also be used to evaluate and improve the efficiency of algorithms.
arXiv comment42 pages
References in corpus (24)
- MCMC using Hamiltonian dynamics
- Dynamic first-order phase transition in kinetically constrained models of glasses
- Direct evaluation of large-deviation functions
- Nonequilibrium Markov processes conditioned on large deviations
- Space-time Thermodynamics of the Glass Transition
- Computation of extreme heat waves in climate models using a large deviation algorithm
- Simulating rare events in dynamical processes
- A numerical approach to large deviations in continuous-time
- The Continuous Time Random Walk, still trendy: Fifty-year history, state of art, and outlook
- Population dynamics method with a multi-canonical feedback control
- Optimizing active work: Dynamical phase transitions, collective motion, and jamming
- Go with the Winners: a General Monte Carlo Strategy
- Thermodynamics of currents in nonequilibrium diffusive systems: theory and simulation
- Test of the Additivity Principle for Current Fluctuations in a Model of Heat Conduction
- Dynamic transition in an atomic glass former: a molecular dynamics evidence
- Sampling rare events across dynamical phase transitions
- Finite-time and finite-size scalings in the evaluation of large-deviation functions: Analytical study using a birth-death process
- Finite-Time and -Size Scalings in the Evaluation of Large Deviation Functions: Numerical Approach in Continuous Time
- Efficient characterisation of large deviations using population dynamics
- Numerical study of extreme mechanical force exerted by a turbulent flow on a bluff body by direct and rare-event sampling techniques
- Current large deviations for partially asymmetric particle systems on a ring
- Rare event simulation for stochastic dynamics in continuous time
- On the concentration properties of Interacting particle processes
- A Central Limit Theorem for Fleming-Viot Particle Systems with Soft Killing