학술논문
Improved Mixing Rates of Directed Cycles with Additional Sparse Interconnections
Document Type
Working Paper
Source
Subject
Language
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/\rho}$ random locations with an appropriate, possibly sparse, interconnection 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.
Comment: 17 pages, 3 figures
Comment: 17 pages, 3 figures