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

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.