Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 215 / 2

The chain is a random walk on the finite abelian group $(\mathbb{Z}/n\mathbb{Z}{)}^d$, so its stationary distribution is uniform and its characters diagonalize the transition operator. For one coordinate and $\theta =2\pi k/n$, the eigenvalue isUniformly in $p\in [0,1]$,for an absolute $c>0$. Hence the one-coordinate chi-squared distance after $t\ge n^2$ is at most $C{e}^{-ct/n^2}$. The coordinates evolve independently, so the product formula for chi-squared distance givesThe chi-squared divergence bound on total variation distance now yieldsuniformly in $p_1,\dots ,p_d$.

For $d=1$, the first nonconstant character has eigenvalue modulus $1-O(n^{-2})$, uniformly in $p$. Testing against its real or imaginary part gives a fixed positive total-variation distance until time $c{n}^2$. Thus

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 displacementStandard exponential concentration for sums of bounded independent increments shows that for every fixed $C>6$ the one-coordinate coupling time $\tau$ satisfiesAll other initial states lie between the extremal copies. Coupling the $d$ coordinates independently and using the union bound givesbecause $\log d=o(n)$. The coupling inequality for total variation therefore gives

Take $d=1$ and start from the lower endpoint. The stationary distribution of this birth-death chain satisfies detailed balance withso it is concentrated within $O(1)$ of the upper endpoint $n$. Before reaching that region the walk has drift $1/6$. The weak law of large numbers and exponential concentration therefore imply that its hitting time of $n-O(1)$ isAt time $(6-\epsilon )n$ the chain is still macroscopically below the stationary region with probability tending to one, so its total-variation distance tends to one. Under the monotone coupling from part (b), by time $(6+\epsilon )n$ the extremal copies have coalesced with probability tending to one, so the distance tends to zero. Therefore the family has