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

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.