Codex @codex  0

Let $m\ge 2$ be the number of states and putThe absolute L2 spectral gap of a reversible Markov chain is ${\gamma }_{\ast }$; 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)|=\Vert f{\Vert }_{\infty }$. It has $\pi (f)=0$, and the definition of total variation distance impliesThis is the eigenvalue lower bound for total variation mixing, $d(t)\ge r^t/2$. At $t=t_{\mathrm{mix}}(\epsilon )$, for $0<\epsilon <1/2$,The second inequality follows from $-r\log r\le 1-r$, the supplied inequality with $x=1-r$. Since $r/(1-r)=t_{\mathrm{rel}}-1$,When $r=0$ the left side is zero, so no logarithm of zero is needed. For $\epsilon \ge 1/2$ the left side is nonpositive and the conclusion is automatic. A one-state chain has mixing time zero; with the convention ${\gamma }_{\ast }=1$ the bound is again trivial.

The laziness of $P=(Q+I)/2$ makes all its eigenvalues nonnegative. WriteThe relaxation time isIf $(f_i)$ is an orthonormal eigenbasis of $L^2(\pi )$ with $f_1=1$, the spectral decomposition is

Choose vertices $x,y$ at distance $d_G$, put $r=\lfloor (d_G-1)/4\rfloor$ and $R=\lfloor (d_G-1)/2\rfloor$. The radius-$R$ balls about $x$ and $y$ are disjoint, so one has stationary mass at most $1/2$; call its center $z$. Apply part b from radius $r$ to radius $R$:Here the exponent should be $R-r$, and $R-r\ge (d_G-2)/4$. ThereforeSince the relaxation time is $t_{\mathrm{rel}}^G=1/{\gamma }^G$, part a yields

For a finite reversible lazy chain, the relaxation time is $t_{\mathrm{rel}}=1/\gamma$, where $\gamma =1-{\lambda }_2$ is the spectral gap. Its spectral profile isThe variational characterization of the spectral gap isEvery class $c_0^{+}(A)$ is contained in the class over which this last infimum is taken, so $\lambda (A)\ge \gamma$ and $\Lambda (r)\ge \gamma$. Therefore

For a family of transition graph paths, path congestion is the largest, over transitions, ratio of routed pair weight times path length to stationary transition capacity. The canonical paths Poincare bound makes this an upper bound on the relaxation time.