Improving Asymptotic Variance of MCMC Estimators: Non-reversible Chains are Better

Abstract

I show how any reversible Markov chain on a finite state space that is irreducible, and hence suitable for estimating expectations with respect to its invariant distribution, can be used to construct a non-reversible Markov chain on a related state space that can also be used to estimate these expectations, with asymptotic variance at least as small as that using the reversible chain (typically smaller). The non-reversible chain achieves this improvement by avoiding (to the extent possible) transitions that backtrack to the state from which the chain just came. The proof that this modification cannot increase the asymptotic variance of an MCMC estimator uses a new technique that can also be used to prove Peskun's (1973) theorem that modifying a reversible chain to reduce the probability of staying in the same state cannot increase asymptotic variance. A non-reversible chain that avoids backtracking will often take little or no more computation time per transition than the original reversible chain, and can sometime produce a large reduction in asymptotic variance, though for other chains the improvement is slight. In addition to being of some practical interest, this construction demonstrates that non-reversible chains have a fundamental advantage over reversible chains for MCMC estimation. Research into better MCMC methods may therefore best be focused on non-reversible chains.

Cited by in corpus (16)

• General state space Markov chains and MCMC algorithms
• Variance Reduction using Nonreversible Langevin Samplers
• Improving the convergence of reversible samplers
• Modified Hamiltonian Monte Carlo for Bayesian inference
• Reversible jump Markov chain Monte Carlo and multi-model samplers
• Some things we've learned (about Markov chain Monte Carlo)
• Improving the Asymptotic Performance of Markov Chain Monte-Carlo by Inserting Vortices
• Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling
• Peskun-Tierney ordering for Markov chain and process Monte Carlo: beyond the reversible scenario
• Geometric Methods for Sampling, Optimisation, Inference and Adaptive Agents
• Quantifying the accuracy of approximate diffusions and Markov chains
• Estimating the Mixing Time of Ergodic Markov Chains
• Non-reversible Markov chain Monte Carlo for sampling of districting maps
• Symmetry-Aware Marginal Density Estimation
• Analysis of high-dimensional Continuous Time Markov Chains using the Local Bouncy Particle Sampler
• Bounds on Lifting Continuous Markov Chains to Speed Up Mixing