Preserving a Target Distribution
In Markov chain Monte Carlo, a transition rule is useful when it preserves the distribution we want to sample. Preservation is a one-step property: if the current state has the target distribution, then after one transition the next state has that same distribution. Detailed balance is a stronger, pairwise condition that is often convenient to verify. It requires probability flow from one state to another to match the flow in the reverse direction.
Throughout, let \(S\) be a finite or countable state space, and let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Write \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\) for its natural filtration. Its transition kernel is \(K=(K(i,j))_{i,j\in S}\), where \(K(i,j)=\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)\) on the event \(X_n=i\). The Markov property says this conditional probability depends on the past only through \(X_n\). For every \(i\in S\), \(K(i,j)\ge0\) and \(\sum_{j\in S}K(i,j)=1\).
Invariance says that the total probability arriving at \(j\), summed over all possible starting states, equals \(\pi_j\). Detailed balance says more: for each pair \(i,j\), the probability flow from \(i\) to \(j\), when the chain starts with distribution \(\pi\), equals the flow from \(j\) to \(i\). The case \(i=j\) in detailed balance is automatic. The case \(i\ne j\) contains the substantive pairwise restriction.
Why Detailed Balance Guarantees Invariance
Proof. Fix any state \(j\in S\). By detailed balance, \(\pi_iK(i,j)=\pi_jK(j,i)\) for every \(i\). Summing these equalities over \(i\) gives \(\sum_i\pi_iK(i,j)=\sum_i\pi_jK(j,i)=\pi_j\sum_iK(j,i)\). The factor \(\pi_j\) does not depend on \(i\), and the sum \(\sum_iK(j,i)\) is the sum of row \(j\) of the transition kernel. That row sums to \(1\), so \(\sum_i\pi_iK(i,j)=\pi_j\). This is the invariance equation for \(j\); since \(j\) was arbitrary, it holds for every state. All sums have nonnegative terms, so the summation is valid on a countable state space as well. Together with the assumed normalization of \(\pi\), this proves invariance. \(\square\)
The reverse implication does not hold in general: the invariance equation only balances the total flow into each state, while detailed balance balances flow separately for every pair. This distinction is important in MCMC. To establish that a proposed target is preserved, detailed balance is a sufficient check, not a necessary condition.
There is also a direct interpretation of the pairwise condition. If \(X_0\) has distribution \(\pi\), then the joint probability of an adjacent pair is \(\mathbb{P}(X_0=i,X_1=j)=\pi_iK(i,j)\). Thus detailed balance says that this joint probability is unchanged when the two states are interchanged. This adjacent-pair symmetry is the precise sense of reversibility used here.
Proof. For each \(i,j\), the Markov property gives \(\mathbb{P}(X_0=i,X_1=j)=\mathbb{P}(X_0=i)K(i,j)=\pi_iK(i,j)\). Symmetry of the joint distribution means this equals \(\mathbb{P}(X_0=j,X_1=i)=\pi_jK(j,i)\) for every pair \(i,j\), which is exactly detailed balance. Conversely, if detailed balance holds, these two joint probabilities are equal for every pair, so the joint distribution is symmetric. \(\square\)
Invariance also explains the word “preserves.” If \(X_0\) has distribution \(\pi\), then for each \(j\), \(\mathbb{P}(X_1=j)=\sum_i\mathbb{P}(X_0=i)K(i,j)=\sum_i\pi_iK(i,j)=\pi_j\). The same argument can be repeated at every step, so each \(X_n\) has distribution \(\pi\). This assertion concerns the distribution at each time when the chain is initialized from \(\pi\). It does not by itself say that a chain started from another distribution will approach \(\pi\).
Exact Checks on Finite Chains
Worked Example: A Two-State Chain
Let \(S=\{0,1\}\) and take \(K=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac12&\tfrac12\end{bmatrix}\). Find a distribution \(\pi\), then verify both invariance and detailed balance.
First check the transition kernel: row \(0\) sums to \(\tfrac34+\tfrac14=1\), and row \(1\) sums to \(\tfrac12+\tfrac12=1\). Write \(\pi=(x,1-x)\), where \(0\le x\le1\). The probability of being in state \(0\) after one transition is \(x\cdot\tfrac34+(1-x)\cdot\tfrac12\). For invariance this must equal \(x\), so \(x=\tfrac34x+\tfrac12-\tfrac12x=\tfrac14x+\tfrac12\). Therefore \(\tfrac34x=\tfrac12\), and \(x=\tfrac23\). Hence \(\pi=(\tfrac23,\tfrac13)\).
Check invariance. Multiplication using the row-vector convention gives \((\tfrac23,\tfrac13)K=(\tfrac23\cdot\tfrac34+\tfrac13\cdot\tfrac12,\ \tfrac23\cdot\tfrac14+\tfrac13\cdot\tfrac12)\). The first component is \(\tfrac12+\tfrac16=\tfrac23\); the second is \(\tfrac16+\tfrac16=\tfrac13\). Thus \(\pi K=\pi\), and \(\tfrac23+\tfrac13=1\).
Check detailed balance. For the off-diagonal pair, \(\pi_0K(0,1)=\tfrac23\cdot\tfrac14=\tfrac16\), while \(\pi_1K(1,0)=\tfrac13\cdot\tfrac12=\tfrac16\). For the diagonal pairs, both sides are the same expression: \(\pi_0K(0,0)=\pi_0K(0,0)\) and \(\pi_1K(1,1)=\pi_1K(1,1)\). Detailed balance holds for every pair.
The two-state case has a useful general form. If \(K(0,1)=a\) and \(K(1,0)=b\), with \(0\le a,b\le1\), the rows are \((1-a,a)\) and \((b,1-b)\). When \(a+b>0\), detailed balance between the distinct states requires \(\pi_0a=\pi_1b\), and normalization gives \(\pi_0=b/(a+b)\), \(\pi_1=a/(a+b)\). If \(a=b=0\), both states are absorbing and every distribution is invariant and satisfies detailed balance. The example above uses \(a=\tfrac14\), \(b=\tfrac12\), yielding \(\pi_0=(\tfrac12)/(\tfrac14+\tfrac12)=\tfrac23\) and \(\pi_1=(\tfrac14)/(\tfrac14+\tfrac12)=\tfrac13\), as computed directly.
Worked Example: Invariance Without Convergence
Consider the two-state chain that switches state at every step: \(K=\begin{bmatrix}0&1\\1&0\end{bmatrix}\). Each row sums to \(1\). The distribution \(\pi=(\tfrac12,\tfrac12)\) is invariant because \((\tfrac12,\tfrac12)K=(\tfrac12\cdot0+\tfrac12\cdot1,\ \tfrac12\cdot1+\tfrac12\cdot0)=(\tfrac12,\tfrac12)\).
Detailed balance also holds: \(\pi_0K(0,1)=\tfrac12\cdot1=\tfrac12\), and \(\pi_1K(1,0)=\tfrac12\cdot1=\tfrac12\). For each diagonal pair the transition probability is \(0\), so both sides are \(0\). But if the chain starts at state \(0\), its distribution at even times is \((1,0)\) and at odd times is \((0,1)\). These distributions alternate and do not converge. Thus an invariant distribution need not be the limiting distribution from every starting state; invariance alone is not a convergence theorem.
Worked Example: Invariance Without Detailed Balance
Let \(S=\{0,1,2\}\), and let the chain move deterministically around a directed cycle: \(K=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}\). Each row sums to \(1\): the row sums are \(0+1+0=1\), \(0+0+1=1\), and \(1+0+0=1\). Take \(\pi=(\tfrac13,\tfrac13,\tfrac13)\). Then \(\pi K=(\tfrac13\cdot0+\tfrac13\cdot0+\tfrac13\cdot1,\ \tfrac13\cdot1+\tfrac13\cdot0+\tfrac13\cdot0,\ \tfrac13\cdot0+\tfrac13\cdot1+\tfrac13\cdot0)=(\tfrac13,\tfrac13,\tfrac13)\). The entries of \(\pi\) are nonnegative and sum to \(1\), so this is an invariant distribution.
However, for the pair \((0,1)\), \(\pi_0K(0,1)=\tfrac13\cdot1=\tfrac13\), while \(\pi_1K(1,0)=\tfrac13\cdot0=0\). These are unequal, so detailed balance fails. The chain preserves the uniform distribution but has a persistent one-way circulation of probability around the cycle.
A Common Mistake and the MCMC Interpretation
A frequent error is to equate the outgoing flow from a state with the probability assigned to the destination, forgetting the reverse transition probability. In the first example, the incorrect equation \(\pi_0K(0,1)=\pi_1\) would give \(\pi_1=\pi_0/4\). Together with \(\pi_0+\pi_1=1\), this gives the incorrect candidate \((\pi_0,\pi_1)=(\tfrac45,\tfrac15)\). Substitution exposes the error: its probability of moving to state \(0\) is \(\tfrac45\cdot\tfrac34+\tfrac15\cdot\tfrac12=\tfrac35+\tfrac1{10}=\tfrac7{10}\), not \(\tfrac45\). The correct detailed-balance equation includes the reverse transition, \(\pi_0K(0,1)=\pi_1K(1,0)\), giving \(\pi_0/4=\pi_1/2\).
For an MCMC sampler, the intended target is a probability distribution \(\pi\), and the sampler is a transition kernel \(K\). A direct invariance check computes \(\sum_i\pi_iK(i,j)\) for each destination \(j\). A detailed-balance check instead computes \(\pi_iK(i,j)\) and \(\pi_jK(j,i)\) for each pair. The theorem shows why the second check is enough to establish the first, but the directed-cycle example shows why it is not necessary. Neither check alone establishes that samples from an arbitrary initial state converge to the target; that is a separate question requiring additional conditions on the chain.
Check Your Understanding
For each question, distinguish the one-step preservation equation from the pairwise flow condition.
- For \(K=\begin{bmatrix}\tfrac23&\tfrac13\\ \tfrac14&\tfrac34\end{bmatrix}\), find an invariant distribution and check the off-diagonal detailed-balance equation.
- State why detailed balance implies invariance for a countable state space, including the role of the row-sum condition.
- For the directed three-state cycle, identify one pair of states that violates detailed balance and calculate both flows.
- Explain why an invariant distribution does not, by itself, guarantee convergence from a fixed initial state.
- If a two-state chain has \(K(0,1)=K(1,0)=0\), describe all its invariant distributions and say whether they satisfy detailed balance.