Restart perturbations for reversible Markov chains: trichotomy and pre-cutoff equivalence

Given a reversible Markov chain $P_n$ on $n$ states, and another chain ${\tilde{P}}_n$ obtained by perturbing each row of $P_n$ by at most ${\alpha }_n$ in total variation, we study the total variation distance between the two stationary distributions, $\mathrm{\parallel }{\pi }_n-{\tilde{\pi }}_n\mathrm{\parallel }$. We show that for chains with cutoff, $\mathrm{\parallel }{\pi }_n-{\tilde{\pi }}_n\mathrm{\parallel }$ converges to $0$, $e^{-c}$, and $1$, respectively, if the product of ${\alpha }_n$ and the mixing time of $P_n$ converges to $0$, $c$, and $\mathrm{\infty }$, respectively. This echoes recent results for specific random walks that exhibit cutoff, suggesting that cutoff is the key property underlying such results. Moreover, we show $| \pi_n - \tilde{\pi}_n |$ismaximizedbyrestartperturbations,forwhich$\tilde{P}_n$\mathrm{"}restarts\mathrm{"}$P_n$atarandomstatewithprobability$\alpha_n$ at each step. Finally, we show that pre-cutoff is (almost) equivalent to a notion of “sensitivity to restart perturbations,” suggesting that chains with sharper convergence to stationarity are inherently less robust.