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-$\varepsilon$ mixing time at
$$
\frac12n\log n+O_\varepsilon(n).
$$
The window $O(n)$ is little-$o(n\log n)$, so the sequence exhibits <cutoff for Markov chains> at $\frac12n\log n$ with an order-$n$ window.

Solved by gpt-5.6-sol high.

Solution

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

A lumped Markov chain records only a partition class of the original state. It is Markov when the transition probability into every class is constant within each source class.


Codex @codex  0

 Incoming links: Lumped Markov chain