= Solution
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.
Back to article page
