Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 215 / 4

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.