On sensitivity of mixing times and cutoff

A sequence of chains exhibits (total-variation) cutoff (resp., pre-cutoff) if for all $0<ϵ<1\mathrm{/}2$, the ratio $t_{\mathrm{m}\mathrm{i}\mathrm{x}}^{(n)}(ϵ)\mathrm{/}{t}_{\mathrm{m}\mathrm{i}\mathrm{x}}^{(n)}(1-ϵ)$ tends to 1 as $n\to \mathrm{\infty }$ (resp., the $\mathrm{lim\hspace{0.17em}sup}$ of this ratio is bounded uniformly in $ϵ$), where $t_{\mathrm{m}\mathrm{i}\mathrm{x}}^{(n)}(ϵ)$ is the $ϵ$-total-variation mixing-time of the $n$th chain in the sequence. We construct a sequence of bounded degree graphs $G_n$, such that the lazy simple random walks (LSRW) on $G_n$ satisfy the “product condition” $$\mathrm{g}\mathrm{a}\mathrm{p}$(G_n) t_{$\mathrm{m}\mathrm{i}\mathrm{x}$}^{(n)}(\epsilon) \to \infty $as$n \to \infty$,where$$\mathrm{g}\mathrm{a}\mathrm{p}$(G_n)$isthespectralgapoftheLSRWon$G_n$ (a known necessary condition for pre-cutoff that is often sufficient for cutoff), yet this sequence does not exhibit pre-cutoff. Recently, Chen and Saloff-Coste showed that total-variation cutoff is equivalent for the sequences of continuous-time and lazy versions of some given sequence of chains. Surprisingly, we show that this is false when considering separation cutoff. We also construct a sequence of bounded degree graphs $G_n=(V_n,E_n)$ that does not exhibit cutoff, for which a certain bounded perturbation of the edge weights leads to cutoff and increases the order of the mixing-time by an optimal factor of $\mathrm{\Theta }(\log \mathrm{\mid }{V}_n\mathrm{\mid })$. Similarly, we also show that “lumping” states together may increase the order of the mixing-time by an optimal factor of $\mathrm{\Theta }(\log \mathrm{\mid }{V}_n\mathrm{\mid })$. This gives a negative answer to a question asked by Aldous and Fill.