Constructing Couplings for Markov Chains

From Two Transition Rules to One Joint Rule

A coupling lets us study two versions of a Markov chain on the same probability space. The aim is not merely to give each version the correct transition probabilities: the joint rule can also make their states agree, or ensure that they stay in agreement once they meet. Such constructions support comparisons between distributions at different times. The details of the joint update matter, because correct marginal chains alone do not guarantee that agreement will persist.

Let \(S\) be a finite or countable state space and \(P=(p_{ij})\) a transition matrix, with \(p_{ij}\ge 0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), a Markov chain \((X_n)_{n\ge0}\) with state space \(S\) has transition probabilities \(P\) when, conditional on its history through time \(n\), its next state has distribution \(P(X_n,\cdot)\). For a pair of chains we use the joint-history filtration \(\mathcal{F}_n=\sigma(X_0,Y_0,\ldots,X_n,Y_n)\).

The two coordinates need not be independent. Their dependence is precisely what the construction chooses. A particularly useful property is coalescence: once \(X_n=Y_n\), the update rule keeps \(X_{n+1}=Y_{n+1}\) with probability one. The diagonal \(\{(x,x):x\in S\}\) is then absorbing for the pair process.

Two Ways to Construct a Joint Update

Shared randomness. Fix an ordering of a finite state space. Given a uniform random variable \(U\) on \([0,1)\), define \(F(x,U)\) by dividing \([0,1)\) into consecutive intervals of lengths \(p_{xj}\), in the fixed state order, and returning the state whose interval contains \(U\). Then \(F(x,U)\) has distribution \(P(x,\cdot)\). Updating both chains with the same \(U\), as \(X_{n+1}=F(X_n,U_n)\) and \(Y_{n+1}=F(Y_n,U_n)\), preserves their transition rows. If the current states are equal, the same function and same random input give equal next states. For a countable state space, the same construction uses a countable sequence of intervals whose lengths sum to one.

Shared randomness is convenient, but it does not generally maximize the chance of agreement in one update. That is the purpose of maximal coupling.

Here is an explicit construction. Put \(c_i=\min(a_i,b_i)\), \(r_i=a_i-c_i\), and \(s_i=b_i-c_i\). The two residual sequences have the same total mass \(1-\alpha\). If this mass is positive, assign joint mass \(c_i\) to \((i,i)\), and assign additional mass \(r_i s_j/(1-\alpha)\) to \((i,j)\). If the residual mass is zero, assign only the diagonal masses \(c_i\).

Why the construction works. If \(1-\alpha>0\), summing the additional mass over \(j\) gives \(r_i\), because \(\sum_j s_j=1-\alpha\). Thus the first marginal at \(i\) is \(c_i+r_i=a_i\). Summing over \(i\) gives \(s_j\), so the second marginal at \(j\) is \(c_j+s_j=b_j\). For each \(i\), at least one of \(r_i,s_i\) is zero: if \(a_i\le b_i\), then \(r_i=0\), and if \(b_i\le a_i\), then \(s_i=0\). The residual part therefore puts no mass on \((i,i)\). The probability of equality is exactly \(\sum_i c_i=\alpha\). If \(1-\alpha=0\), then \(a=b=c\), and the diagonal coupling has the required marginals and agreement probability one. This proves the construction in both cases.

Apply this rule at each pair \((x,y)\), using \(a_i=p_{xi}\) and \(b_i=p_{yi}\). This defines a joint transition kernel with the required marginals. On the diagonal, the two rows are identical; choosing the diagonal coupling there makes equality persistent.

Worked Constructions

When Does a Meeting Last?

Proof. Fix \(n\). Conditional on \(\mathcal{F}_n\), the current pair is known. On the event \(\{X_n=Y_n=x\}\), the conditional probability of unequal next states is \[ \mathbb{P}(X_{n+1}\ne Y_{n+1}\mid\mathcal{F}_n) =\sum_{i\ne j}K((x,x),(i,j))=0. \] Thus equality holds at time \(n+1\) almost surely on \(\{X_n=Y_n\}\). Applying this implication successively shows that for each fixed pair \(n\le m\), equality at time \(n\) implies equality at time \(m\), outside a null event. There are only countably many pairs of integer times, so the union of these exceptional null events is still null. On \(\{T<\infty\}\), the equality begins at the integer time \(T\), and hence persists at every later integer time. \(\square\)

The condition is about the joint update on the diagonal; the marginal transition rules alone do not impose it. For instance, suppose both chains are currently at \(x\) and the row \(P(x,\cdot)\) assigns positive probability to two different states. An update that samples their next states independently has positive probability of choosing different states. It remains a valid coupling of the marginals, but it does not preserve a meeting. In contrast, the diagonal update assigns probability \(p_{xi}\) to \((i,i)\) for each \(i\), so its marginals are both \(P(x,\cdot)\) and it preserves equality.

A useful consequence is the coupling inequality. If \(X_n\) and \(Y_n\) have marginal distributions \(\mu_n\) and \(\nu_n\), then for any \(A\subseteq S\), \[ |\mu_n(A)-\nu_n(A)| =|\mathbb{E}[\mathbf{1}_{\{X_n\in A\}}-\mathbf{1}_{\{Y_n\in A\}}]| \le \mathbb{P}(X_n\ne Y_n). \] Indeed, the two indicators agree whenever \(X_n=Y_n\), and their absolute difference is at most one otherwise. Taking the supremum over \(A\) gives \(\|\mu_n-\nu_n\|_{\mathrm{TV}}\le\mathbb{P}(X_n\ne Y_n)\). For a coalescent coupling, \(\{X_n\ne Y_n\}\subseteq\{T>n\}\), so the right side can be bounded by the probability that the chains have not met by time \(n\). This inequality is a bound, not an assertion that every coupling is optimal or that a meeting must occur.

Common Mistake and Construction Checklist

Common mistake: assigning residual mass to the wrong coordinate. In the first worked example, a tempting but incorrect table assigns probabilities \(\tfrac14\) to \((0,0)\), \(\tfrac12\) to \((1,1)\), and \(\tfrac14\) to \((1,2)\). Its first marginal puts mass \(\tfrac14\) at \(0\) and \(\tfrac12+\tfrac14=\tfrac34\) at \(1\), which is not the required row \((\tfrac12,\tfrac12,0)\). The shared mass at state \(1\) is already \(\tfrac12\), leaving no first-row residual there. The first-row residual is instead \(\tfrac14\) at state \(0\), and the second-row residual is \(\tfrac14\) at state \(2\). Pairing those residuals at \((0,2)\) gives the correct table, whose marginals were checked explicitly above.

For a new coupling construction, check the following in order:

• Each transition row is a probability distribution.
• The joint update has the specified first and second marginals, computed by summing over the other coordinate.
• Any claimed agreement probability follows from the actual diagonal mass.
• If a meeting is meant to persist, the joint kernel assigns zero probability to leaving the diagonal.
• If shared randomness is used, verify its resulting joint outcomes rather than assuming it is maximal.

These checks separate three distinct goals: preserving the two Markov-chain laws, maximizing the chance of agreement in an update, and ensuring that an achieved agreement is permanent. A construction may meet the first goal without meeting either of the other two. Choosing and verifying the joint rule is the central step.