Proving Invariance of Metropolis-Hastings and Gibbs Kernels

Invariance Is Not the Same as Reversibility

In Markov chain Monte Carlo, a transition rule should preserve the distribution it is designed to sample. The precise claim is invariance: if the current state has the target distribution, then the next state has that distribution too. Detailed balance is a stronger, pairwise condition that implies invariance. Metropolis–Hastings is built to satisfy detailed balance, while a Gibbs update can be shown to preserve the target by integrating over a conditional distribution. These arguments also clarify what happens when updates are composed: invariance is preserved by composition, but detailed balance need not be.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), with transition kernel \(K=(K(i,j))\). Each row of \(K\) sums to \(1\). A probability distribution \(\pi=(\pi_i)\), written as a row vector, is invariant for \(K\) if \(\pi K=\pi\). It satisfies detailed balance if \(\pi_iK(i,j)=\pi_jK(j,i)\) for all \(i,j\in S\). Invariance is a property of one-step marginal distributions; it does not assert that the chain has reached the target from every starting state.

The acceptance rule compares the proposed probability flow \(\pi_iq(i,j)\) with the reverse flow \(\pi_jq(j,i)\). Rejection is included in \(K(i,i)\), so the rule defines a probability of staying at the current state as well as probabilities of moving.

Proof. For \(i\ne j\), \(0\le\alpha(i,j)\le1\), so \(K(i,j)\ge0\). Moreover, \(\sum_{j\ne i}q(i,j)\alpha(i,j)\le\sum_{j\ne i}q(i,j)\le1\), making \(K(i,i)\ge0\). By its definition, the row sum of \(K\) is \(1\). To prove detailed balance, first suppose \(q(i,j)>0\) and \(q(j,i)>0\). Then \[ \pi_iK(i,j)=\min\{\pi_iq(i,j),\pi_jq(j,i)\}=\pi_jK(j,i). \] If \(q(i,j)=0\), then \(K(i,j)=0\). If \(q(j,i)>0\), the ratio defining \(\alpha(j,i)\) has zero numerator, so \(K(j,i)=0\) as well. If both proposal probabilities are zero, both off-diagonal kernel entries are zero. Thus detailed balance holds for every distinct pair; for \(i=j\) it is an identity. Finally, for each \(j\), summing detailed balance over \(i\) gives \[ \sum_i\pi_iK(i,j)=\pi_j\sum_iK(j,i)=\pi_j, \] because row \(j\) of \(K\) sums to \(1\). Hence \(\pi K=\pi\). \(\square\)

Gibbs Updates Preserve the Joint Target

A Gibbs update replaces one component of the current state by a draw from its conditional distribution under the target, leaving the other components fixed. The argument below uses a two-component state \(S=\mathcal{X}\times\mathcal{Y}\) with target probability distribution \(\Pi\). Assume conditional distributions \(\Pi(dx\mid y)\) and \(\Pi(dy\mid x)\) are defined for target-almost-every \(y\) and \(x\), respectively. For finite or countable spaces, these are the usual conditional probabilities whenever the conditioning event has positive target probability. Values on conditioning events of target probability zero may be assigned arbitrarily, since they do not affect the invariance calculation.

Proof. Let \(f\) be any bounded measurable function on \(\mathcal{X}\times\mathcal{Y}\). Starting from \((x,y)\), the update \(K_X\) draws \(x'\) from \(\Pi(dx'\mid y)\). Integrating the expected value of \(f\) after the update against the target gives \[ \int \Pi(dx,dy)\int \Pi(dx'\mid y)f(x',y) =\int \Pi_{\mathcal{Y}}(dy)\int \Pi(dx\mid y)\int\Pi(dx'\mid y)f(x',y) =\int \Pi_{\mathcal{Y}}(dy)\int\Pi(dx'\mid y)f(x',y) =\int f(x,y)\Pi(dx,dy). \] The second equality holds because \(\int\Pi(dx\mid y)=1\) for target-almost-every \(y\); the last is the conditional-distribution decomposition of \(\Pi\). Thus the distribution after the update integrates every bounded measurable \(f\) exactly as \(\Pi\) does, so it equals \(\Pi\). For \(K_Y\), the same calculation integrates first over the conditional law of \(y\) given \(x\): the unchanged \(x\) has marginal \(\Pi_{\mathcal{X}}\), and the newly drawn \(y'\) has law \(\Pi(dy'\mid x)\). The resulting joint distribution is again \(\Pi\). \(\square\)

Composing Invariant Updates

Suppose \(K_1\) and \(K_2\) are transition kernels on the same state space and both preserve \(\pi\). Applying \(K_1\) and then \(K_2\) gives the composed kernel \(K_1K_2\), with \((K_1K_2)(i,j)=\sum_kK_1(i,k)K_2(k,j)\) in the countable case. It too preserves \(\pi\): starting with \(\pi\), the first update leaves the distribution at \(\pi\), and the second does the same.

Proof. By associativity of multiplication of probability vectors and kernels, \[ \pi(K_1K_2)=(\pi K_1)K_2=\pi K_2=\pi. \] Applying this identity repeatedly proves the claim for any finite number of updates. No detailed-balance assumption is used. \(\square\)

Which Argument Applies?

For a Metropolis–Hastings kernel, the direct proof is pairwise: compare the target-weighted flow from \(i\) to \(j\) with the reverse flow, then account for rejection on the diagonal. For a Gibbs coordinate update, the direct proof is conditional: under the target, the unchanged coordinates have their target marginal, and the replaced coordinate is drawn from its target conditional distribution. For a composition, invariance follows by applying the invariance identities in update order; do not infer detailed balance merely because the individual kernels are reversible.

Common mistake. A tempting but incorrect argument is: “Each coordinate update is reversible, so their systematic composition is reversible.” The binary example disproves this: its coordinate updates preserve the target, but the one-sweep flows between \(00\) and \(01\) are \(\tfrac1{60}\) and \(\tfrac1{45}\), not equal. The valid conclusion is only that the composition preserves the target. Detailed balance for the composition must be checked separately, and it can fail.