Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 215 / 2

A family exhibits pre-cutoff for Markov chains if there are constants $0<A<B<\infty$ and times $t_n$ such that its worst-case total-variation distance tends to one at $A{t}_n$ and to zero at $B{t}_n$. For irreducible reversible chains, a standard necessary condition for pre-cutoff is the product conditionThe hypothesis that $t_{\mathrm{mix}}^{(n)}/t_{\mathrm{rel}}^{(n)}$ is bounded contradicts this condition, while $t_{\mathrm{mix}}^{(n)}\to \infty$ excludes a bounded-time degeneracy. Hence the family cannot exhibit pre-cutoff.

Let ${\Pi }_n(x,y)={\pi }_n(y)$. Since $P_n{\Pi }_n={\Pi }_n{P}_n={\Pi }_n$ and ${\Pi }_n^2={\Pi }_n$, the stationary-reset perturbation of a Markov chain satisfiesEvery row difference from stationarity is multiplied by the nonnegative scalar $(1-a_n{)}^t$, so

Write $r_n=t_{\mathrm{mix}}^{(n)}/t_{\mathrm{rel}}^{(n)}\to \infty$. ThenBy cutoff, at every fixed multiple $c/a_n$ the original chain is still asymptotically unmixed, while part i givesThus the new chain crosses between fixed distance levels gradually on the full scale $a_n^{-1}$: for example its $\epsilon$-mixing times are asymptotic to $a_n^{-1}\log (1/\epsilon )$. No two fixed multiples of one scale can make the limiting distance respectively one and zero, so the family has no pre-cutoff.

Every nonconstant eigenvalue $\lambda$ of $P_n$ becomes $(1-a_n)\lambda$. Hence, writing ${\gamma }_n=1/t_{\mathrm{rel}}^{(n)}$,Sincewe have ${\tilde{t}}_{\mathrm{rel}}^{(n)}\sim t_{\mathrm{rel}}^{(n)}$. Part ii gives ${\tilde{t}}_{\mathrm{mix}}^{(n)}\asymp a_n^{-1}$, and therefore