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

By Radford M. Neal. 2004

96 citations recorded by the source corpus.

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.

Subfields: Condensed Matter Physics, Materials Chemistry, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/d19570d77da5619e5e724dd4352b25cb63384225

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

1. Jeffrey S. Rosenthal
2. Gareth O. Roberts
3. Andrew Gelman
4. Li Cai
5. C. T. ter Braak
6. Andrew M. Stuart
7. Paul Fearnhead
8. Radford M. Neal

In Materials Chemistry

1. Andrew Gelman
2. Jeffrey S. Rosenthal
3. Gareth O. Roberts

In Statistics and Probability

1. Galin L. Jones
2. Jeffrey S. Rosenthal
3. Gareth O. Roberts
4. Xiao-Li Meng
5. Andrew Gelman
6. Radford M. Neal
7. Steve P. Brooks
8. Jasper A. Vrugt

Citations in the corpus

• Geometric ergodicity of the Bouncy Particle Sampler (2018, background): “In addition, [36] shows that the asymptotic variance of M̃ is always smaller than the one of M.”
• Handbook of Markov Chain Monte Carlo: Hardcover: 619 pages Publisher: Chapman and Hall/CRC Press (first edition, May 2011) Language: English ISBN-10: 1420079417 (2012, background): “Additionally, as noted by Sisson (2005), one does not need to work only with reversible Markov chains, and nonreversible chains may offer opportunities for sampler improvement (Diaconis et al., 2000; Mira and Geyer, 2000; Neal, 2004).”
• General state space Markov chains and MCMC algorithms (2004, background): “Neal [57]), and much of the theory can be applied to this case.”