= Solution
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_{*,n}=1-\max_{j\geq2}|\lambda_{j,n}|$. In particular $\gamma_{*,n}\leq\gamma_n$.
If $\gamma_nT_n$ did not tend to infinity, there would be a subsequence and $B>0$ for which $\gamma_nT_n\leq B$. Along it part (c) implies, for every fixed $0<\varepsilon<1/2$,
$$
\frac{t_{\mathrm{mix}}^{(n)}(\varepsilon)}{T_n}
\geq\left(\frac1{\gamma_{*,n}T_n}-\frac1{T_n}\right)\log\frac1{2\varepsilon}
\geq\left(\frac1B-\frac1{T_n}\right)\log\frac1{2\varepsilon}.
$$
Since $T_n\to\infty$, choose fixed $\varepsilon$ so small that $\log(1/(2\varepsilon))>B$. The lower limit of this ratio is then greater than one, contradicting <cutoff for Markov chains>. Thus the <Peres product condition> holds:
$$
\boxed{\gamma_nT_n\longrightarrow\infty.}
$$
In fact the argument with $\gamma_{*,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_*$ or for $1-\max_{j\geq2}\operatorname{Re}\lambda_j$, which is at least $\gamma_*$. No real ordering of complex <eigenvalues> is implicit.
For the requested counterexample take nonlazy <simple random walk> on the <complete graph> $K_n$, $n\geq3$. Let $\Pi$ have every row equal to the <uniform distribution on a finite set>, and let $a=-1/(n-1)$. Then
$$
P=\Pi+a(I-\Pi),\quad P^t=\Pi+a^t(I-\Pi),\quad
\boxed{d_n(t)=\left(1-\frac1n\right)(n-1)^{-t}.}
$$
Thus $d_n(0)\to1$ and $d_n(1)=1/n\to0$: 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.
Back to article page
