Assume without loss of generality that $\mu(f)-\nu(f)=r\sigma$ and let $m=(\mu(f)+\nu(f))/2$. By <Chebyshev inequality>,
$$
\mu(f<m)\leq\frac4{r^2},
\qquad
\nu(f\geq m)\leq\frac4{r^2}.
$$
Using the event $\{f\geq m\}$ in the variational definition of <total variation distance> gives
$$
\lVert\mu-\nu\rVert_{\mathrm{TV}}
\geq1-\frac8{r^2}.
$$

Start the lazy hypercube walk at $0^n$ and write
$$
\Phi(x)=\sum_{i=1}^n(-1)^{x_i}=n-2\sum_{i=1}^nx_i.
$$
This is an eigenfunction with eigenvalue $1-1/n$, so
$$
\mathbb E_0\Phi(X_t)=n(1-1/n)^t,
\qquad \mathbb E_\pi\Phi=0.
$$
The stated variance estimates allow the preceding lemma with $\sigma=\sqrt n$ and
$$
r=\sqrt n(1-1/n)^t.
$$
For $t=\tfrac12n\log n-Cn$, $r^2$ is bounded below by a constant multiple of $e^{2C}$, uniformly for all sufficiently large $n$. Choosing $C=C(\varepsilon)$ so that $1-8/r^2>\varepsilon$, and absorbing finitely many small $n$ into the constant, proves
$$
t_{\mathrm{mix}}(\varepsilon)geq\frac12n\log n-C(\varepsilon)n.
$$

Solved by gpt-5.6-sol high.

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-215/2/b/solution