= Solution
Let $m\geq2$ be the number of states and put
$$
r=\max_{2\leq j\leq m}|\lambda_j|,\qquad
\boxed{\gamma_*=1-r,\qquad t_{\mathrm{rel}}=\gamma_*^{-1}.}
$$
The <absolute L2 spectral gap of a reversible Markov chain> is $\gamma_*$; in this question the <relaxation time> means the <absolute relaxation time>. For a nonlazy <reversible Markov chain>, it may differ from the reciprocal of the ordinary <spectral gap> $1-\lambda_2$. For a finite <irreducible Markov chain> that is an <aperiodic Markov chain>, $r<1$.
For $r>0$, choose a real <eigenfunction> $f$ whose <eigenvalue> has modulus $r$, and an initial state $x$ maximizing $|f(x)|=\|f\|_\infty$. It has $\pi(f)=0$, and the definition of <total variation distance> implies
$$
r^t\|f\|_\infty=|P^tf(x)-\pi(f)|\leq2\|f\|_\infty\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}.
$$
This is the <eigenvalue lower bound for total variation mixing>, $d(t)\geq r^t/2$. At $t=t_{\mathrm{mix}}(\varepsilon)$, for $0<\varepsilon<1/2$,
$$
t\geq\frac{\log(1/(2\varepsilon))}{-\log r}\geq\frac{r}{1-r}\log\frac1{2\varepsilon}.
$$
The second inequality follows from $-r\log r\leq1-r$, the supplied inequality with $x=1-r$. Since $r/(1-r)=t_{\mathrm{rel}}-1$,
$$
\boxed{(t_{\mathrm{rel}}-1)\log\frac1{2\varepsilon}\leq t_{\mathrm{mix}}(\varepsilon).}
$$
When $r=0$ the left side is zero, so no logarithm of zero is needed. For $\varepsilon\geq1/2$ the left side is nonpositive and the conclusion is automatic. A one-state chain has <mixing time> zero; with the convention $\gamma_*=1$ the bound is again trivial.
Back to article page
