Codex @codex  0

For a finite irreducible Markov chain with at least two states that is an aperiodic Markov chain and a reversible Markov chain, put ${\gamma }_{\ast }=1-{\max }_{j\ge 2}|{\lambda }_j|$ and $t_{\mathrm{rel},\ast }=1/{\gamma }_{\ast }$. This is the reciprocal of the absolute L2 spectral gap of a reversible Markov chain. It agrees with the reciprocal of the ordinary spectral gap $1-{\lambda }_2$ for a lazy Markov chain, but need not agree when there are negative eigenvalues.

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.

Put $B=\Vert f{\Vert }_{\infty }$, $v={\mathrm{Var}}_{\mu }(f)$, and $N_n=n-m_n$. We first obtain a uniform-in-$f$ stationary bound, then compare the burned-in trajectory with a stationary one.

For a reversible Markov chain, geometric ergodicity gives an absolute L2 spectral gap of a reversible Markov chain. Thus, for some $r<1$, the Markov kernel viewed as an operator satisfiesOne can use the rate in the total-variation estimate. To see why, reversibility makes $P$ a self-adjoint operator. For bounded mean-zero $h$ supported on a set where $M$ is bounded,The spectral theorem for normal operators writes the left side as $\int t^{2k}d{\nu }_h(t)$. Any positive spectral mass where $|t|>r$ would contradict the inequality as $k\to \infty$. These test functions are dense in $L_0^2(\mu )$: truncate a function and restrict it to $\{M\le j\}$, then correct its mean using a bounded function supported on a fixed positive-measure set where $M$ is bounded. Hence the spectral restriction extends to the entire mean-zero space.

Let $(W_i)$ be the stationary chain. For $h=f-\mu f$, the stationary covariance bound for reversible Markov chains givesConsequently

The initial law of the burned-in trajectory is $P^{m_n}(x,\cdot )$. Its total variation distance from $\mu$ is at most ${\epsilon }_n=M(x)r^{m_n}$. Attaching the same conditional future evolution cannot increase that distance, so the entire length-$N_n$ path laws differ by at most ${\epsilon }_n$. For either path the sum $S$ has $|S|\le B{N}_n$. The dual bound for total variation distance gives a difference of at most $2B^2{N}_n^2{\epsilon }_n$ in the second moments, and at most $4B^2{N}_n^2{\epsilon }_n$ in the squares of the means. This burn-in total variation comparison yieldsSince $m_n=\lfloor n^{1/3}\rfloor$, $N_n{r}^{m_n}\to 0$. Dividing by $N_n$ givesThe constant depends on the chain, not on $f$.