Coupling as a Bound on Distance
Convergence to equilibrium asks how close the distribution of a chain at time \(t\) is to its stationary distribution. A coupling approaches this question indirectly: put two chains on the same probability space, give them the correct individual dynamics, and arrange for them to become equal. Once they meet, a construction that keeps them together turns the probability that they have not yet met into a bound on distributional distance.
Throughout, let \((X_t)_{t\ge0}\) and \((Y_t)_{t\ge0}\) be continuous-time Markov chains on the same finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal F,\mathbb P)\). Write \(P(t)\) for their common transition semigroup when their generators are the same. A coupling means that the two processes are defined jointly while each coordinate, considered on its own, has the specified chain law. For chains with generator \(Q=(q_{ij})\), this means each coordinate has transition rate \(q_{ij}\) from \(i\) to \(j\), for \(i\ne j\).
For probability distributions \(\alpha,\beta\) on a countable state space, their total variation distance is \( \|\alpha-\beta\|_{\mathrm{TV}}=\sup_{A\subseteq S}|\alpha(A)-\beta(A)|=\tfrac12\sum_{i\in S}|\alpha_i-\beta_i| \). The factor \(1/2\) belongs to this definition; it is not an additional factor to apply to a coupling probability.
Proof. Fix any set \(A\subseteq S\). The difference between the two probabilities of \(A\) can be written as \( \mathbb P(X_t\in A)-\mathbb P(Y_t\in A)=\mathbb E[\mathbf 1_{\{X_t\in A\}}-\mathbf 1_{\{Y_t\in A\}}]. \) The two indicators agree whenever \(X_t=Y_t\), and their absolute difference is at most \(1\) otherwise. Therefore \( |\mathbb P(X_t\in A)-\mathbb P(Y_t\in A)|\le\mathbb P(X_t\ne Y_t)=\mathbb P(T>t), \) where the last equality uses coalescence. Taking the supremum over \(A\) proves the first inequality. If \(Y_0\) has distribution \(\pi\) and \(\pi P(t)=\pi\), then \(Y_t\) also has distribution \(\pi\); substituting \(\nu=\pi\) proves the second inequality. \(\square\)
The theorem applies to any coalescing coupling; it does not prescribe one. The next construction shows that such couplings are available for finite-state continuous-time chains, even if the resulting bound is not always sharp.
A General Coalescing Construction
Let \(S\) be finite and let \(Q\) be a generator: \(q_{ij}\ge0\) for \(i\ne j\), and each row sums to zero, so \(q_{ii}=-\sum_{j\ne i}q_{ij}\). For \(x\ne y\), define a joint chain as follows. Before the coordinates meet, let either coordinate make its own jumps while the other stays fixed. When the pair is \((x,y)\), its rate of transition to \((z,y)\) is \(q_{xz}\) for \(z\ne x\), and its rate to \((x,w)\) is \(q_{yw}\) for \(w\ne y\). A jump can land on the diagonal; for example, \((x,y)\) can jump to \((y,y)\). On the diagonal, make the two coordinates jump together: from \((x,x)\) to \((z,z)\) at rate \(q_{xz}\), for each \(z\ne x\).
Why this is a valid coupling. At an off-diagonal pair \((x,y)\), the first coordinate has rate \(q_{xz}\) to each \(z\ne x\), and no other joint transitions change that coordinate. Its total rate of leaving \(x\) is therefore \(\sum_{z\ne x}q_{xz}=-q_{xx}\), as required. The same check gives rate \(q_{yw}\) for the second coordinate to move from \(y\) to \(w\). On a diagonal pair \((x,x)\), each coordinate moves from \(x\) to \(z\) at rate \(q_{xz}\), because the joint transition to \((z,z)\) changes both coordinates. Thus both marginals have generator \(Q\). The diagonal is preserved by the construction, so the coupling is coalescing. Since the joint state space \(S\times S\) is finite and all specified rates are finite, these rates define a continuous-time Markov chain.
This construction may allow the coordinates to separate if they are run independently after meeting. That would invalidate a bound based on \(\mathbb P(T>t)\). Synchronizing their jumps on the diagonal is precisely what prevents separation.
Worked Example: A Two-State Chain Started from Different States
Take \(S=\{0,1\}\) and generator \(Q=\begin{bmatrix}-1&1\\2&-2\end{bmatrix}\). The first row sums to \(-1+1=0\), and the second to \(2-2=0\). Use the construction above, starting the joint chain at \((0,1)\).
From \((0,1)\), the first coordinate jumps from \(0\) to \(1\) at rate \(1\), producing \((1,1)\). The second jumps from \(1\) to \(0\) at rate \(2\), producing \((0,0)\). Both transitions meet the chains, and after that the pair stays on the diagonal. Hence the meeting time is exponential with rate \(1+2=3\), and \( \mathbb P(T>t)=e^{-3t}. \)
To check the resulting bound against the marginal laws, the stationary distribution is \(\pi=(\tfrac23,\tfrac13)\): the rate of flow from \(0\) to \(1\) is \(\tfrac23\cdot1=\tfrac23\), equal to the rate \(\tfrac13\cdot2=\tfrac23\) from \(1\) to \(0\). Let \(u(t)\) be the probability of state \(1\) when starting at \(0\). The forward equation is \(u'(t)=1-3u(t)\), with \(u(0)=0\), so \(u(t)=\tfrac13(1-e^{-3t})\). Starting at \(1\), the probability of state \(1\) is \(v(t)=\tfrac13+\tfrac23e^{-3t}\), the solution with \(v(0)=1\). On a two-state space, total variation distance is the absolute difference between the probabilities of state \(1\). Thus \( |v(t)-u(t)|=|\tfrac13+\tfrac23e^{-3t}-\tfrac13+\tfrac13e^{-3t}|=e^{-3t}. \) This equals the meeting-time bound. At \(t=0\), both sides are \(1\), as they must be for two different point masses.
Choosing a Coupling to Make Meeting Likely
The independent-until-meeting construction is systematic, but a coupling designed around the transition mechanism can give a simpler or faster meeting-time estimate. A useful case is a chain that can be represented as periodic random resets: at each event, its state is replaced by a draw from a fixed distribution. Two copies can use the same reset times and the same reset value, so the first reset makes them equal.
Worked Example: A Three-State Shared-Reset Coupling
Let \(S=\{1,2,3\}\), let \(\pi=(\tfrac12,\tfrac13,\tfrac16)\), and let reset events occur at rate \(2\). At each event, choose a new state from \(\pi\). If the chosen state equals the current state, the event causes no visible change. For \(i\ne j\), the generator has \(q_{ij}=2\pi_j\). Its rows are \( (-1,\tfrac23,\tfrac13),\quad (1,-\tfrac43,\tfrac13),\quad (1,\tfrac23,-\tfrac53). \) The row sums are respectively \(-1+\tfrac23+\tfrac13=0\), \(1-\tfrac43+\tfrac13=0\), and \(1+\tfrac23-\tfrac53=0\).
The proposed stationary distribution is verified directly. For column \(1\), \(\tfrac12(-1)+\tfrac13(1)+\tfrac16(1)=0\); for column \(2\), \(\tfrac12(\tfrac23)+\tfrac13(-\tfrac43)+\tfrac16(\tfrac23)=0\); for column \(3\), \(\tfrac12(\tfrac13)+\tfrac13(\tfrac13)+\tfrac16(-\tfrac53)=0\). Also \(\tfrac12+\tfrac13+\tfrac16=1\), so \(\pi Q=0\). Equivalently, after a reset event the state has distribution \(\pi\), and resetting preserves that distribution.
Start \(X_0=1\), and let \(Y_0\) have distribution \(\pi\). At every reset event, choose one common reset value for both chains. Each coordinate has the stated generator, and the chains agree at the first reset. If \(Y_0=1\), they already agree; otherwise they remain different until the first reset. Therefore the probability they have not met by time \(t\) is \( \mathbb P(T>t)=\mathbb P(Y_0\ne1)e^{-2t}=(1-\tfrac12)e^{-2t}=\tfrac12e^{-2t}. \)
Check against the marginal distribution. From state \(1\), the law at time \(t\) is \(e^{-2t}\delta_1+(1-e^{-2t})\pi\): with probability \(e^{-2t}\) no reset has occurred, and otherwise the last reset value has law \(\pi\). Its distance to \(\pi\) is \(e^{-2t}\|\delta_1-\pi\|_{\mathrm{TV}}\). Since \(\|\delta_1-\pi\|_{\mathrm{TV}}=\tfrac12(|1-\tfrac12|+|0-\tfrac13|+|0-\tfrac16|)=\tfrac12\), this distance is exactly \(\tfrac12e^{-2t}\), agreeing with the coupling bound.
In applications, the key task is often not to calculate the full distribution of \(T\), but to bound its tail. For example, if a coupling argument shows \(\mathbb P(T>t)\le Ce^{-ct}\) for constants \(C,c>0\), then the coupling inequality immediately gives the same bound on total variation distance. The constants must come from a valid coupling and a justified estimate of its meeting time; they are not automatic consequences of having a stationary distribution.
Worked Example: A Shared-Map Coupling on a Three-State Path
Let \(S=\{0,1,2\}\) and use generator \( Q=\begin{bmatrix}-1&1&0\\1&-2&1\\0&1&-1\end{bmatrix}. \) The row sums are \(-1+1=0\), \(1-2+1=0\), and \(1-1=0\). The distribution \(\pi=(\tfrac13,\tfrac13,\tfrac13)\) is stationary: each column sum of \(Q\) is zero, so each coordinate of \(\pi Q\) is zero.
Construct both chains using two shared rate-\(1\) event clocks. At a left event apply \(L(x)=\max(x-1,0)\) to each coordinate; at a right event apply \(R(x)=\min(x+1,2)\) to each coordinate. At state \(0\), left events do nothing and right events move to \(1\) at rate \(1\); at state \(1\), the two event types move to \(0\) and \(2\), each at rate \(1\); at state \(2\), right events do nothing and left events move to \(1\) at rate \(1\). These are exactly the rates in \(Q\), so each coordinate has the required chain law. Once the coordinates agree, applying the same map keeps them equal.
First take the initial pair \((0,2)\). The first clock event occurs after an exponential time of rate \(2\). It changes the pair to either \((0,1)\) or \((1,2)\). From either adjacent pair, one of the two clocks makes the coordinates equal at rate \(1\), while the other changes the pair to the other adjacent pair at rate \(1\). Consequently the probability of still being unequal for a further duration \(s\), starting from an adjacent pair, is \(e^{-s}\): the total event rate is \(2\), and the unequal pair is retained or changed at rate \(1\), while coalescence occurs at rate \(1\). More explicitly, the probability \(g(s)\) of remaining unequal satisfies \(g'(s)=-g(s)\), \(g(0)=1\).
For \(t\ge0\), either there is no event by time \(t\), with probability \(e^{-2t}\), or the first event occurs at time \(s\le t\), with density \(2e^{-2s}\), followed by an adjacent-pair duration \(t-s\). Hence \( \mathbb P_{(0,2)}(T>t)=e^{-2t}+\int_0^t 2e^{-2s}e^{-(t-s)}\,ds=e^{-2t}+2e^{-t}(1-e^{-t})=2e^{-t}-e^{-2t}. \)
Now start \(X_0=0\) and take \(Y_0\sim\pi\). If \(Y_0=0\), the chains meet immediately; if \(Y_0=1\), the meeting-time tail is \(e^{-t}\); if \(Y_0=2\), it is \(2e^{-t}-e^{-2t}\). Averaging with the three initial probabilities gives \( \mathbb P(T>t)=\tfrac13\cdot0+\tfrac13e^{-t}+\tfrac13(2e^{-t}-e^{-2t})=e^{-t}-\tfrac13e^{-2t}. \) Thus \( \|\mathcal L(X_t)-\pi\|_{\mathrm{TV}}\le e^{-t}-\tfrac13e^{-2t} \). At \(t=0\), the bound is \(\tfrac23\), equal to \(\|\delta_0-\pi\|_{\mathrm{TV}}=\tfrac12(\tfrac23+\tfrac13+\tfrac13)=\tfrac23\). This checks the initial-time value.
What the Bound Does—and Does Not—Say
A coupling bound proves convergence to stationarity when its right-hand side tends to zero. In particular, if a coalescing coupling with \(Y_0\sim\pi\) satisfies \(\mathbb P(T>t)\to0\), then the total variation distance tends to zero by the proved inequality. A stationary distribution alone does not supply such a coupling estimate, and the estimate can be loose: different couplings of the same marginals can have different meeting-time tails.
Common mistake. It is incorrect to halve the mismatch probability after applying the coupling inequality. For example, if \(X_t\) and \(Y_t\) are deterministic and unequal, their distributions are different point masses, so their total variation distance is \(1\), while \(\mathbb P(X_t\ne Y_t)=1\). The incorrect bound \(\|{\cal L}(X_t)-{\cal L}(Y_t)\|_{\mathrm{TV}}\le\tfrac12\mathbb P(X_t\ne Y_t)=\tfrac12\) fails. The factor \(1/2\) is already present in the sum formula for total variation; the coupling inequality itself has no extra factor.
Meeting is also essential. For a chain on \(\{0,1\}\) with zero generator, both states are absorbing. The stationary distribution \(\pi=\delta_0\) is valid, but a chain started at \(1\) remains there, so its distance to \(\pi\) is \(1\) at every time. Coupling it with a stationary copy started at \(0\) gives \(\mathbb P(T>t)=1\) forever. No claim of convergence follows. In general, verify both marginal dynamics and the coalescing property before using a meeting-time tail.
Check Your Understanding
Use the definitions and verify each coupling against its marginal transition rates.
- For the two-state generator with rates \(q_{01}=3\) and \(q_{10}=1\), what is the stationary distribution? Under the independent-until-meeting coupling from \((0,1)\), what is \(\mathbb P(T>t)\)?
- State why the diagonal rule in the general joint-generator construction makes the coupling coalescing.
- For a coalescing coupling with \(Y_0\sim\pi\), explain why the coupling inequality bounds distance to \(\pi\), rather than merely distance between two unspecified laws.
- In the shared-reset example, what is the probability that a reset has occurred by time \(t\), and why does one shared reset ensure equality?
- Give a reason a valid coupling can yield a bound that is not sharp, even when both marginal chains are correct.