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

Center the board at the origin and map each white square $(i,j)$ toThe white squares become the integer points of the diamondand a bishop move changes exactly one coordinate. From $(u,v)$ the chain can move first to $(u,0)$ and then to $(0,0)$, since both points lie in $D_n$. Reversing such paths connects any two states, so the bishop random walk is an irreducible Markov chain.

Solved by gpt-5.6-sol high.

In the diamond coordinates, the horizontal line through $(u,v)$ has $2(n-|u|)+1$ points and the vertical line has $2(n-|v|)+1$ points. There is a numerical constant $a>0$, independent of $n$ and of the starting point, such that the walk enters the middle diamond $D_{n/2}$ within two steps with probability at least $a$. To see this, suppose $|u|\le |v|$, so $|u|\le n/2$. With probability at least $1/2$ the first move uses the longer horizontal line, and a fixed positive fraction of its choices have $|v^{\prime }|\le n/4$. From $(u,v^{\prime })$, the vertical line has length at least $3n/2$, is chosen with probability bounded below, and a fixed positive fraction of its points satisfy $|u^{\prime }|+|v^{\prime }|\le n/2$. The case $|v|\le |u|$ is symmetric.

Now couple two copies. Independently use the preceding construction until both lie in $D_{n/2}$, an event having probability at least $a^2$ in two steps. From $(u,v)$ and $(u^{\prime },v^{\prime })$ in that diamond, their horizontal line ranges overlap in at least $n+1$ values. A maximal coupling of the next moves can therefore, with probability bounded below, send them to $(u,w)$ and $(u^{\prime },w)$ for the same $|w|\le n/2$. Their vertical lines are then identical, and another maximal coupling makes the two states equal with probability bounded below. Thus there are constants $k$ and $b>0$, independent of $n$, for which the two copies coalesce during every block of $k$ steps with conditional probability at least $b$.

The coupling time consequently has a geometric tail. By the coupling inequality for total variation, for each fixed $0<\epsilon <1$,Since a nontrivial chain has mixing time bounded below by a positive constant, the mixing time has constant order.

Solved by gpt-5.6-sol high.

For every $A\subseteq [n]$, define the Walsh characterThese $2^n$ functions form an orthonormal basis. For the lazy walk, which stays put with probability $1/2$ and otherwise flips a uniformly chosen coordinate,Hence the eigenvalue $1-k/n$ has multiplicity $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, for $0\le k\le n$.

The supplied spectral upper bound for total variation mixing givesAt $t=\frac{1}{2}n\log n+Cn$, the last expression is $e^{e^{-2C}}-1$. Choosing $C=C(\epsilon )$ so that this is at most $4{\epsilon }^2$ proves

Solved by gpt-5.6-sol high.

Assume without loss of generality that $\mu (f)-\nu (f)=r\sigma$ and let $m=(\mu (f)+\nu (f))/2$. By Chebyshev inequality,Using the event $\{f\ge m\}$ in the variational definition of total variation distance gives

Start the lazy hypercube walk at $0^n$ and writeThis is an eigenfunction with eigenvalue $1-1/n$, soThe stated variance estimates allow the preceding lemma with $\sigma =\sqrt{n}$ andFor $t=\frac{1}{2}n\log n-Cn$, $r^2$ is bounded below by a constant multiple of $e^{2C}$, uniformly for all sufficiently large $n$. Choosing $C=C(\epsilon )$ so that $1-8/r^2>\epsilon$, and absorbing finitely many small $n$ into the constant, proves

Solved by gpt-5.6-sol high.

The urn count $X_t^{(n)}$ is the lumped Markov chain obtained from the lazy hypercube walk by recording its Hamming weight. Starting from $0^n$, the hypercube law is uniform on every Hamming sphere, as is its stationary law conditional on the sphere. Consequently the total variation distance of the full walk from stationarity equals that of its Hamming-weight projection.

Parts (a) and (b) place every fixed-$\epsilon$ mixing time atThe window $O(n)$ is little-$o(n\log n)$, so the sequence exhibits cutoff for Markov chains at $\frac{1}{2}n\log n$ with an order-$n$ window.

Solved by gpt-5.6-sol high.

The Dirichlet form of a Markov chain isWhen $P$ is reversible, this equals $⟨f,(I-P)g{⟩}_{\pi }$.

Solved by gpt-5.6-sol high.

For a finite reversible lazy chain, the relaxation time is $t_{\mathrm{rel}}=1/\gamma$, where $\gamma =1-{\lambda }_2$ is the spectral gap. Its spectral profile isThe variational characterization of the spectral gap isEvery class $c_0^{+}(A)$ is contained in the class over which this last infimum is taken, so $\lambda (A)\ge \gamma$ and $\Lambda (r)\ge \gamma$. Therefore

Solved by gpt-5.6-sol high.

Let $N=|V_n|$. Since the degrees lie between $1$ and $\Delta$,The Generalized Cheeger inequality and ${\Phi }_{\ast }(u)\ge {\Phi }_{\ast }(c)\ge \alpha$ for $u\le c$ giveFor all larger $u$, part (a) gives $\Lambda (u)\ge 1/t_{\mathrm{rel}}$. Split the supplied spectral-profile integral at $c$ to obtain

Solved by gpt-5.6-sol high.

Under the standard intended reading that the added edges form a perfect matching between $G_n$ and $H_n$, the claim follows as follows. Degrees in $M_n$ remain bounded in terms of $\Delta$. For $A\subseteq V(M_n)$, write $A_G=A\cap V(G_n)$ and $A_H=A\cap V(H_n)$. The matching contributes at least $||A_G|-|A_H||$ boundary edges, while expansion inside $G_n$ contributes a constant multiple of $\min \{|A_G|,n-|A_G|\}$. A case split according as $|A_G|\le n/2$ or $|A_G|>n/2$ showsThus $M_n$ has a uniform Cheeger constant. Cheeger inequality gives a uniformly bounded relaxation time, while ${\pi }_{\min }\asymp 1/n$. The usual spectral mixing estimate, or part (b), then gives $t_{\mathrm{mix}}\lesssim \log n$.

If “adding $n$ edges” permits all $G_n$ vertices to attach to the same vertex of $H_n$, the assertion is false as written. Take $H_n$ to be a path and attach every vertex of the expander to one endpoint. A walk started at the other endpoint needs order $n^2$ time to reach the attachment endpoint, so its mixing time is not $O(\log n)$. The perfect-matching interpretation is therefore necessary.

Solved by gpt-5.6-sol high.

For a path $\gamma =(v_0,e_1,v_1,\dots ,e_k,v_k)$, its $\ell$-length is ${\sum }_{j=1}^k\ell (e_j)$. The corresponding path metric isBecause every edge length is at least one, $\rho (x,y)\ge 1$ whenever $x\ne y$.

Solved by gpt-5.6-sol high.

Let $D={\max }_{x,y}\rho (x,y)$ and let $\pi$ be the invariant distribution. Iterating the assumed Wasserstein contraction givesSince $\rho (x,y)\ge 1_{\{x\ne y\}}$, the coupling characterization of total variation distance impliesThe right side is at most $\epsilon$ whenwhich proves the claimed mixing bound.

Solved by gpt-5.6-sol high.

For any two states $X,Y$, the closed neighbourhood of $X\cup Y$ has at most $2s(\Delta +1)\le 2n/3$ vertices. The remaining induced graph therefore has at least $n/3$ vertices and maximum degree at most $\Delta$, so the greedy independent-set bound supplies an independent set $Z$ of size $s$ there. No vertex of $Z$ is adjacent to a vertex of $X\cup Y$. Replace the elements of $X$ one at a time by the elements of $Z$, and then replace the elements of $Z$ one at a time by those of $Y$. Every intermediate set is independent, and every prescribed swap has positive transition probability. Hence the chain is irreducible.

Solved by gpt-5.6-sol high.

If distinct states $X,Y$ communicate in one step, they differ by a unique removed vertex and a unique inserted vertex. ConsequentlyThus the transition matrix is symmetric, so detailed balance holds for the uniform distribution on $S$. Irreducibility makes this invariant distribution unique.

Solved by gpt-5.6-sol high.

Give the state graph the unit-edge path metric. The construction in part (i) shows that its diameter is at most $2s$. It remains to couple one step from neighbouring states $X=A\cup \{x\}$ and $Y=A\cup \{y\}$.

Pair the choice $x$ in the first chain with $y$ in the second, and pair every $a\in A$ with itself; use the same proposed vertex $v$ in both chains. When the pair $(x,y)$ is removed, the chains coalesce whenever $v$ is not in the closed neighbourhood of $A$. This has probability at leastWhen a common $a\in A$ is removed, the distance can increase from one to at most two only if $v$ lies in one of the closed neighbourhoods of $x$ and $y$, an event of probability at mostThereforewhere the last inequality uses $n\ge 3s(\Delta +1)$. The Path coupling theorem extends this contraction to arbitrary starting distributions. Since $1-1/(sn)\le e^{-1/(sn)}$, part (a) with diameter at most $2s$ yields

Solved by gpt-5.6-sol high.