Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 215 (Mixing Times of Markov Chains)

Start the random-to-top card shuffle from a fixed ordering and let $T$ be the first time every card has been selected. Once a card has been selected, its location relative to the other selected cards is determined by their most recent selection times. At $T$ these times have a uniformly random strict order, so the deck is uniform and independent of the event $\{T=t\}$. Thus $T$ is a strong stationary time, andThe coupon collector problem gives $T=n\log n+O_{\mathbb{P}}(n)$, so for $c\to \infty$,

Before all cards have been selected, the unselected cards form the bottom block of the deck in their original relative order. At time $n\log n-cn$, with $c\to \infty$ sufficiently slowly, the number $U$ of unselected cards tends to infinity in probability. Choose $k\to \infty$ with $\mathbb{P}(U\ge k)\to 1$. The bottom $k$ cards are then in their original relative order, whereas under the uniform distribution this has probability $1/k!$. HenceThe random-to-top shuffle therefore has cutoff for Markov chains at $n\log n$ with window $O(n)$.

The top-to-random card shuffle is the time reversal of the random-to-top card shuffle under the uniform stationary distribution. Equivalently, their step distributions on the symmetric group are carried into one another by permutation inversion, which preserves total variation from uniform. Their mixing profiles agree, so top-to-random has the same cutoff at $n\log n$ with window $O(n)$.

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

Couple two noisy voter model chains by choosing the same update vertex, the same refresh coin and refreshed spin, and, for a voter update, the same chosen neighbor. Let $D_t$ be their Hamming distance. If $G$ is $r$-regular, conditioning on the current disagreement set givesbecause every disagreeing vertex is counted in exactly $r$ neighbor sets. ThereforeThe coupling inequality for total variation and $1_{\{{\sigma }_t\ne {\sigma }_t^{\prime }\}}\le D_t$ give

For a nonregular graph, use the degree-weighted Hamming metricUnder the same coupling,Here the final double sum equals ${\sum }_{u\in D_t}\mathrm{deg}(u)=W_t$. Since $W_0\le {\sum }_v\mathrm{deg}(v)=2|E|$ and $W_t\ge 1$ whenever the chains differ,

Let $P$ be a finite reversible Markov chain with stationary distribution $\pi$, and write $Q(e)=\pi (u)P(u,v)$ for an oriented transition edge $e=(u,v)$. For every ordered pair $(x,y)$ choose a directed path ${\gamma }_{xy}$ from $x$ to $y$ using positive-capacity edges, and define the congestionThen the Canonical paths comparison theorem gives the Poincare inequalityfor every real function $f$, and hence the spectral gap is at least $1/\rho$.

Indeed,Write each difference as the sum of edge differences along ${\gamma }_{xy}$ and apply Cauchy-Schwarz inequality:Interchanging the pair and edge sums, then applying the definition of $\rho$, bounds the result by

Letand choose $x$ attaining the maximum. For every $t$, the Strong Markov property at time $t$ givesThusIf $t\ge t_{\mathrm{mix}}(1/4)$, thenSince $\{X_t\in A\}\subseteq \{T_A\le t\}$, this is impossible when $t<m/4$. Allowing for integer times, one may take any smaller absolute constant, for example