From Meeting Times to Mixing Bounds
For a finite Markov chain, a coupling gives a way to compare two copies of the chain on the same probability space while preserving each copy’s transition law. If the copies meet and are then kept together, their distributions can differ at time \(t\) only on the event that they have not yet met. This simple observation turns a bound on meeting times into a bound on convergence to stationarity, and therefore into an explicit mixing-time estimate.
Let \(S\) be a finite state space, let \(P=(p_{ij})\) be a transition matrix whose rows sum to \(1\), and suppose \(\pi\) is a stationary distribution, so \(\pi P=\pi\). For a distribution \(\nu\) on \(S\), write \(\nu P^t\) for its distribution after \(t\) steps. The total-variation distance is \(\|\nu-\eta\|_{\mathrm{TV}}=\frac12\sum_{j\in S}|\nu(j)-\eta(j)|\). For \(0<\varepsilon<1\), define the worst-case mixing time by \(t_{\mathrm{mix}}(\varepsilon)=\inf\{t\ge0:\max_{x\in S}\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}\le\varepsilon\}\), where \(t\) ranges over nonnegative integers. If this set is empty, the mixing time is infinite.
The coalescent condition matters because it makes the event \(X_t\ne Y_t\) exactly the event \(T>t\). A coupling may be designed using shared randomness, or by choosing a joint distribution of the next states conditional on the current pair. Either way, each marginal transition must still be \(P\); otherwise it is not a coupling of the specified chains.
Proof. First, for any two random variables \(U,V\) on \(S\) with respective distributions \(\nu,\eta\), and any subset \(A\subseteq S\), \(|\nu(A)-\eta(A)|=|\mathbb{P}(U\in A)-\mathbb{P}(V\in A)|\le\mathbb{P}(U\ne V)\). Indeed, the two indicators \(\mathbf{1}_{\{U\in A\}}\) and \(\mathbf{1}_{\{V\in A\}}\) agree whenever \(U=V\), so their absolute difference is at most \(\mathbf{1}_{\{U\ne V\}}\). On a finite set, total variation equals \(\sup_{A\subseteq S}|\nu(A)-\eta(A)|\): taking \(A=\{j:\nu(j)\ge\eta(j)\}\) gives half the sum of the absolute coordinate differences, and no other set can give a larger absolute difference. Thus \(\|\nu-\eta\|_{\mathrm{TV}}\le\mathbb{P}(U\ne V)\). Apply this with \(U=X_t\) and \(V=Y_t\). Their distributions are \(P^t(x,\cdot)\) and \(\pi\), respectively, because \(\pi P=\pi\). By coalescence, \(X_t\ne Y_t\) if and only if \(T_x>t\), proving the first inequality. Taking the maximum over \(x\) proves the tail-bound assertion. Finally, for a nonnegative random variable \(T_x\), Markov’s inequality gives \(\mathbb{P}(T_x>t)\le\mathbb{E}[T_x]/t\le C/t\) for \(t>0\). Taking \(t=\lceil C/\varepsilon\rceil\) makes \(C/t\le\varepsilon\), proving the stated estimate. \(\square\)
The tail in this theorem is the probability of not yet having met by time \(t\). It is not the probability of meeting at precisely time \(t\). Also, the bound is useful only to the extent that it holds uniformly over the starting states \(x\). A coupling estimate for one starting state alone does not establish a worst-case mixing bound.
Worked Coupling Bounds
Worked Example: A Common Reset Gives an Exact Mixing Profile
Let \(S=\{1,2,3\}\). At each step, with probability \(\tfrac12\), replace the state by a uniformly chosen state in \(S\); otherwise keep the current state. The transition matrix is \(P=\begin{bmatrix}\tfrac23&\tfrac16&\tfrac16\\\tfrac16&\tfrac23&\tfrac16\\\tfrac16&\tfrac16&\tfrac23\end{bmatrix}\). Each row sums to \(\tfrac23+\tfrac16+\tfrac16=1\), and the columns also sum to \(1\), so \(\pi=(\tfrac13,\tfrac13,\tfrac13)\) satisfies \(\pi P=\pi\).
Couple a chain from \(x\) and a chain from \(Y_0\sim\pi\) by using the same reset indicator and, on a reset, the same uniformly chosen state. If \(Y_0=x\), then \(T=0\). If \(Y_0\ne x\), the chains meet on their first reset. The probability of starting unequal is \(\tfrac23\), and the probability of no reset during the first \(n\) transitions is \((\tfrac12)^n\). Therefore, for every integer \(n\ge0\), \(\mathbb{P}(T>n)=\tfrac23(\tfrac12)^n\).
For a nonnegative integer-valued \(T\), \(\mathbb{E}[T]=\sum_{n\ge0}\mathbb{P}(T>n)\). Hence \(\mathbb{E}[T]=\tfrac23\sum_{n\ge0}(\tfrac12)^n=\tfrac23\cdot2=\tfrac43\). The coupling theorem gives \(d(n)\le\tfrac23(\tfrac12)^n\), where \(d(n)=\max_x\|P^n(x,\cdot)-\pi\|_{\mathrm{TV}}\).
Check by direct calculation: Write \(J\) for the matrix with every entry \(\tfrac13\). Here \(P=\tfrac12 I+\tfrac12J\), and \(J^2=J\), so \(P^n=2^{-n}I+(1-2^{-n})J\). Thus \(P^n(x,\cdot)=2^{-n}\delta_x+(1-2^{-n})\pi\). Since \(\|\delta_x-\pi\|_{\mathrm{TV}}=\tfrac12(|1-\tfrac13|+2|\tfrac13|)=\tfrac23\), the distance is exactly \(\tfrac23\,2^{-n}\). The coupling bound is sharp, including at \(n=0\), when the tail and the distance are both \(\tfrac23\).
Worked Example: Maximal Coupling and the Tail at One Step
On \(S=\{1,2,3\}\), consider a chain that resets to a uniform state with probability \(\tfrac14\), and otherwise stays put. Its transition matrix is \(P=\begin{bmatrix}\tfrac56&\tfrac1{12}&\tfrac1{12}\\\tfrac1{12}&\tfrac56&\tfrac1{12}\\\tfrac1{12}&\tfrac1{12}&\tfrac56\end{bmatrix}\). For each row, \(\tfrac56+\tfrac1{12}+\tfrac1{12}=1\); the columns have the same sum, so the uniform distribution \(\pi=(\tfrac13,\tfrac13,\tfrac13)\) is stationary.
A maximal coupling of two distributions is one that makes the probability of equality as large as possible. For distinct current states \(1\) and \(2\), their next-state distributions are \((\tfrac56,\tfrac1{12},\tfrac1{12})\) and \((\tfrac1{12},\tfrac56,\tfrac1{12})\). The common mass at states \(1,2,3\) is respectively \(\tfrac1{12},\tfrac1{12},\tfrac1{12}\), for total overlap \(\tfrac14\). A maximal coupling therefore meets on the next step with probability \(\tfrac14\). To see why this is maximal, any coupling can put probability at most \(\min\{\nu(j),\eta(j)\}\) on the event \(U=V=j\); summing over \(j\) bounds its equality probability by the total overlap. This bound is attained by assigning that common mass to equal pairs and coupling the remaining masses, whose supports are disjoint.
Now start \(X_0=x\) and \(Y_0\sim\pi\). If \(Y_0=x\), the chains are already together, an event of probability \(\tfrac13\). If \(Y_0\ne x\), use a maximal coupling for their next transitions; the probability of meeting at step one, conditional on distinct starting states, is \(\tfrac14\). Consequently, \(\mathbb{P}(T=1)=\tfrac23\cdot\tfrac14=\tfrac16\), while \(\mathbb{P}(T>1)=\tfrac23\cdot\tfrac34=\tfrac12\).
Check against the distance: The transition law from \(x\) can be written \(P(x,\cdot)=\tfrac34\delta_x+\tfrac14\pi\). Therefore \(\|P(x,\cdot)-\pi\|_{\mathrm{TV}}=\tfrac34\|\delta_x-\pi\|_{\mathrm{TV}}=\tfrac34\cdot\tfrac23=\tfrac12\). This equals \(\mathbb{P}(T>1)\), as the coupling inequality permits. In particular, using \(\mathbb{P}(T=1)=\tfrac16\) instead would incorrectly assert \(\tfrac12\le\tfrac16\). The relevant quantity is the tail \(\mathbb{P}(T>1)\), not the probability of meeting exactly at step one.
What Different Coupling Strategies Guarantee
A synchronous coupling uses the same randomness to update both chains. It can be simple and effective when the transition rule contracts distances, but sharing randomness alone does not ensure rapid meeting. A maximal one-step coupling chooses the joint next-state distribution to maximize the chance of equality for the current pair. A coalescent coupling additionally ensures that equality, once achieved, persists. These describe related but distinct properties: maximality concerns the next step, while coalescence concerns what happens after meeting.
For any two current states \(i,j\), the largest possible one-step meeting probability is \(\sum_{k\in S}\min\{p_{ik},p_{jk}\}=1-\|P(i,\cdot)-P(j,\cdot)\|_{\mathrm{TV}}\). The overlap argument in the preceding example proves the first equality as an attainable maximum; the second follows by expanding the finite-state total-variation formula. If this quantity is at least \(\alpha>0\) for every distinct pair, one can use a maximal coupling at each step and, after meeting, use identical transitions. Conditional on not having met yet, the chance of meeting at the next step is at least \(\alpha\). Thus, for any initial pair, \(\mathbb{P}(T>n+1)\le(1-\alpha)\mathbb{P}(T>n)\), and induction gives \(\mathbb{P}(T>n)\le(1-\alpha)^n\). The mixing theorem then yields \(t_{\mathrm{mix}}(\varepsilon)\le\lceil\log(\varepsilon)/\log(1-\alpha)\rceil\) for \(0<\alpha<1\). If \(\alpha=1\), every distinct pair can be coupled to meet in one step, so the same tail argument gives mixing by time \(1\). The hypothesis is substantive: if some distinct rows have disjoint support, their one-step overlap is zero, and this uniform geometric argument supplies no positive \(\alpha\).
Worked Example: Synchronous Updates Can Miss Available Overlap
Consider \(S=\{0,1,2\}\) and \(P=\begin{bmatrix}\tfrac12&\tfrac12&0\\0&\tfrac12&\tfrac12\\\tfrac12&0&\tfrac12\end{bmatrix}\). Each row sums to \(\tfrac12+\tfrac12+0=1\), \({0+\tfrac12+\tfrac12=1}\), and \(\tfrac12+0+\tfrac12=1\). The columns each sum to \(1\), so direct multiplication gives \(\pi P=(\tfrac13,\tfrac13,\tfrac13)P=(\tfrac13,\tfrac13,\tfrac13)=\pi\).
Start two chains at \(0\) and \(1\). For a synchronous inverse-CDF update, take one uniform random variable \(U\) on \([0,1]\) for both chains, and assign outcomes in the order \(0,1,2\). If \(0\le U<\tfrac12\), the chain at \(0\) goes to \(0\) and the chain at \(1\) goes to \(1\). If \(\tfrac12\le U\le1\), the first goes to \(1\) and the second goes to \(2\). The endpoints have probability zero, and in either interval the two next states differ. Thus this synchronous coupling has zero probability of meeting in one step.
But the next-state distributions from \(0\) and \(1\) overlap at state \(1\) with mass \(\min\{\tfrac12,\tfrac12\}=\tfrac12\). A maximal coupling can assign probability \(\tfrac12\) to the equal pair \((1,1)\), and the remaining masses pair \((0,2)\) with probability \(\tfrac12\). It therefore meets in one step with probability \(\tfrac12\). After any meeting, choose identical transitions to make the coupling coalescent.
Check: The synchronous calculation has meeting probability \(0\), while the overlap calculation gives maximal meeting probability \(\tfrac12\). Neither contradicts the marginal transition rules: both copies in each construction have their prescribed rows of \(P\). The difference is the choice of joint update, which does not appear in either marginal row.
Limits of the Bound and a Common Pitfall
A uniform coupling-time tail tending to zero guarantees convergence to \(\pi\), whether or not convergence was established by another method: the theorem gives \(d(t)\le g(t)\to0\). Conversely, a bound for only one starting state says nothing by itself about the worst-case mixing time. Nor does the existence of a stationary distribution alone guarantee convergence. For example, the two-state chain with \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\) has stationary distribution \((\tfrac12,\tfrac12)\), but from state \(0\) its distribution alternates between \(\delta_0\) and \(\delta_1\), each at total-variation distance \(\tfrac12\) from stationarity. There can be no coalescent coupling with a stationary start whose meeting-time tail tends to zero for this initial state, since the coupling inequality would then force the distance to tend to zero.
Common pitfall: confusing an exact-time probability with a tail probability. In the reset example with reset probability \(\tfrac14\), the stationary-start maximal coupling has \(\mathbb{P}(T=1)=\tfrac16\), but its one-step distance is \(\tfrac12\). The valid comparison is \(\|P(x,\cdot)-\pi\|_{\mathrm{TV}}=\tfrac12\le\mathbb{P}(T>1)=\tfrac12\), not \(\tfrac12\le\mathbb{P}(T=1)\). Always identify the event that the coupling inequality uses: the chains have not met by the time being considered.
Check Your Understanding
For each question, distinguish the coupling construction from the marginal chain and use the meeting-time tail in any mixing bound.
- For a coalescent coupling started at \(X_0=x\), \(Y_0\sim\pi\), explain why \(X_t\ne Y_t\) is the event \(T>t\), including the case \(T=0\).
- If \(\mathbb{P}(T_x>n)\le 3( \tfrac14)^n\) for every state \(x\), what integer \(n\) does this bound give for accuracy \(\varepsilon=\tfrac1{16}\)?
- For two transition rows \((\tfrac34,\tfrac14)\) and \((\tfrac14,\tfrac34)\), calculate their overlap and the maximal one-step meeting probability.
- Why does a bound on \(\mathbb{P}(T=t)\) alone not yield the coupling inequality at time \(t\)?
- Give one reason a synchronous coupling can have a smaller one-step meeting probability than a maximal coupling.