NIPS Proceedingsβ

Improving the Asymptotic Performance of Markov Chain Monte-Carlo by Inserting Vortices

Part of: Advances in Neural Information Processing Systems 23 (NIPS 2010)

[PDF] [BibTeX]



We present a new way of converting a reversible finite Markov chain into a nonreversible one, with a theoretical guarantee that the asymptotic variance of the MCMC estimator based on the non-reversible chain is reduced. The method is applicable to any reversible chain whose states are not connected through a tree, and can be interpreted graphically as inserting vortices into the state transition graph. Our result confirms that non-reversible chains are fundamentally better than reversible ones in terms of asymptotic performance, and suggests interesting directions for further improving MCMC.