The parallel replica method for simulating long trajectories of Markov chains

DOI10.1093/AMRX/ABU005MaRDI QIDQ2927899zbMATH OpenOpenAlexFDO

Authors David Aristoff, Tony Lelièvre, Gideon Simpson

Publication date 5 November 2014

Published in AMRX. Applied Mathematics Research eXpress (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.4500

zbMATH Keywords

algorithmalgorithm simulating Markov chainsdecorrelation stepdephasing stepmetastable statesnumerical exampleparallel replica dynamicsparallel step

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40)

Abstract: The parallel replica dynamics, originally developed by A.F. Voter, efficiently simulates very long trajectories of metastable Langevin dynamics. We present an analogous algorithm for discrete time Markov processes. Such Markov processes naturally arise, for example, from the time discretization of a continuous time stochastic dynamics. Appealing to properties of quasistationary distributions, we show that our algorithm reproduces exactly (in some limiting regime) the law of the original trajectory, coarsened over the metastable states.

Review text

The authors consider the problem of simulating, in an efficient way, time-homogeneous Markov chains with subsets of states in which the Markov chain stays for a long time. Those states are the so-called metastable states. The authors present an algorithm which is an adaptation of the parallel replica (ParRep) dynamics generally used to simulate metastable processes. Their version is used in the discrete time setting, but it can be applied to any Markov chain. In order to describe the proposed algorithm, some basic definitions are given as well as the setting of some notation. After the statement of the preliminary information, the discrete time ParRep algorithm is described. This is performed in three steps: the decorrelation step, the dephasing step, and finally, the parallel step. A mathematical analysis of some properties of the discrete ParRep algorithm is also performed. Among them is the analysis of the properties of the quasi-stationary distributions, including conditions for their existence and uniqueness. Examples illustrating the use of the algorithm are given towards the end of the work as well as a discussion of the algorithm's performance.

Recommendations

• The parallel replica method for computing equilibrium averages of Markov chains
• Stationary Averaging for Multiscale Continuous Time Markov Chains Using Parallel Replica Dynamics
• A generalized parallel replica dynamics
• A mathematical formalization of the parallel replica dynamics
• Numerical analysis of parallel replica dynamics

Cited in

(9)

• Shaken dynamics: an easy way to parallel Markov chain Monte Carlo
• A mathematical formalization of the parallel replica dynamics
• Stationary Averaging for Multiscale Continuous Time Markov Chains Using Parallel Replica Dynamics
• Efficient simulation of Markov chains using segmentation
• Generalizing Parallel Replica Dynamics: Trajectory Fragments, Asynchronous Computing, and PDMPs
• Numerical analysis of parallel replica dynamics
• The enhanced sampling in parallel finite-time dynamics method with replica exchange
• A generalized parallel replica dynamics
• The parallel replica method for computing equilibrium averages of Markov chains

This page was built for publication: The parallel replica method for simulating long trajectories of Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2927899)