Restart Perturbations for Reversible Markov Chains: Trichotomy and Pre‐Cutoff Equivalence
Open Access
- 21 April 2025
- journal article
- Published by Wiley in Random Structures & Algorithms
- Vol. 66 (3)
Abstract
Given a reversible Markov chain on states, and another chain obtained by perturbing each row of by at most in total variation, we study the total variation distance between the two stationary distributions, . We show that for chains with cutoff, converges to 0, is asymptotically at most (with a sequence of perturbations for which convergence to this bound occurs), and converges to 1, respectively, if the product of and the mixing time of converges to 0, , and , 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 is maximized by restart perturbations, for which “restarts” at a random state with probability 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
Funding Information
- National Science Foundation (CCF 2008130)
This publication has 18 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
- Random walks on dynamic configuration models:A trichotomyStochastic Processes and their Applications, 2019
- 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
- Exact sampling with coupled Markov chains and applications to statistical mechanicsRandom Structures & Algorithms, 1996
- 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
- Random walks on finite groups and rapidly mixing markov chains1983