= Solution
Writing $a=|A\setminus B|$ and $b=|B\setminus A|$ gives
$$
\rho(A,B)=\frac{a+b+|a-b|}{2}=\max(a,b).
$$
Make 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 gives
$$
\mathbb E_{A,B}\rho(X_1,Y_1)
\leq\left(1-\frac1{2n}\right)\rho(A,B).
$$
The <Path coupling theorem> extends this to all pairs. Since $\operatorname{diam}(V)=k$, part (a), with $\alpha\geq1/(2n)$ up to an absolute constant, gives
$$
t_{\mathrm{mix}}(\varepsilon)\lesssim
n\bigl(\log k+\log(1/\varepsilon)\bigr)
\lesssim n\log(k/\varepsilon).
$$
Back to article page
