= Eigenvalue lower bound for total variation mixing
{title2=$d(t)\geq r^t/2$}
If $r=\max_{j\geq2}|\lambda_j|$ for a finite <irreducible Markov chain> with at least two states, then its worst-case <total variation distance> from its <stationary distribution> satisfies $d(t)\geq r^t/2$. Choose a possibly complex <eigenfunction> $f$ for an <eigenvalue> of modulus $r$, normalize $\max_x|f(x)|=1$, and start where the maximum is attained. Since $\pi(f)=0$, $|P^tf(x)-\pi(f)|=r^t$; the defining sum for <total variation distance> bounds this difference by $2d(t)$. For $0<r<1$, this yields $t_{\mathrm{mix}}(\varepsilon)\geq(r/(1-r))\log(1/(2\varepsilon))$ for $0<\varepsilon<1/2$, because $-r\log r\leq1-r$.
Back to article page
