Efficient Large Deviation Estimation Based on Importance Sampling

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.

• Publication year

  2020

• Venue

  Journal of statistical physics

• Publication date

  2020-03-11

• Fields of study

  Mathematics, Physics

• Identifiers
  DOI 10.1007/s10955-020-02589-xarXiv 2003.05274
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Adaptive multilevel splitting: Historical perspective and recent results.

  2019cited by this paper
• Direct evaluation of dynamical large-deviation rate functions using a variational ansatz.

  2019cited by this paper
• Large Deviations For Performance Analysis

  2019cited by this paper
• On a new class of score functions to estimate tail probabilities of some stochastic processes with adaptive multilevel splitting.

  2018cited by this paper
• On the Asymptotic Normality of Adaptive Multilevel Splitting

  2018cited by this paper
• Rare Event Simulation for Stochastic Dynamics in Continuous Time

  2018cited by this paper
• Experiments in Stochastic Thermodynamics: Short History and Perspectives

  2017cited by this paper
• Aspects of non-equilibrium in classical and quantum systems: Slow relaxation and glasses, dynamical large deviations, quantum non-ergodicity, and open quantum dynamics

  2017cited by this paper
• Introduction to dynamical large deviations of Markov processes

  2017cited by this paper
• Generic dynamical phase transition in one-dimensional bulk-driven lattice gases with exclusion

  2017cited by this paper
• Asymptotic Equivalence of Probability Measures and Stochastic Processes

  2017cited by this paper
• Stochastic thermodynamics: From principles to the cost of precision

  2017cited by this paper
• Rare behavior of growth processes via umbrella sampling of trajectories.

  2017cited by this paper
• Sampling rare fluctuations of discrete-time Markov chains.

  2017cited by this paper
• A minimal model of dynamical phase transition

  2016cited by this paper
• Variational and optimal control representations of conditioned and driven processes

  2015cited by this paper
• Equivalence and Nonequivalence of Ensembles: Thermodynamic, Macrostate, and Measure Levels

  2014cited by this paper
• Large-deviation properties of resilience of power grids

  2014cited by this paper
• Nonequilibrium Markov Processes Conditioned on Large Deviations

  2014cited by this paper
• Macroscopic fluctuation theory

  2014cited by this paper
• Cusp Singularities in Boundary-Driven Diffusive Systems

  2013cited by this paper
• Rare Event Simulation of Small Noise Diffusions

  2012cited by this paper
• Dynamical phase transition for current statistics in a simple driven diffusive system

  2012cited by this paper
• Stochastic thermodynamics, fluctuation theorems and molecular machines

  2012cited by this paper
• Large Deviation Approach to Nonequilibrium Systems

  2011cited by this paper
• Entropy,Large Deviations,and Statistical Mechanics

  2011cited by this paper
• A basic introduction to large deviations: Theory, applications, simulations

  2011cited by this paper
• Large-deviation properties of largest component for random graphs

  2010cited by this paper
• Application of importance sampling to the computation of large deviations in nonequilibrium processes.

  2010cited by this paper
• A multiple replica approach to simulate reactive trajectories.

  2010cited by this paper
• Introduction to Rare Event Simulation

  2010cited by this paper
• Free Energy Computations: A Mathematical Perspective

  2010cited by this paper
• FAST TRACK COMMUNICATION: Current fluctuations in stochastic systems with long-range memory

  2009cited by this paper
• Thermodynamics of quantum jump trajectories.

  2009cited by this paper
• Fluctuations and response of nonequilibrium states.

  2009cited by this paper
• The large deviation approach to statistical mechanics

  2008cited by this paper
• Dynamical first-order phase transition in kinetically constrained models of glasses.

  2007cited by this paper
• Stochastic Simulation: Algorithms and Analysis

  2007cited by this paper
• Stochastic interacting particle systems out of equilibrium

  2007cited by this paper
• Fluctuation theorems for stochastic dynamics

  2007cited by this paper
• Splitting for rare event simulation : A large deviation approach to design and analysis

  2007cited by this paper
• Optimal importance sampling with explicit formulas in continuous time

  2007cited by this paper
• of Statistical Mechanics : Theory and Experiment Non-equilibrium steady states : fluctuations and large deviations of the density and of the current

  2007cited by this paper
• Adaptive Multilevel Splitting for Rare Event Analysis

  2007cited by this paper
• Rare-event Simulation Techniques : An Introduction and Recent Advances

  2006cited by this paper
• Chapter 11 Rare-Event Simulation Techniques: An Introduction and Recent Advances

  2006cited by this paper
• A numerical approach to large deviations in continuous time

  2006cited by this paper
• Large deviations and metastability: Large deviations and statistical mechanics

  2005cited by this paper
• Direct evaluation of large-deviation functions.

  2005cited by this paper
• Energy Landscapes: With Applications to Clusters, Biomolecules and Glasses

  2005cited by this paper
• On asymptotically efficient simulation of large deviation probabilities

  2005influential reference
• The Cross‐Entropy Method

  2004cited by this paper
• Energy Landscapes by David Wales

  2004cited by this paper
• Minimum action method for the study of rare events

  2004cited by this paper
• On Large Deviation Properties of Erdös–Rényi Random Graphs

  2003cited by this paper
• Go with the Winners: a General Monte Carlo Strategy

  2002cited by this paper
• Convex Analysis And Nonlinear Optimization

  2000cited by this paper
• Large Deviation Principles and Complete Equivalence and Nonequivalence Results for Pure and Mixed Ensembles

  2000cited by this paper
• On large-deviation efficiency in statistical inference

  1998cited by this paper
• A Gallavotti–Cohen-Type Symmetry in the Large Deviation Functional for Stochastic Dynamics

  1998cited by this paper
• Analogue studies of nonlinear systems

  1998cited by this paper
• Large Deviations Techniques and Applications

  1998cited by this paper
• On exponential families of Markov processes

  1998cited by this paper
• Fluctuation theorem for stochastic dynamics

  1997cited by this paper
• Counterexamples in importance sampling for large deviations probabilities

  1997cited by this paper
• Large Deviations for Performance Analysis: Queues, Communications, and Computing , Adam Shwartz and Alan Weiss (New York: Chapman and Hall, 1995).

  1996cited by this paper
• Dynamical Ensembles in Nonequilibrium Statistical Mechanics.

  1994cited by this paper
• On the asymptotic efficiency of importance sampling techniques

  1993cited by this paper
• Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains

  1990cited by this paper
• On large deviations theory and asymptotically efficient Monte Carlo estimation

  1989cited by this paper
• Large Deviations Theory Techniques In Monte Carlo Simulation

  1989influential reference
• Noise in nonlinear dynamical systems: Macroscopic potentials, bifurcations and noise in dissipative systems

  1989cited by this paper
• Macroscopic potentials, bifurcations and noise in dissipative systems

  1987influential reference
• RANDOM PERTURBATIONS OF DYNAMICAL SYSTEMS (Grundlehren der mathematischen Wissenschaften, 260)

  1985cited by this paper
• Entropy, large deviations, and statistical mechanics

  1985cited by this paper
• Random Perturbations of Dynamical Systems

  1984cited by this paper
• Large deviations and rare events in the study of stochastic algorithms

  1983cited by this paper
• Multidimensional Diffusion Processes

  1979cited by this paper
• Nonphysical sampling distributions in Monte Carlo free-energy estimation: Umbrella sampling

  1977cited by this paper
• Convex Analysis: (pms-28)

  1970cited by this paper
• LARGE DEVIATIONS THEORY IN EXPONENTIAL FAMILIES

  1968cited by this paper
• Asymptotic probabilities and differential equations

  1966cited by this paper

• Affine invariant interacting Langevin dynamics in Markov chain importance sampling for rare event estimation

  2025cites this paper
• Convergence order of one point large deviations rate functions for backward Euler method of stochastic delay differential equations with small noise

  2024cites this paper
• Unified perspective on exponential tilt and bridge algorithms for rare trajectories of discrete Markov processes.

  2023cites this paper
• Markov Chain transition probability modeling of radon gas records and future projection possibility determination

  2023cites this paper
• Fluctuations of Rare Event Simulation with Monte Carlo Splitting in the Small Noise Asymptotics

  2022cites this paper
• Noise correction of large deviations with anomalous scaling.

  2022cites this paper
• Adaptive power method for estimating large deviations in Markov chains.

  2022cites this paper
• Numerical approximations of one-point large deviations rate functions of stochastic differential equations with small noise

  2021cites this paper
• Stochastic viscosity approximations of Hamilton-Jacobi equations and variance reduction

  2021cites this paper
• Finite Time Large Deviations via Matrix Product States.

  2021cites this paper
• Approximate Optimal Controls via Instanton Expansion for Low Temperature Free Energy Computation

  2020cites this paper