Lifting—A nonreversible Markov chain Monte Carlo algorithm
- 1 December 2016
- journal article
- Published by American Association of Physics Teachers (AAPT) in American Journal of Physics
- Vol. 84 (12), 958-968
- https://doi.org/10.1119/1.4961596
Abstract
Markov chain Monte Carlo algorithms are invaluable tools for exploring stationary properties of physical systems, especially in situations where direct sampling is unfeasible. Common implementations of Monte Carlo algorithms employ reversible Markov chains. Reversible chains obey detailed balance and thus ensure that the system will eventually relax to equilibrium, though detailed balance is not necessary for convergence to equilibrium. We review nonreversible Markov chains, which violate detailed balance and yet still relax to a given target stationary distribution. In particular cases, nonreversible Markov chains are substantially better at sampling than the conventional reversible Markov chains with up to a square root improvement in the convergence time to the steady state. One kind of nonreversible Markov chain is constructed from the reversible ones by enlarging the state space and by modifying and adding extra transition rates to create non-reversible moves. Because of the augmentation of the state space, such chains are often referred to as lifted Markov Chains. We illustrate the use of lifted Markov chains for efficient sampling on several examples. The examples include sampling on a ring, sampling on a torus, the Ising model on a complete graph, and the one-dimensional Ising model. We also provide a pseudocode implementation, review related work, and discuss the applicability of such methods.Keywords
This publication has 19 references indexed in Scilit:
- Violation of detailed balance accelerates relaxationPhysical Review E, 2013
- Optimal Non-reversible Linear Drift for the Convergence to Equilibrium of a DiffusionJournal of Statistical Physics, 2013
- Addendum to “Event-chain Monte Carlo algorithms for hard-sphere systems”Physical Review E, 2012
- Non-reversible Monte Carlo simulations of spin modelsComputer Physics Communications, 2011
- Irreversible Monte Carlo algorithms for efficient samplingPhysica D: Nonlinear Phenomena, 2011
- Markov Chain Monte Carlo Method without Detailed BalancePhysical Review Letters, 2010
- Nonequilibrium stationary states and phase transitions in directed Ising modelsJournal of Statistical Mechanics: Theory and Experiment, 2009
- Event-chain Monte Carlo algorithms for hard-sphere systemsPhysical Review E, 2009
- Analysis of a nonreversible Markov chain samplerThe Annals of Applied Probability, 2000
- Monte Carlo sampling methods using Markov chains and their applicationsBiometrika, 1970