Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 215 / 3

Choose a shortest path $x=x_0,\dots ,x_m=y$. Glue the prescribed one-step edge couplings successively. The triangle inequality for the Wasserstein transportation metric givesNow couple initial states $(U,V)$ optimally for $\mu ,\nu$ and conditionally use these one-step couplings. Taking expectations and then the infimum givesIteration with $\nu =\pi$ yields ${\rho }_K(P^t(x,\cdot ),\pi )\le e^{-\alpha t}\mathrm{diam}(V)$. Since this metric dominates total variation, it is at most $\epsilon$ once

Writing $a=|A\setminus B|$ and $b=|B\setminus A|$ givesMake two states adjacent when one can pair every disagreement except at most one, equivalently when $\rho =1$, and give every such edge length one. Pairing a deletion with an insertion as a swap and then handling the excess disagreements constructs a path of length $\max (a,b)$; every edge changes $\rho$ by at most one, so this is the corresponding path metric.

For adjacent states, couple the lazy coin and coordinate choices so that a distinguished disagreement is removed whenever its coordinate is selected, matching a compensating coordinate in the swap case. A direct check of the nested and equal-cardinality cases givesThe Path coupling theorem extends this to all pairs. Since $\mathrm{diam}(V)=k$, part (a), with $\alpha \ge 1/(2n)$ up to an absolute constant, gives