Reversibility of Markov Chains

Reversibility of Markov Chains

Let $(X_n{)}_{n\in \mathbb{N}}$ be an irreducible Markov chain with transition matrix $P$ and invariant distribution ${\pi }^{\ast }$. Run the chain backward by defining $Y_n=X_{N-n}$ for $n=0,\dots ,N$ under a starting distribution $X_0\sim {\pi }^{\ast }$. The reverse transition matrix $\hat{P}$ is defined by
$\hat{P}(x,y)=\frac{{\pi }^{\ast }(y)P(y,x)}{{\pi }^{\ast }(x)},$
which is the unique stochastic matrix making $(Y_n)$ a Markov chain with the same stationary distribution as $(X_n)$.

The chain is reversible with respect to ${\pi }^{\ast }$ if $\hat{P}=P$, i.e., the forward and backward chains are statistically identical. Reversibility is equivalent to the detailed balance equation (DBE):
${\pi }^{\ast }(x)P(x,y)={\pi }^{\ast }(y)P(y,x)\text{for all }x,y\in \mathcal{X}.$

Detailed balance implies stationarity (summing both sides over $x$ gives the balance equation ${\pi }^{\ast }={\pi }^{\ast }P$), but the converse does not hold in general. A chain can be stationary without being reversible; however, if a distribution $\pi$ satisfies the DBE for some $P$, then $\pi$ is automatically the invariant distribution of that $P$. This one-way implication is the workhorse of MCMC: design a transition $P$ that satisfies the DBE with the target $\pi$, and $\pi$ is automatically stationary.

DBE Is a Local Condition local: it equates pairwise flow between any two states. The balance equation ${\pi }^{\ast }={\pi }^{\ast }P$ is global: it equates total flow into and out of each state. Every reversible chain is stationary, but not every stationary chain is reversible. The forward-reverse transformation $\hat{P}(x,y)={\pi }^{\ast }(y)P(y,x)/{\pi }^{\ast }(x)$ always gives a valid reverse chain; reversibility requires the additional identity $\hat{P}=P$.

Detailed balance is

Intuition

“Reversibility” means the movie of the chain looks the same played forward and backward. Imagine watching a chain in stationarity and being shown a video of state transitions: if the chain is reversible, there is no statistical test that distinguishes the video from its time-reversed counterpart. The DBE is the precise condition: the probability flow from $x$ to $y$ in one step, ${\pi }^{\ast }(x)P(x,y)$, exactly matches the flow from $y$ to $x$, ${\pi }^{\ast }(y)P(y,x)$.

The one-way implication “detailed balance $\Rightarrow$ stationarity” is why MCMC algorithms are designed to satisfy the DBE rather than the balance equation directly. Checking pairwise detailed balance is an algebraic identity between $P$ and ${\pi }^{\ast }$ that can be verified (or enforced, as in Metropolis-Hastings’ accept-reject rule) without computing ${\pi }^{\ast }$‘s normalizing constant. Checking the balance equation requires summing over all states of the chain, which is usually intractable when ${\pi }^{\ast }$ is known only up to a constant.

Properties

(DBE $\Rightarrow$ Stationarity) Any distribution satisfying the detailed balance equation with $P$ is automatically invariant for $P$.

Summing the DBE ${\pi }^{\ast }(x)P(x,y)={\pi }^{\ast }(y)P(y,x)$ over $x$ gives
${\sum }_x{\pi }^{\ast }(x)P(x,y)={\pi }^{\ast }(y){\sum }_{x}P(y,x)={\pi }^{\ast }(y),$
since the rows of $P$ sum to $1$. The left-hand side is the $y$-th entry of ${\pi }^{\ast }P$, so ${\pi }^{\ast }P={\pi }^{\ast }$. This is the implication that underwrites MCMC: to sample from ${\pi }^{\ast }$, it suffices to build any irreducible $P$ satisfying the DBE, and ${\pi }^{\ast }$ will be the long-run distribution of the chain regardless of the starting state.

(Stationarity $\nRightarrow$ DBE) A stationary chain need not be reversible.

The balance equation ${\pi }^{\ast }(y)={\sum }_x{\pi }^{\ast }(x)P(x,y)$ equates the total probability flow into and out of $y$ from all states; the DBE equates pairwise flow between each pair. A cyclic chain illustrates the difference: let $\mathcal{X}=\{1,2,3\}$ with $P(1,2)=P(2,3)=P(3,1)=1$ and all other transitions $0$. The uniform distribution ${\pi }^{\ast }=(1/3,1/3,1/3)$ is stationary, but ${\pi }^{\ast }(1)P(1,2)=1/3\ne 0={\pi }^{\ast }(2)P(2,1)$, violating the DBE. Probability flows around the cycle one direction only; played backward the chain looks different, and is therefore not reversible.

(Reverse Chain Always Well-Defined) Every irreducible chain has a reverse chain with the same stationary distribution; reversibility is the special case where it equals the forward chain.

The reverse transition $\hat{P}(x,y)={\pi }^{\ast }(y)P(y,x)/{\pi }^{\ast }(x)$ is a stochastic matrix whenever ${\pi }^{\ast }>0$: its rows sum to $1$ because ${\sum }_y\hat{P}(x,y)={\sum }_y{\pi }^{\ast }(y)P(y,x)/{\pi }^{\ast }(x)={\pi }^{\ast }(x)/{\pi }^{\ast }(x)=1$ using ${\pi }^{\ast }={\pi }^{\ast }P$. The reverse chain has the same stationary distribution ${\pi }^{\ast }$ and the same communicating classes as the forward chain. Reversibility is then the single extra condition $\hat{P}=P$, equivalent to the DBE.

(Metropolis Construction) Any irreducible proposal $Q$ can be turned into a ${\pi }^{\ast }$-reversible chain via the accept-reject rule.

Given any irreducible proposal $Q(x,y)$, define the Metropolis-Hastings transition $P(x,y)=Q(x,y)\alpha (x,y)$ for $y\ne x$, with
$\alpha (x,y)=\min \left(1,\frac{{\pi }^{\ast }(y)Q(y,x)}{{\pi }^{\ast }(x)Q(x,y)}\right).$
This $P$ satisfies the DBE with ${\pi }^{\ast }$ by construction (see MH note’s derivation), so ${\pi }^{\ast }$ is stationary. The entire MCMC toolkit (random-walk Metropolis, Gibbs, MALA, HMC) is built on this reversibility-by-design principle.

(Symmetric $P$ Implies Uniform Is Reversible) If $P(x,y)=P(y,x)$ for all $x,y$, the uniform distribution over $\mathcal{X}$ satisfies the DBE.

Plugging ${\pi }^{\ast }(x)=1/|\mathcal{X}|$ into the DBE gives $P(x,y)=P(y,x)$, which holds by assumption. Symmetric transition matrices arise for random walks on undirected graphs (transition to each neighbor with probability $1/\mathrm{deg}(x)$ is symmetric iff the graph is regular) and for Ising-style models with symmetric flip probabilities. The reverse is also useful: to design a reversible chain with uniform target, make $P$ symmetric.

Examples

Birth-death chain is always reversible

A birth-death chain on $\{0,1,2,\dots \}$ has transitions only to immediate neighbors: $P(n,n+1)=p_n$, $P(n,n-1)=q_n$, $P(n,n)=1-p_n-q_n$, with $p_n+q_n\le 1$ and $q_0=0$. Every such chain with a proper stationary distribution is reversible.

The DBE ${\pi }^{\ast }(n)p_n={\pi }^{\ast }(n+1)q_{n+1}$ gives the recursion
${\pi }^{\ast }(n+1)={\pi }^{\ast }(n)\frac{p_n}{q_{n+1}},$
so
${\pi }^{\ast }(n)={\pi }^{\ast }(0){\prod }_{k=0}^{n-1}\frac{p_k}{q_{k+1}}.$
If ${\sum }_n{\pi }^{\ast }(n)<\infty$, normalize to get the stationary distribution. Because the DBE is the only source of probability flow between adjacent states (there are no jumps skipping neighbors), every birth-death chain that has a stationary distribution is automatically reversible. This is a special structural feature that makes queueing theory computations tractable.

Random walk on a graph

Let $G=(V,E)$ be a finite connected undirected graph and let $(X_n)$ be the simple random walk: from state $x$, move to a uniformly chosen neighbor. The transition probability is $P(x,y)=1/\mathrm{deg}(x)$ if $(x,y)\in E$ and $0$ otherwise.

The DBE becomes ${\pi }^{\ast }(x)/\mathrm{deg}(x)={\pi }^{\ast }(y)/\mathrm{deg}(y)$ whenever $(x,y)\in E$, so ${\pi }^{\ast }(x)\propto \mathrm{deg}(x)$ is a solution. Normalizing,
${\pi }^{\ast }(x)=\frac{\mathrm{deg}(x)}{2|E|},$
using ${\sum }_x\mathrm{deg}(x)=2|E|$. The random walk on an undirected graph is reversible with this degree-proportional stationary distribution, a standard tool in spectral graph theory and Monte Carlo algorithms.

Cyclic chain: stationary but not reversible

Let $\mathcal{X}=\{1,2,3\}$ with deterministic cyclic transitions: $P(1,2)=P(2,3)=P(3,1)=1$. The uniform distribution ${\pi }^{\ast }=(1/3,1/3,1/3)$ is stationary: each state has exactly one state flowing into it (with probability $1/3$) and the total inflow balances the probability $1/3$ of being at that state.

But the DBE fails: ${\pi }^{\ast }(1)P(1,2)=1/3\ne 0={\pi }^{\ast }(2)P(2,1)$. Played backward, probability flows $1\to 3\to 2\to 1$, which is not the forward pattern. Concretely, if you’re shown the sequence $(1,2,3,1,2,3,\dots )$ and asked whether it is forward or backward, you can tell immediately from the direction of the cycle, so the forward and backward chains are statistically distinguishable.

See Also

• 3.11.1 Metropolis-Hastings: uses the DBE to turn any proposal into a ${\pi }^{\ast }$-reversible chain.
• 3.11.2 Gibbs Sampling: each coordinate update is reversible with respect to the target.
• 3.11 MCMC: the central application of reversibility in Bayesian computation.
• 5.3 Distribution of Markov Chains: balance equation and stationary distributions.
• 5.1 Markov Chains: foundational.