Limit theorems for cloning algorithms

Letizia Angeli, Stefan Grosskinsky, Adam M. Johansen

Research output: Contribution to journalArticlepeer-review

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 led to only 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.

Original languageEnglish
Pages (from-to)117-152
Number of pages36
JournalStochastic Processes and their Applications
Volume138
Early online date22 Apr 2021
DOIs
Publication statusE-pub ahead of print - 22 Apr 2021

Keywords

  • Cloning algorithm
  • Dynamic large deviations
  • Feynman–Kac formulae
  • Interacting particle systems
  • Jump processes
  • L convergence

ASJC Scopus subject areas

  • Statistics and Probability
  • Modelling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Limit theorems for cloning algorithms'. Together they form a unique fingerprint.

Cite this