A unified perspective on exponential tilt and bridge algorithms for rare trajectories of discrete Markov processes

Abstract

This article analyzes and compares two general techniques of rare event simulation for generating paths of Markov processes over fixed time horizons: exponential tilting and stochastic bridge. These two methods allow to accurately compute the probability that a Markov process ends within a rare region, which is unlikely to be attained. Exponential tilting is a general technique for obtaining an alternative or tilted sampling probability measure, under which the Markov process becomes likely to hit the rare region at terminal time. The stochastic bridge technique involves conditioning paths towards two endpoints: the terminal point and the initial one. The terminal point is generated from some appropriately chosen probability distribution that covers well the rare region. We show that both methods belong to the class of importance sampling procedures, by providing a common mathematical framework of these two conceptually different methods of sampling rare trajectories. We also conduct a numerical comparison of these two methods, revealing distinct areas of application for each Monte Carlo method, where they exhibit superior efficiency. Detailed simulation algorithms are provided.

References in corpus (26)

• Stochastic thermodynamics, fluctuation theorems, and molecular machines
• Dynamic first-order phase transition in kinetically constrained models of glasses
• Forward Flux Sampling for rare event simulations
• First-order dynamical phase transition in models of glasses: an approach based on ensembles of histories
• Large deviations and ensembles of trajectories in stochastic models
• Nonequilibrium microcanonical and canonical ensembles and their equivalence
• A numerical approach to large deviations in continuous-time
• Extinction Rates for Fluctuation-Induced Metastabilities : A Real-Space WKB Approach
• Numerical computation of rare events via large deviation theory
• Making rare events typical in Markovian open quantum systems
• Go with the Winners: a General Monte Carlo Strategy
• The convex hull of the run-and-tumble particle in a plane
• Generating Transition Paths by Langevin Bridges
• Extreme-Value Statistics of Fractional Brownian Motion Bridges
• Time between the maximum and the minimum of a stochastic process
• Building continuous time crystals from rare events
• Convex Hulls of Random Walks: Large-Deviation Properties
• Sampling rare events across dynamical phase transitions
• Fixation in Evolutionary Games under Non-Vanishing Selection
• Practical guide to replica exchange transition interface sampling and forward flux sampling
• Stochastic resetting antiviral therapies prevents drug resistance development
• Efficient characterisation of large deviations using population dynamics
• Gillespie algorithms for stochastic multiagent dynamics in populations and network
• A Deep Learning Functional Estimator of Optimal Dynamics for Sampling Large Deviations
• Joint distributions of partial and global maxima of a Brownian Bridge
• Efficient large deviation estimation based on importance sampling

Cited by in corpus (3)

• Analytic and Monte Carlo Approximations to the Distribution of the First Passage Time of the Drifted Diffusion with Stochastic Resetting and Mixed Boundary Conditions
• Markov-bridge generation of transition paths and its application to cell-fate choice
• The Limits of Inference in Complex Systems: When Stochastic Models Become Indistinguishable