Reversibility in MCMC

Question

I am reading Geyer's lecture notes on MCMC. A condensed version of these notes constitutes Chapter 1 of the Handbook of Markov Chain Monte Carlo (ed. Brooks et al., 2011).

Geyer notes that the composition of valid transition operators is still valid:

It is clear that if an update mechanism $U_1$ preserves a specified distribution, and so does another update mechanism $U_2$, then so does $U_1$ followed by $U_2$, which we will denote $U_1U_2$.

Later on he notes that $U_1U_2$ is in general not reversible, but one could easily build a reversible composite update via a palindromic update, such as $U_1 U_2 U_1$ or $U_1 U_2 U_2 U_1$.

Reversibility is a sufficient condition to prove that a given update leaves the target distribution invariant, and that is why we want elementary updates to be reversible. However, once we prove that, we do not need the composite update to be reversible. (For example, the typical fixed-scan Gibbs sampler is not reversible.)

Is there any theoretical or practical gain in keeping composite updates reversible? My question is general, not only for Gibbs; although I suspect that the effect of ordering of operators might have been studied the most in the case of Gibbs sampling.

In practice, I am currently building MCMC updates by composing a number of elementary operators of various kind (see also this question). I could combine the operators in a palindromic way -- would that matter?

PS: I am aware that probabilistic mixtures of operators are valid and reversible, but here I am interested in composition.

Answer 1

I am interpreting your question as much more general in that "Is there any gain to using a reversible Markov chain over a non-reversible Markov chain?". Here are two reasons I can think of off the top of my head:

1. Standard errors: If the chain is reversible, then a Markov chain CLT can hold for geometrically ergodic Markov chains while assuming only a finite second moment. If the chain is not reversible, then you have to assume $2 + \delta$ for $\delta > 0$ finite moments. So if you are estimating the posterior mean, and have only two finite moments available, then only a nonreversible Markov chain might not allow analysis of standard errors. You can find more information here.

2. Spectral Gap: Often analysis of the convergence rates of MCMC samplers is done by looking at the spectral gap of the Markov chain. For a reversible Markov chain, the second largest eigenvalue determines the mixing time, and there are many known bounds for this. Maybe see a review here. So if your Markov chain is reversible, it is likely easier to study its convergence rates. There is also some work that has been done for non-reversible Markov chains (see this), but the literature is not as rich. This is some more discussion on this in Mathoverflow.

Overall, if you don't have a need to study the exact convergence rate for your sampler, and your distribution is well behaved enough that it has larger than 2 moments for most functions of interest, then there should be no reason to restrict yourself to just reversible Markov chains. This is part of the reason why fixed-scan Gibbs sampler are so often used; in practice nothing is lost.