Meeting-Time Tails as Convergence Bounds
Total variation distance measures how distinguishable two probability distributions are by observing the state. A coupling gives a way to bound this distance: run two chains together on one probability space, with each chain having the desired marginal law, and track how long they remain different. If the chains are constructed to stay together once they meet, then a difference at time \(n\) is possible only if they have not met by time \(n\). This turns a tail probability for a random time into a bound on distributional convergence.
Let \(S\) be a finite or countable state space, and let \(P=(p_{ij})\) be a transition matrix on \(S\), with \(\sum_{j\in S}p_{ij}=1\) for each \(i\). For probability distributions \(\alpha,\beta\) on \(S\), use the total variation convention \(\|\alpha-\beta\|_{\mathrm{TV}}=\sup_{A\subseteq S}|\alpha(A)-\beta(A)|\). For chains started at \(x,y\in S\), their time-\(n\) distributions are \(P^{(n)}(x,\cdot)\) and \(P^{(n)}(y,\cdot)\).
The coalescing condition is part of the bound, not a cosmetic feature. The two coordinates must each have the correct transition law, but before they meet their transitions may be dependent. Once they meet, using the same transition for both coordinates preserves both marginal laws and ensures that meeting is permanent. The time \(T\) is a stopping time for the joint filtration because \(\{T\le n\}=\bigcup_{k=0}^n\{X_k=Y_k\}\in\mathcal{F}_n\).
Proof. Fix any set \(A\subseteq S\). For the point-started chains, the absolute difference between their probabilities of being in \(A\) at time \(n\) is $$ \left|\mathbb{P}(X_n\in A)-\mathbb{P}(Y_n\in A)\right| =\left|\mathbb{E}\left[\mathbf{1}_{\{X_n\in A\}}-\mathbf{1}_{\{Y_n\in A\}}\right]\right|. $$ The absolute value of an expectation is at most the expectation of the absolute value. The two indicators agree whenever \(X_n=Y_n\), and their absolute difference is at most \(1\) otherwise. Therefore the expression is at most \(\mathbb{P}(X_n\ne Y_n)\). Coalescence implies that \(\{X_n\ne Y_n\}\subseteq\{T>n\}\): if \(T\le n\), the chains have met and have stayed together through time \(n\). Thus the expression is at most \(\mathbb{P}(T>n)\). Taking the supremum over all \(A\) gives the stated total variation bound, since the coordinates have the required time-\(n\) distributions. The same argument applies to random initial states with laws \(\mu,\nu\), whose time-\(n\) distributions are \(\mu P^{(n)},\nu P^{(n)}\). \(\square\)
The theorem separates the construction of a coupling from the use of its tail. A useful coupling need not make the chains meet as quickly as possible; it must be valid and coalescing, and its meeting-time tail must be tractable. Any upper bound on that tail is consequently an upper bound on total variation distance.
Worked Example: A Two-State Chain with an Exact Tail Bound
Take \(S=\{0,1\}\) and $$ P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}. $$ Each row sums to \(\tfrac34+\tfrac14=1\). Start one chain at \(0\) and the other at \(1\). When the chains are at different states, couple their next states by assigning probability \(\tfrac14\) to \((0,0)\), probability \(\tfrac14\) to \((1,1)\), and probability \(\tfrac12\) to \((0,1)\). Each coordinate then has its correct row of \(P\). Once the chains meet, use identical transitions for them.
At each step before meeting, the chance of meeting is \(\tfrac14+\tfrac14=\tfrac12\), while the chance of remaining different is \(\tfrac12\). Since they start different, for every \(n\ge0\), $$ \mathbb{P}(T>n)=\left(\tfrac12\right)^n. $$ For example, at \(n=2\) the tail is \(\tfrac12\cdot\tfrac12=\tfrac14\), so the theorem gives a total variation bound of \(\tfrac14\).
Here the bound can be checked exactly. If \(a_n=\mathbb{P}_0(X_n=0)-\mathbb{P}_1(X_n=0)\), then \(a_0=1\). One step gives \(a_{n+1}=(\tfrac34-\tfrac14)a_n=\tfrac12a_n\), so \(a_n=(\tfrac12)^n\). On a two-state space the total variation distance is the absolute difference in the probability of either one-state set. Hence the distance at \(n=2\) is \(|a_2|=|(\tfrac12)^2|=\tfrac14\), exactly the coupling bound.
Turning Tail Estimates into Rates
A tail formula is already a time-specific convergence estimate. If, for some constants \(C<\infty\) and \(0<r<1\), a coupling satisfies \(\mathbb{P}(T>n)\le Cr^n\) for all \(n\ge0\), then its total variation distance is at most \(Cr^n\) at time \(n\). The same statement applies to a stationary comparison: if \(Y_0\) has stationary distribution \(\pi\), then \(Y_n\) has distribution \(\pi\), and \(\|\mathcal{L}(X_n)-\pi\|_{\mathrm{TV}}\le\mathbb{P}(T>n)\). Here \(\mathcal{L}(X_n)\) denotes the distribution of \(X_n\). Stationarity is needed for the comparison distribution to remain \(\pi\); the coupling inequality itself does not require stationarity.
An exponential moment also controls the tail. The following implication uses only Markov's inequality. Suppose \(a>1\), \(T\) is nonnegative integer-valued (allowing \(T=\infty\)), and \(\mathbb{E}[a^T]<\infty\), with \(a^\infty=\infty\). On the event \(\{T>n\}\), the integer-valued property gives \(T\ge n+1\), so \(a^T\ge a^{n+1}\). Therefore \(\mathbb{E}[a^T]\ge a^{n+1}\mathbb{P}(T>n)\), and \(\mathbb{P}(T>n)\le a^{-(n+1)}\mathbb{E}[a^T]\). The strict tail event \(T>n\) matters: it is what yields the threshold \(n+1\).
Worked Example: Converting an Exponential Moment into a Rate
Suppose a coalescing coupling satisfies \(\mathbb{E}[2^T]\le8\). The preceding argument with \(a=2\) gives $$ \mathbb{P}(T>n)\le\frac{8}{2^{n+1}}. $$ At \(n=3\), this gives \(\mathbb{P}(T>3)\le 8/2^4=8/16=1/2\), and therefore the total variation distance at time \(3\) is at most \(1/2\). At \(n=5\), it gives \(\mathbb{P}(T>5)\le8/2^6=8/64=1/8\), so the time-\(5\) distance is at most \(1/8\). These are valid upper bounds; they need not be equal to the actual tail or distance.
The endpoint convention can be checked directly: when \(T=6\), the event \(T>5\) holds and \(2^T=64=2^{5+1}\). Using \(2^5\) instead of \(2^6\) in the threshold would lose the sharper integer-time bound.
Sometimes it is easier to bound the mean meeting time than the whole tail. If \(\mathbb{E}[T]<\infty\), then on \(\{T>n\}\), \(T\ge n+1\). Thus \(\mathbb{E}[T]\ge(n+1)\mathbb{P}(T>n)\), and the coupling theorem yields the weaker but useful estimate \(\|\mathcal{L}(X_n)-\mathcal{L}(Y_n)\|_{\mathrm{TV}}\le \mathbb{E}[T]/(n+1)\). This is a polynomial bound, not a geometric one. A finite mean alone does not imply a geometric tail.
Worked Example: Comparing a Chain with Its Stationary Distribution
Let \(S=\{0,1,2\}\), and define \(f(0)=1\), \(f(1)=2\), and \(f(2)=0\). Consider a chain which, at each step, resets to \(0\) with probability \(\tfrac12\), and otherwise moves from \(i\) to \(f(i)\). Its transition matrix is $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac12&0&\tfrac12\\ 1&0&0 \end{bmatrix}. $$ The row sums are \(\tfrac12+\tfrac12=1\), \(\tfrac12+\tfrac12=1\), and \(1=1\), so \(P\) is stochastic.
First find a stationary distribution \(\pi=(\pi_0,\pi_1,\pi_2)\). The equations \(\pi P=\pi\) give \(\pi_1=\tfrac12\pi_0\), \(\pi_2=\tfrac12\pi_1\), and \(\pi_0=\tfrac12\pi_0+\tfrac12\pi_1+\pi_2\). The first two equations give \(\pi_1=\tfrac12\pi_0\) and \(\pi_2=\tfrac14\pi_0\). Normalization gives \(\pi_0+\pi_1+\pi_2=(1+\tfrac12+\tfrac14)\pi_0=\tfrac74\pi_0=1\), hence \(\pi=(\tfrac47,\tfrac27,\tfrac17)\). Check: the coordinates of \(\pi P\) are \(\tfrac12\cdot\tfrac47+\tfrac12\cdot\tfrac27+\tfrac17=\tfrac47\), \(\tfrac12\cdot\tfrac47=\tfrac27\), and \(\tfrac12\cdot\tfrac27=\tfrac17\); they equal \(\pi\), whose entries sum to \(1\).
Start \(X_0=0\), and start \(Y_0\) with distribution \(\pi\). At every step use the same reset coin for both chains. If it says reset, set both chains to \(0\); if they are already equal, use identical transitions thereafter. If the chains start different and no reset has occurred, applying the bijection \(f\) to both states keeps them different. Consequently, for every \(n\ge0\), \(T>n\) exactly when \(Y_0\ne0\) and no reset occurs in the first \(n\) steps. The initial inequality has probability \(1-\pi_0=1-\tfrac47=\tfrac37\), independently of the reset coins, so \(\mathbb{P}(T>n)=\tfrac37(\tfrac12)^n\). At \(n=2\), the coupling bound is \(\tfrac37\cdot\tfrac14=\tfrac3{28}\).
For a direct check, \(P^{(2)}(0,\cdot)=\tfrac12( \tfrac12,\tfrac12,0)+\tfrac12(\tfrac12,0,\tfrac12)=(\tfrac12,\tfrac14,\tfrac14)\). Its total variation distance from \(\pi\) is $$ \tfrac12\left(\left|\tfrac12-\tfrac47\right|+ \left|\tfrac14-\tfrac27\right|+ \left|\tfrac14-\tfrac17\right|\right) =\tfrac12\left(\tfrac1{14}+\tfrac1{28}+\tfrac3{28}\right) =\tfrac3{28}. $$ Thus this coupling bound is exact at time \(2\).
Why Coalescence Matters
A common mistake is to define \(T\) as the first time the chains meet and then assume, without imposing any condition on the coupling, that \(\{X_n\ne Y_n\}\subseteq\{T>n\}\). That inclusion can fail: a coupling can have \(X_1=Y_1\) and then choose different next states at time \(2\), even when both coordinates still have the correct marginal transitions. In that case \(T\le1\) but \(X_2\ne Y_2\). The correction is to use a coalescing coupling, or to prove separately that the chosen construction stays together after meeting. Without this condition, the proof of the tail bound has a missing step.
Another common error is to reverse the tail event. A small \(\mathbb{P}(T>n)\) is useful because it bounds the probability that the chains are still different; \(\mathbb{P}(T\le n)\) measures the complementary event and does not give the same upper bound. Finally, a coupling estimate is an upper bound, not automatically an exact distance. The exact two-state and stationary-start calculations above show equality in particular cases, but other couplings may give looser bounds.
Check Your Understanding
In each question, specify whether the coupling is coalescing and use the strict tail event \(T>n\).
- Two chains start in different states, and their coupling has conditional probability at least \(\tfrac13\) of meeting at the next step whenever they are still different. What upper bound follows for \(\mathbb{P}(T>n)\)?
- If \(\mathbb{E}[3^T]\le9\), what coupling bound on total variation follows at time \(n=2\)?
- Why does a stationary-start comparison require that the second chain have initial distribution \(\pi\) satisfying \(\pi P=\pi\)?
- For a coalescing coupling with \(\mathbb{P}(T>n)\le 5(2/3)^n\), state the resulting total variation bound at time \(n\).
- Give a path on which two chains meet and later separate, and explain which inclusion in the coupling-time proof fails on that path.