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

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