Coupling Bounds for Finite-State MCMC

Why Couple Two Chains?

To assess convergence of a finite-state Markov chain, one can compare its distribution at time $n$ with a stationary distribution. A coupling makes this comparison concrete: construct two chains on the same probability space, one starting from the state of interest and one starting in stationarity, and arrange their transitions so they sometimes meet. If they have met and thereafter use identical transitions, they remain equal. Thus the chance that they have not met by time $n$ bounds the difference between their distributions at that time.

Let $(X_n)_{n\ge0}$ be a Markov chain on a finite state space $S$, with transition matrix $P=(p_{ij})$, where each row sums to $1$. Write $P^{(n)}=P^n$, and let $\mu P^{(n)}$ denote the distribution at time $n$ when the initial distribution is the row vector $\mu$. A stationary distribution is a row vector $\pi$ satisfying $\pi P=\pi$. The chain need not be irreducible for the coupling inequalities below, but a stationary distribution must be specified when comparing to stationarity.

Definition: For probability distributions $\mu$ and $\nu$ on finite $S$, their total variation distance is $$ \|\mu-\nu\|_{\mathrm{TV}}=\frac12\sum_{z\in S}|\mu(z)-\nu(z)|. $$ A coupling of $\mu$ and $\nu$ is a pair of random variables $(U,V)$ on one probability space whose marginal distributions are $\mu$ and $\nu$. A coupling of two chains is a joint construction whose two coordinate processes each have the specified chain as their marginal process.

The equivalent set-based expression is $\|\mu-\nu\|_{\mathrm{TV}}=\sup_{A\subseteq S}|\mu(A)-\nu(A)|$. To see this, put $d(z)=\mu(z)-\nu(z)$; then $\sum_z d(z)=0$. The sum of the positive $d(z)$'s equals half the sum of their absolute values. Choosing $A=\{z:d(z)>0\}$ attains that value, and no other set can have a larger absolute sum.

Theorem (Coupling inequality): If $(U,V)$ is any coupling of distributions $\mu,\nu$ on finite $S$, then $$ \|\mu-\nu\|_{\mathrm{TV}}\le \mathbb{P}(U\ne V). $$

Proof. Fix any subset $A\subseteq S$. The indicators $\mathbf{1}_{\{U\in A\}}$ and $\mathbf{1}_{\{V\in A\}}$ can differ only on the event $\{U\ne V\}$. Therefore $$ |\mu(A)-\nu(A)|=\left|\mathbb{E}\left[\mathbf{1}_{\{U\in A\}}-\mathbf{1}_{\{V\in A\}}\right]\right| \le \mathbb{P}(U\ne V). $$ Taking the supremum over $A$ and using the set-based expression proves the inequality. $\square$

Worked Example: Coupling Two Distributions by Their Common Mass

On $S=\{a,b,c\}$, let $\mu=(\tfrac12,\tfrac13,\tfrac16)$ and $\nu=(\tfrac13,\tfrac13,\tfrac13)$, in the displayed state order. Construct a coupling and calculate its probability of disagreement.

At each state $z$, the mass that can be assigned to $U=V=z$ is at most both $\mu(z)$ and $\nu(z)$. Take the common masses to be their coordinatewise minima: $$ \min(\mu,\nu)=\left(\tfrac13,\tfrac13,\tfrac16\right), \qquad c=\tfrac13+\tfrac13+\tfrac16=\tfrac56. $$ With probability $\tfrac56$, choose $U=V$ with probabilities proportional to these common masses. The resulting diagonal probabilities are $(\tfrac13,\tfrac13,\tfrac16)$. The remaining mass of $\mu$ is $\tfrac16$ at $a$, while the remaining mass of $\nu$ is $\tfrac16$ at $c$; assign the remaining probability to $(U,V)=(a,c)$. This gives the stated marginals and disagreement probability $\tfrac16$.

Check: the first marginal has mass $\tfrac13+\tfrac16=\tfrac12$ at $a$, $\tfrac13$ at $b$, and $\tfrac16$ at $c$. The second has $\tfrac13$ at $a$, $\tfrac13$ at $b$, and $\tfrac16+\tfrac16=\tfrac13$ at $c$. Directly, $$ \|\mu-\nu\|_{\mathrm{TV}} =\tfrac12\left(\left|\tfrac12-\tfrac13\right|+0+\left|\tfrac16-\tfrac13\right|\right) =\tfrac16, $$ so this coupling attains the coupling inequality.

A Geometric Bound from Repeated Opportunities to Meet

For chains with the same transition matrix $P$, a useful coupling is coalescent: when the two coordinates are equal, choose their next states identically. To state a convergence bound, take a joint process $(X_n,Y_n)$ with filtration $\mathcal{F}_n=\sigma(X_0,Y_0,\ldots,X_n,Y_n)$. Require that, conditional on $\mathcal{F}_n$, each coordinate moves according to $P$ from its current state, and that once $X_n=Y_n$, the coordinates remain equal at all subsequent times.

Theorem (Geometric coupling bound): Suppose such a coalescent coupling has the property that, for some $0<\varepsilon\le1$, at every time $n$ and every pair of distinct current states, $$ \mathbb{P}(X_{n+1}=Y_{n+1}\mid\mathcal{F}_n)\ge\varepsilon \quad\text{on }\{X_n\ne Y_n\}. $$ If $X_0=x$ and $Y_0$ has stationary distribution $\pi$, then for every integer $n\ge0$, $$ \|P^{(n)}(x,\cdot)-\pi\|_{\mathrm{TV}}\le \mathbb{P}(X_n\ne Y_n)\le(1-\varepsilon)^n. $$

Proof. Since the coordinate processes have transition matrix $P$, $X_n$ has distribution $P^{(n)}(x,\cdot)$. Also $Y_n$ has distribution $\pi$: it starts in $\pi$, and $\pi P=\pi$ implies inductively that its distribution remains $\pi$. The coupling inequality gives the first bound. For the second, let $q_n=\mathbb{P}(X_n\ne Y_n)$. On $\{X_n=Y_n\}$, coalescence means the next states agree. On its complement, the conditional probability of disagreement at the next time is at most $1-\varepsilon$. Taking expectations gives $q_{n+1}\le(1-\varepsilon)q_n$. Since $q_0\le1$, induction yields $q_n\le(1-\varepsilon)^n$, including $n=0$. $\square$

The hypothesis is a uniform, conditional meeting probability, not just a positive chance of meeting from one particular pair. It also does not say the displayed bound is the exact distance: a chosen coupling may fail to meet as often as an optimal coupling, and the inequality can be strict. The coupling time is $T_{\mathrm{c}}=\inf\{n\ge0:X_n=Y_n\}$; under coalescence, $\{T_{\mathrm{c}}>n\}=\{X_n\ne Y_n\}$, so the same argument bounds its tail.

Worked Example: A Uniform Overlap Bound for a Three-State Chain

Consider the chain on $S=\{a,b,c\}$ with transition matrix $$ P=\begin{bmatrix} \tfrac12&\tfrac14&\tfrac14\\ \tfrac14&\tfrac12&\tfrac14\\ \tfrac14&\tfrac14&\tfrac12 \end{bmatrix}. $$ Each row sums to $\tfrac12+\tfrac14+\tfrac14=1$, so $P$ is row-stochastic. The uniform distribution $\pi=(\tfrac13,\tfrac13,\tfrac13)$ is stationary: each coordinate of $\pi P$ is $\tfrac13(\tfrac12+\tfrac14+\tfrac14)=\tfrac13$.

For any two distinct rows, their coordinatewise common mass is $(\tfrac14,\tfrac14,\tfrac14)$, which sums to $\tfrac34$. Couple a pair of distinct states by assigning probability $\tfrac14$ to each equal outcome $(a,a),(b,b),(c,c)$. The remaining probability is $\tfrac14$; the residual distribution in each coordinate is concentrated at that coordinate's original state, so use those residual marginals for the remaining pair. Each marginal is its required transition row, and the probability of meeting is at least $\tfrac34$. If the states are already equal, use the same transition for both coordinates. Thus the theorem applies with $\varepsilon=\tfrac34$, giving $$ \|P^{(n)}(a,\cdot)-\pi\|_{\mathrm{TV}}\le\left(\tfrac14\right)^n. $$

For a check at $n=2$, starting from $a$ gives $$ P^{(2)}(a,\cdot)=\left(\tfrac38,\tfrac5{16},\tfrac5{16}\right). $$ Indeed, the first coordinate is $\tfrac12\cdot\tfrac12+\tfrac14\cdot\tfrac14+\tfrac14\cdot\tfrac14=\tfrac38$; the second is $\tfrac12\cdot\tfrac14+\tfrac14\cdot\tfrac12+\tfrac14\cdot\tfrac14=\tfrac5{16}$, and the third has the same calculation. Therefore $$ \|P^{(2)}(a,\cdot)-\pi\|_{\mathrm{TV}} =\tfrac12\left(\tfrac1{24}+\tfrac1{48}+\tfrac1{48}\right) =\tfrac1{24}\le\tfrac1{16}. $$ The exact distance is smaller than the coupling bound $(\tfrac14)^2=\tfrac1{16}$.

Computing a Coupling Bound for Metropolis–Hastings

For a finite-state Metropolis–Hastings chain, first compute its transition rows, including rejected proposals that leave the chain in place. Then compare rows to find a common mass that guarantees a chance of coalescence. The following example uses a state-dependent coupling: for each pair of current states it couples their two transition distributions, and for equal states it uses identical transitions. This is a valid joint construction because each coordinate has the required transition distribution conditional on the current pair.

Worked Example: A Three-State Metropolis–Hastings Coupling Bound

Let the target probabilities on $\{0,1,2\}$ be proportional to $(1,2,1)$, so $\pi=(\tfrac14,\tfrac12,\tfrac14)$. From either endpoint, propose to stay with probability $\tfrac12$ and move to the neighboring state with probability $\tfrac12$. From state $1$, propose $0$ or $2$, each with probability $\tfrac12$. The proposal is symmetric. The Metropolis–Hastings acceptance probability from $i$ to a proposed state $j$ is $\min(1,\pi_j/\pi_i)$.

From state $0$, the proposal to $1$ is accepted with probability $1$, giving probabilities $\tfrac12$ to stay and $\tfrac12$ to move to $1$. From state $1$, each proposal to an endpoint is accepted with probability $\tfrac12$; each move therefore has probability $\tfrac12\cdot\tfrac12=\tfrac14$, and the remaining probability $\tfrac12$ is a stay. State $2$ is symmetric to state $0$. Hence $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac14&\tfrac12&\tfrac14\\ 0&\tfrac12&\tfrac12 \end{bmatrix}. $$ Every row sums to $1$: respectively, $\tfrac12+\tfrac12=1$, $\tfrac14+\tfrac12+\tfrac14=1$, and $\tfrac12+\tfrac12=1$. Also $\pi P=\pi$: the three coordinates are $\tfrac14\cdot\tfrac12+\tfrac12\cdot\tfrac14=\tfrac14$, $\tfrac14\cdot\tfrac12+\tfrac12\cdot\tfrac12+\tfrac14\cdot\tfrac12=\tfrac12$, and $\tfrac12\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac14$.

For rows $0$ and $1$, the common masses at states $0,1,2$ are $\tfrac14,\tfrac12,0$, totaling $\tfrac34$. For rows $1$ and $2$, they are $0,\tfrac12,\tfrac14$, again totaling $\tfrac34$. For rows $0$ and $2$, the only common mass is $\tfrac12$ at state $1$, totaling $\tfrac12$. For each distinct pair, assign equal next states according to these common masses and couple the residual distributions in any way that preserves their marginals. This gives a meeting probability at least $\tfrac12$ for every pair. Once the chains meet, move them identically. The geometric coupling bound therefore gives, from any starting state $x$, $$ \|P^{(n)}(x,\cdot)-\pi\|_{\mathrm{TV}}\le\left(\tfrac12\right)^n. $$

For example, after $4$ steps the bound is $(\tfrac12)^4=\tfrac1{16}$. This is an upper bound on the distance, not a claim that the distance equals $\tfrac1{16}$. The construction guarantees that at each step before meeting, the conditional meeting probability is at least $\tfrac12$; iterating that conditional guarantee is what yields the bound.

What the Bound Does—and Does Not—Say

A uniform overlap condition is useful because it converts a local comparison of transition rows into a bound valid at every time. Its limitation is equally important: if some pair of distinct states has no common one-step mass, this particular argument gives no positive uniform $\varepsilon$. A bound might still be available by comparing multiple steps or by using a different coupling, but it does not follow from the one-step condition above.

For instance, the identity chain on $\{0,1\}$ has transition matrix $P=I$ and stationary distribution $\pi=(\tfrac12,\tfrac12)$. Starting at $0$, its distribution remains $(1,0)$, whose total variation distance from $\pi$ is $\tfrac12$ at every time. If one starts the second chain from $\pi$, the two chains cannot coalesce when they start at different states. There is no positive uniform meeting probability for distinct pairs, and no geometric decay follows. This example shows why the meeting-probability hypothesis matters.

Common mistake. Omitting the factor $\tfrac12$ in the definition of total variation doubles the reported distance. In the $n=2$ calculation for the three-state chain above, the sum of absolute coordinate differences is $\tfrac1{24}+\tfrac1{48}+\tfrac1{48}=\tfrac1{12}$. The total variation distance is half that sum, $\tfrac1{24}$, not $\tfrac1{12}$. The coupling bound is then checked against the correct distance: $\tfrac1{24}\le\tfrac1{16}$.

Check Your Understanding

For each question, distinguish the coupling probability from the total variation distance it bounds.

For distributions $\mu=(\tfrac12,\tfrac12)$ and $\nu=(\tfrac34,\tfrac14)$ on a two-state space, calculate their total variation distance.
In the geometric coupling theorem, why must the lower bound on meeting probability hold conditionally for every distinct current pair?
For the Metropolis–Hastings matrix in the worked example, what is the common mass of rows $0$ and $2$, and at which state does it occur?
If a coalescent coupling has meeting probability at least $\tfrac13$ at each step before meeting, what upper bound does it give on the probability that the chains still differ after $n$ steps?
Why does the coupling inequality give an upper bound rather than necessarily an equality?

Coupling Bounds for Finite-State MCMC

What You'll Learn