 Path coupling theorem

The Path coupling theorem reduces a global contraction calculation to pairs joined by one edge in a connected state graph. Let $d$ be the shortest-path metric from positive edge lengths, and let $P$ be a transition matrix on this finite state space. Suppose every adjacent pair $x,y$ admits a coupling $(X^{\prime },Y^{\prime })$ of $P(x,\cdot )$ and $P(y,\cdot )$ such thatThen the Wasserstein distance associated with $d$ satisfiesfor all initial probability distributions $\mu ,\nu$. Along a shortest path between two states, the triangle inequality for Wasserstein distance sums the adjacent-pair bounds to give the same bound for that pair. Averaging over a coupling of the initial states gives the distribution-level inequality. Iteration yields contraction by ${\alpha }^t$.^[ref]

If $\pi$ is stationary, $d_{\min }={\min }_{x\ne y}d(x,y)>0$, and $D={\max }_{x,y}d(x,y)$, the coupling bound givesFor example, on $m$ bits choose one coordinate uniformly and replace it by a fair bit. Couple two configurations by choosing the same coordinate and replacement. A one-bit disagreement disappears with Probability $1/m$, so the Hamming distance contracts by $1-1/m$. Here $D=m$, $d_{\min }=1$, giving the explicit bound $m(1-1/m{)}^t$. The strength is that only one-bit differences had to be analyzed.