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.

Use the ratio definition of cutoff from part (a), and write $T_n=t_{\mathrm{mix}}^{(n)}(1/4)$. In the reversible Markov chain setting of the preceding parts let ${\gamma }_n=1-{\lambda }_{2,n}$ and ${\gamma }_{\ast ,n}=1-{\max }_{j\ge 2}|{\lambda }_{j,n}|$. In particular ${\gamma }_{\ast ,n}\le {\gamma }_n$.

If ${\gamma }_n{T}_n$ did not tend to infinity, there would be a subsequence and $B>0$ for which ${\gamma }_n{T}_n\le B$. Along it part (c) implies, for every fixed $0<\epsilon <1/2$,Since $T_n\to \infty$, choose fixed $\epsilon$ so small that $\log (1/(2\epsilon ))>B$. The lower limit of this ratio is then greater than one, contradicting cutoff for Markov chains. Thus the Peres product condition holds:In fact the argument with ${\gamma }_{\ast ,n}$ proves the stronger absolute-gap product condition. Part (d) does not repeat the reversible Markov chain hypothesis; the ordinary real ordering of eigenvalues above uses that hypothesis. If arbitrary chains are intended, define the spectral gap explicitly: the eigenvalue lower bound for total variation mixing works for complex eigenfunctions too, and proves the same assertion for ${\gamma }_{\ast }$ or for $1-{\max }_{j\ge 2}\mathrm{Re}{\lambda }_j$, which is at least ${\gamma }_{\ast }$. No real ordering of complex eigenvalues is implicit.

For the requested counterexample take nonlazy simple random walk on the complete graph $K_n$, $n\ge 3$. Let $\Pi$ have every row equal to the uniform distribution on a finite set, and let $a=-1/(n-1)$. ThenThus $d_n(0)\to 1$ and $d_n(1)=1/n\to 0$: every fixed-level mixing time is eventually one. This is a bounded-time jump satisfying the ratio definition of cutoff. The ordinary spectral gap is $n/(n-1)$ and the absolute one is $(n-2)/(n-1)$, so both products with $T_n=1$ tend to one, not infinity. The divergence assumption on $T_n$ is therefore essential under this convention.

For finite irreducible Markov chains that are aperiodic Markov chains and reversible Markov chains, the ratio definition of cutoff and $T_n=t_{\mathrm{mix}}^{(n)}(1/4)\to \infty$ imply the Peres product condition, with ${\gamma }_n=1-{\lambda }_{2,n}$. If ${\gamma }_n{T}_n\le B$ on a subsequence, then ${\gamma }_{\ast ,n}\le {\gamma }_n$ and the eigenvalue lower bound for total variation mixing giveFor sufficiently small fixed $\epsilon$, this contradicts the limit one forced by cutoff for Markov chains. The same argument proves the stronger conclusion ${\gamma }_{\ast ,n}{T}_n\to \infty$.