Improved Mixing Rates of Directed Cycles with Additional Sparse Interconnections
(2026) , 17 pages
Files
2307.09949v2.pdf
Open Access - Adobe PDF
- 558.82 KB
Details
- Authors
Gerencsér, Balázs 
- Abstract
- We analyze the absolute spectral gap of Markov chains on graphs obtained from a cycle of n vertices and perturbed only at approximately n 1/ρ random locations with an appropriate, possibly sparse, inter-connection structure. Together with a strong asymmetry along the cycle, the gap of the resulting chain can be bounded inversely proportionally by the longest arc length (up to logarithmic factors) with high probability, providing a significant mixing speedup compared to the reversible version.
- Affiliations
Citations
Gerencsér, B., & Hendrickx, J. (2026). Improved Mixing Rates of Directed Cycles with Additional Sparse Interconnections. https://hdl.handle.net/2078.5/281637