2024/12/17 by Sam Olesker-Taylor, Olesker-Taylor, Sam, Thomas Sauerwald +3
Computer Science · #Formal Methods in Verification #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2412.13109
Random walks on expanders play a crucial role in Markov Chain Monte Carlo algorithms, derandomization, graph theory, and distributed computing. A desirable property is that they are rapidly mixing, which is equivalent to having a spectral gap γ (asymptotically) bounded away from 0. Our work has two main strands. First, we establish a dichotomy for the robustness of mixing times on edge-weighted d-regular graphs (i.e., reversible Markov chains) subject to a Lipschitz condition, which bounds the ratio of adjacent weights by β≥ 1. If β≥ 1 is sufficiently small, then γ\asymp 1 and the mixing time is logarithmic in n. On the other hand, if β≥ 2d, there is an edge-weighting such that γ is polynomially small in 1/n. Second, we apply our robustness result to a time-dependent version of the so-called ε-biased random walk, as introduced in Azar et al. [Combinatorica 1996]. We show that, for any constant ε>0, a bias strategy can be chosen adaptively so that the ε-biased random walk covers any bounded-degree regular expander in Θ(n) expected time, improving the previous-best bound of O(n log log n). We prove the first non-trivial lower bound on the cover time of the ε-biased random walk, showing that, on bounded-degree regular expanders, it is ω(n) whenever ε = o(1). We establish this by controlling how much the probability of arbitrary events can be ``boosted'' by using a time-dependent bias strategy.