Efficient large deviation estimation based on importance sampling

Abstract

We present a complete framework for determining the asymptotic (or logarithmic) efficiency of estimators of large deviation probabilities and rate functions based on importance sampling. The framework relies on the idea that importance sampling in that context is fully characterized by the joint large deviations of two random variables: the observable defining the large deviation probability of interest and the likelihood factor (or Radon-Nikodym derivative) connecting the original process and the modified process used in importance sampling. We recover with this framework known results about the asymptotic efficiency of the exponential tilting and obtain new necessary and sufficient conditions for a general change of process to be asymptotically efficient. This allows us to construct new examples of efficient estimators for sample means of random variables that do not have the exponential tilting form. Other examples involving Markov chains and diffusions are presented to illustrate our results.

v1: 34 pages, 8 figures; v2: Typos corrected; v3: More mathematical version containing technical modifications in Assumption 2, Assumption 3, and Eq. (53) needed in some of the proofs

References in corpus (14)

• The large deviation approach to statistical mechanics
• Non equilibrium steady states: fluctuations and large deviations of the density and of the current
• Dynamic first-order phase transition in kinetically constrained models of glasses
• Fluctuation theorems for stochastic dynamics
• Fluctuations and response of nonequilibrium states
• A numerical approach to large deviations in continuous-time
• Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels
• A minimal model of dynamical phase transition
• Current fluctuations in stochastic systems with long-range memory
• Large-deviation properties of resilience of power grids
• Direct evaluation of dynamical large-deviation rate functions using a variational ansatz
• Application of importance sampling to the computation of large deviations in non-equilibrium processes
• On a new class of score functions to estimate tail probabilities of some stochastic processes with Adaptive Multilevel Splitting
• Rare event simulation for stochastic dynamics in continuous time

Cited by in corpus (5)

• Finite time large deviations via matrix product states
• Optimal sampling of dynamical large deviations via matrix product states
• Noise correction of large deviations with anomalous scaling
• Adaptive power method for estimating large deviations in Markov chains
• A unified perspective on exponential tilt and bridge algorithms for rare trajectories of discrete Markov processes