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

Authors:
  • DVDaniel Vial
    Daniel Vial
  • VSVijay Subramanian
    Vijay Subramanian

Abstract
Given a lazy, reversible Markov chain with $n$ states and transition matrix $P_n$, a distribution $\sigma_n$ over the states, and some $\alpha_n \in (0,1)$, we consider restart perturbations, which take the following form: with probability $1-\alpha_n$, sample the next state from $P_n$; with probability $\alpha_n$, sample the next state from $\sigma_n$ (i.e. "restart" at a random state). Our main object of study is $\| \pi_n - \tilde{\pi}_n\|$, where $\pi_n$ and $\tilde{\pi}_n$ are the stationarity distributions of the original and perturbed chains and $\| \cdot \|$ denotes total variation. Our first result characterizes $\| \pi_n - \tilde{\pi}_n\|$ in terms of the $\epsilon$-mixing times $t_{\textrm{mix}}^{(n)}(\epsilon)$ of the $P_n$ chain, assuming these mixing times exhibit cutoff. Namely, we show that if $\alpha_n t_{\textrm{mix}}^{(n)}(\epsilon) \rightarrow 0$, then $\| \pi_n - \tilde{\pi}_n \| \rightarrow 0$ for any restart perturbation; if $\alpha_n t_{\textrm{mix}}^{(n)}(\epsilon) \rightarrow \infty$, then $\| \pi_n - \tilde{\pi}_n \| \rightarrow 1$ for some restart perturbation; and if $\alpha_n t_{\textrm{mix}}^{(n)}(\epsilon) \rightarrow c \in (0,\infty)$, then $\limsup_{n \rightarrow \infty} \| \pi_n - \tilde{\pi}_n \| \leq 1 - e^{-c}$ for any restart perturbation (and the bound is tight). Similar "trichotomies" have appeared in several result results; however, these existing results consider generative models for the chain, whereas ours applies more broadly. Our second result shows the weaker notion of pre-cutoff is (almost) equivalent to a certain notion of "sensitivity to perturbation", in the sense that $\| \pi_n - \tilde{\pi}_n \| \rightarrow 1$ for certain perturbations. This complements a recent result by Basu, Hermon, and Peres, which shows that cutoff is equivalent to a certain notion of "hitting time cutoff".