= Solution
Use the monotone grand coupling in every coordinate: at each step use the same attempted move for chains started from the bottom and top states, censoring moves that leave the interval. The two copies coalesce after the lower copy has accumulated enough upward drift and boundary censoring has removed their initial separation. Away from the boundary, one step has mean displacement
$$
\frac13-\frac16=\frac16.
$$
Standard exponential concentration for sums of bounded independent increments shows that for every fixed $C>6$ the one-coordinate coupling time $\tau$ satisfies
$$
\mathbb P(\tau>Cn)\leq e^{-c_Cn}.
$$
All other initial states lie between the extremal copies. Coupling the $d$ coordinates independently and using the <union bound> gives
$$
\mathbb P(\text{some coordinate has not coupled by }Cn)
\leq d e^{-c_Cn}=o(1),
$$
because $\log d=o(n)$. The <coupling inequality for total variation> therefore gives
$$
\boxed{t_{\mathrm{mix}}=O(n).}
$$
Back to article page
