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

Daniel Vial, Vijay Subramanian

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 tota…