Time-Biased Random Walks and Robustness of Expanders

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 γ ≍ 1 and the mixing time is logarithmic in n.

• 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.