Restart perturbations for reversible Markov chains: trichotomy and pre-cutoff equivalence
Preprint
Abstract
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, $\| \pi_n - \tilde{\pi}_n \|$. We show that for chains with cutoff, $\| \pi_n - \tilde{\pi}_n \|$ 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 $\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 \|$ is maximized by restart perturbations, for which $\tilde{P}_n$ "restarts" $P_n$ at a random state with probability $\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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Linking the mixing times of random walks on static and dynamic random graphsStochastic Processes and their Applications, 2022
- Mixing time of PageRank surfers on sparse random digraphsRandom Structures & Algorithms, 2021
- A Structural Result for Personalized PageRank and its Algorithmic ConsequencesProceedings of the ACM on Measurement and Analysis of Computing Systems, 2019
- Cutoff at the “entropic time” for sparse Markov chainsProbability Theory and Related Fields, 2018
- Random walk on sparse random digraphsProbability Theory and Related Fields, 2017
- Cutoff for nonbacktracking random walks on sparse random graphsThe Annals of Probability, 2017
- Cutoff on all Ramanujan graphsGeometric and Functional Analysis, 2016
- The cutoff phenomenon in finite Markov chains.Proceedings of the National Academy of Sciences, 1996
- Time to Reach Stationarity in the Bernoulli–Laplace Diffusion ModelSIAM Journal on Mathematical Analysis, 1987
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981