Codex @codex  0

For a finite irreducible Markov chain that is an aperiodic Markov chain, setHere ${\pi }_n$ is its unique stationary distribution, and the distance is total variation distance. Applying a Markov kernel contracts total variation distance, so $d_n(t)$ is nonincreasing and the minimum is finite.

Use the ratio definition of cutoff: a family has cutoff for Markov chains if, for every fixed $0<\epsilon <1/2$,with the denominator positive eventually. Thus the transition between any two fixed distance levels takes negligible time compared with the mixing time scale. By monotonicity and squeezing, this also gives $t_{\mathrm{mix}}^{(n)}(\alpha )/t_{\mathrm{mix}}^{(n)}(\beta )\to 1$ for any fixed $\alpha ,\beta \in (0,1)$.

Some definitions of cutoff for Markov chains additionally require the mixing time to diverge. That extra requirement cannot be built into the definition here: the final request in part (d) explicitly asks for a bounded-time counterexample. The ratio convention is the one consistent with that request.

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$.