Mixing on the cycle with constant size perturbation
- 1 January 2026
- journal article
- Published by Institute of Mathematical Statistics in Electronic Journal of Probability
- Vol. 31 (none) , 1-27
Abstract
Considering a Markov chain defined on a cycle, near-quadratic improvement of mixing is shown when only a subtle perturbation is introduced to the structure and non-reversible transition probabilities are used. More precisely, a mixing time of O(n k+2 k+1) can be achieved by adding k random edges to the cycle, keeping k fixed while n→∞. The construction builds upon a biased random walk along the cycle.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Phase transition for random walks on graphs with added weighted random matchingProbability Theory and Related Fields, 2024
- Analysis of a non-reversible Markov chain speedup by a single edgeJournal of Applied Probability, 2023
- Characterizing limits and opportunities in speeding up Markov chain mixingStochastic Processes and their Applications, 2021
- Probability2019
- Comparing mixing times on sparse random graphs2018
- Random walks on the random graphThe Annals of Probability, 2018
- Markov Chains and Mixing Times2017
- Smoothed Analysis on Connected GraphsSIAM Journal on Discrete Mathematics, 2015
- Random Graph Dynamics2006
- Lifting Markov chains to speed up mixing1999