Coupling Bounds for Graph Random Walks

Coupling as a Comparison of Two Walks

A random walk can be studied by comparing two copies of the same chain, started from different vertices and advanced jointly. The joint evolution is called a coupling when each coordinate, considered on its own, has the transition probabilities of the original walk. If the two coordinates agree with high probability, their distributions cannot be far apart. This gives a way to bound mixing without computing every distribution at every time.

Throughout, let \(G=(V,E)\) be a finite, connected, simple graph with at least two vertices. Its lazy simple random walk stays at its current vertex with probability \(1/2\), and with probability \(1/2\) chooses a neighbor uniformly. Its transition matrix is \(P\). Thus \(P(v,v)=1/2\), and for each neighbor \(w\) of \(v\), \(P(v,w)=1/(2\deg(v))\); all other entries are zero. The stationary distribution is \(\pi(v)=\deg(v)/(2|E|)\). We use the standard facts that this distribution is stationary and that the lazy walk on a finite connected graph converges to it.

For probability distributions \(\mu,\nu\) on \(V\), their total variation distance is \(\|\mu-\nu\|_{\mathrm{TV}}=\frac12\sum_{z\in V}|\mu(z)-\nu(z)|\). Equivalently, it is \(\max_{A\subseteq V}|\mu(A)-\nu(A)|\). The mixing time at tolerance \(0<\varepsilon<1\) is \(t_{\mathrm{mix}}(\varepsilon)=\min\{t\geq0:\max_{x\in V}\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}\leq\varepsilon\}\).

Proof. For any \(A\subseteq V\), the difference between \(\Pr(X\in A)\) and \(\Pr(Y\in A)\) is bounded in absolute value by the probability that exactly one of \(X,Y\) belongs to \(A\). That event is contained in \(\{X\ne Y\}\), so \(|\mu(A)-\nu(A)|\leq\Pr(X\ne Y)\). Taking the maximum over \(A\) gives the result. \(\square\)

In particular, if \(X_0=x\), \(Y_0\) has distribution \(\pi\), and \(Y_t\) remains stationary, then \(\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}\leq\Pr(X_t\ne Y_t)\). A coalescing coupling therefore turns a meeting-time tail bound into a mixing bound.

Maximal Coupling and Common Transition Mass

For two probability distributions \(\mu,\nu\), the quantity \(\sum_z\min\{\mu(z),\nu(z)\}\) is their common mass. A maximal coupling makes the two variables equal with probability exactly this amount. To construct one, put mass \(\min\{\mu(z),\nu(z)\}\) on the diagonal pair \((z,z)\) for each \(z\). The remaining mass in each marginal has the same total, and the two residual distributions have disjoint support. Couple those residual distributions in any way. If the common mass is \(1\), the variables are equal with probability \(1\).

Applied to two rows \(P(x,\cdot)\) and \(P(y,\cdot)\), this construction gives a joint next step for walks currently at \(x,y\). If they are already together, set their next positions equal using one transition from that row. Otherwise, use a maximal coupling. Repeating this rule gives a coalescing coupling: when a step succeeds the walks meet, and thereafter they move together.

Proof. Conditional on the walks not having met by time \(t\), their current states are distinct, and the next-step maximal coupling makes them equal with probability at least \(a\). Thus \(\Pr(T>t+1\mid T>t)\leq1-a\) whenever \(\Pr(T>t)>0\). Multiplying this conditional bound successively gives \(\Pr(T>t)\leq(1-a)^t\); if a conditioning event has probability zero, the bound for later times holds automatically. At \(t=0\), the probability is at most \(1=(1-a)^0\), including the case of equal starting states. \(\square\)

Block Couplings and Bounds at Every Time

For some chains, one-step overlap is small or zero, while several steps give substantial common mass. Fix an integer \(k\geq1\) and define \(\alpha_k=\min_{x,y\in V}\sum_z\min\{P^k(x,z),P^k(y,z)\}\). The minimum is over all pairs of states, including \(x=y\). When \(\alpha_k>0\), the \(k\)-step transition rows can be coupled to agree at the end of a block with probability at least \(\alpha_k\).

Proof. Consider only the chains sampled at times \(0,k,2k,\ldots\); this is a Markov chain with transition matrix \(P^k\). At each block time, maximally couple the two \(P^k\)-transitions. If the endpoint states agree, couple all subsequent block endpoints identically. From any pair of block states the chance of agreement at the next block endpoint is at least \(\alpha_k\), so the probability of disagreement after \(q\) blocks is at most \((1-\alpha_k)^q\), by the same conditional-probability argument as above.

Start one block chain at \(x\) and the other with initial distribution \(\pi\). Stationarity makes the second chain's distribution \(\pi\) at every block time. The coupling inequality therefore gives the asserted bound at \(t=qk\). For the remaining \(s\) steps, where \(t=qk+s\) and \(0\leq s<k\), use contraction of total variation: for any distributions \(\mu,\nu\), \(\|\mu P^s-\nu P^s\|_{\mathrm{TV}}\leq\|\mu-\nu\|_{\mathrm{TV}}\). Indeed, for each set \(A\), \((\mu P^s)(A)-(\nu P^s)(A)=\sum_z(\mu(z)-\nu(z))P^s(z,A)\), and \(0\leq P^s(z,A)\leq1\); maximizing over \(A\) is bounded by the total variation distance of \(\mu,\nu\). Apply this with \(\nu=\pi\), for which \(\pi P^s=\pi\), to obtain the bound at \(qk+s\). Choosing \(q\) so that \((1-\alpha_k)^q\leq\varepsilon\) gives the mixing-time estimate. If \(\alpha_k=1\), any two endpoint distributions have common mass 1 and hence are identical, so the chain is stationary from every initial state after \(k\) steps. \(\square\)

This argument couples block endpoints. It does not assert that the walks meet, or remain together, at times inside a block. The contraction step is what extends the total variation estimate to times between block endpoints; it does not turn the block construction into a coalescing coupling of the original walks.

What the Bounds Do—and Do Not—Say

The common-mass calculation is useful because it converts a transition table into a quantitative estimate. On a small graph, one can compute \(P^k\), compare every pair of rows, and use the smallest overlap as \(\alpha_k\). A larger overlap yields a faster geometric decay in the block count. When the graph is regular, the stationary distribution is uniform, but the coupling argument itself does not require regularity.

A meeting-time bound and a mixing-time bound are related, but they are not interchangeable without specifying the coupling. The one-step construction on \(P_3\) was coalescing at every time and gave a meeting-time tail. The block construction couples the sampled chain with transition matrix \(P^k\). It proves agreement at block endpoints only; conditional path choices inside a block could meet and then separate. To bound mixing at intermediate times, use total-variation contraction, as proved above, rather than claiming a meeting at those times.

Common pitfall: adding the wrong overlap entries. For rows \((3/8,1/2,1/8)\) and \((1/8,1/2,3/8)\), the minima are \((1/8,1/2,1/8)\). Their sum is \(1/8+1/2+1/8=3/4\). The common mass is not \(5/8\). Also, the overlap of one selected pair is not a uniform bound: to use \(\alpha_k\), take the minimum over every pair of starting states.