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

A randomized stopping time $\tau$ is a strong stationary time whenfor every initial state $x$, state $y$, and time $t$. Equivalently, $X_{\tau }$ has distribution $\pi$ and is independent of $\tau$.

One shuffle removes the ordered top $k$ cards and inserts them, in a uniformly random person-order, into successively chosen uniform slots. The transition rule depends on a deck only through relabeling of its cards, so its transition matrix on the symmetric group is doubly stochastic. Hence the uniform distribution on all $n!$ permutations is invariant.

Reverse time under the uniform invariant law. The reverse shuffle selects $k$ cards uniformly without replacement and moves them to the top in random order. Track cards once selected. The forward time $\tau$ at which the initially bottom card first lies among the next top $k$ corresponds in reverse to the first time every card has been selected. At that coupon-collector time, the order of all marked cards is uniform and independent of the marking time, by induction over the random insertions. Reversing again shows that $X_{\tau }$ is uniform and independent of $\tau$, so part (a) makes $\tau$ a strong stationary time.

In the reverse description, a fixed card avoids selection in one shuffle with probability $1-k/n$. After $t$ shuffles, a union bound givesFor a strong stationary time, the separation distance and hence total variation distance at time $t$ are at most $\mathbb{P}(\tau >t)$. Takingmakes this at most $\epsilon$. Since $k\ge 1$, the second term is at most $C(\epsilon )n$, proving

With stationary flow $Q(x,y)=\pi (x)P(x,y)$, the conductance of a Markov chain is $\Phi (A)=Q(A,A^c)/\pi (A)$. The bottleneck ratio and isoperimetric profile are

No transition joins distinct $A_i$, soConsequently

The graph has $\asymp n^4$ vertices, bounded degrees, and stationary masses $\asymp n^{-4}$. Split any set into components that do not communicate in one step and use part (a)(ii). A connected component of stationary mass $r\le 1/2$ has $O(r{n}^4)$ vertices. The planar grid isoperimetric bound supplies at least $c\sqrt{r{n}^4}$ boundary edges unless the component fills most of one layer; in that case the $\asymp n^2$ interlayer edges give the same order. ThusThe conductance-profile mixing bound for a lazy chain now givesHere ${\Phi }_{\ast }\gtrsim n^{-2}$ also gives $t_{\mathrm{rel}}\lesssim n^4$ by Cheeger inequality. Hence $t_{\mathrm{mix}}\lesssim n^4$.

Choose a shortest path $x=x_0,\dots ,x_m=y$. Glue the prescribed one-step edge couplings successively. The triangle inequality for the Wasserstein transportation metric givesNow couple initial states $(U,V)$ optimally for $\mu ,\nu$ and conditionally use these one-step couplings. Taking expectations and then the infimum givesIteration with $\nu =\pi$ yields ${\rho }_K(P^t(x,\cdot ),\pi )\le e^{-\alpha t}\mathrm{diam}(V)$. Since this metric dominates total variation, it is at most $\epsilon$ once

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

For $0<\alpha ,\epsilon <1$, defineA hit${}_{\alpha }$ cutoff means that for every fixed $0<\epsilon <1/2$,For finite reversible chains, mixing-time cutoff implies hit${}_{1/2}$ cutoff; this is the hitting-time characterization of cutoff.

Both chains are reversible. Since $G$ is $d$-regular, simple random walk $X$ is reversible with uniform invariant distribution. In the weighted graph every vertex has total incident weight $d+\theta$, so $Y$ is also reversible with the same uniform invariant distribution.

Writewhere $M$ traverses the added perfect matching. The standard rare-transition robustness theorem for reversible chains says that when $t_{\mathrm{rel}}=o(t_{\mathrm{mix}})$, adding a bounded-degree kernel at rate $q\asymp 1/t_{\mathrm{mix}}$ cannot create cutoff: if the original chain's mixing window is a nonvanishing fraction of its mixing time, the perturbed chain retains such a window. The proof couples the chains between matching jumps; the geometric waiting time for those jumps has mean $\asymp t_{\mathrm{mix}}$ and nonconcentrated fluctuations, while the $X$ segments retain the original noncutoff profile. Therefore cutoff of $Y$ would imply cutoff of $X$, contrary to hypothesis. Hence $Y$ does not exhibit cutoff.

Thomson principle states that the effective resistance is the minimum energy of a unit flow from $a$ to $z$:An edge cutset separating $a$ and $z$ is a set of edges whose removal disconnects them. Every unit flow has net flux one across each such cutset ${\Pi }_k$. By Cauchy-Schwarz inequality,For disjoint cutsets, summing these energy lower bounds and applying Thomson's principle gives the Nash-Williams inequalityThe commute time identity is

There are $\asymp n^3$ edges. The $n^2$ horizontal cutsets between successive rows perpendicular to the long direction are disjoint and each contains $\asymp n$ unit-conductance edges. Nash-Williams inequality givesConversely, spread a unit flow nearly uniformly across the width $n$ while moving it through the $n^2$ long-direction layers, with bounded extra energy to fan out from and collect at the two corner vertices. Its energy is $O(n^2/n)+O(\log n)=O(n)$, so Thomson's principle gives the matching upper bound $R_{\mathrm{eff}}\asymp n$.

The graph is invariant under a half-turn exchanging the two corners, so the two directional hitting-time expectations are equal. The commute time identity therefore yields