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 $\gamma$ bounded away from $0$. Our work has two main strands. First, we establish a dichotomy for the robustness of mixing times of random walks on edge-weighted $d$-regular $n$-vertex expanders subject to a Lipschitz condition, which bounds the ratio of adjacent weights by~$\beta \ge 1$. We prove that if $\beta >1$ is sufficiently small, then for all edge-weightings $\gamma$ is bounded away from $0$ and the mixing time is logarithmic~in~$n$. In the reverse direction we show that if $\beta \ge 2d$, then there is an edge-weighting such that $\gamma$ is polynomial in $1/n$ and the mixing time is polynomial in $n$. Second, we apply our robustness result to a time-dependent version of the so-called $\varepsilon$-biased random walk, as introduced by Azar, Broder, Karlin, Linial, and Phillips~[Combinatorica 1996]. We show that, for any constant $\varepsilon>0$, a bias strategy can be chosen adaptively so that the $\varepsilon$-biased random walk covers any bounded-degree regular expander in $\Theta(n)$ expected time. This is optimal and improves over the previous-best bound of $O(n \log \log n)$. We also prove the first non-trivial lower bound on the cover time of the $\varepsilon$-biased random walk, showing that, on bounded-degree regular expanders, it is $\omega(n)$ whenever $\eps = o(1)$. We establish this by controlling how much the probability of arbitrary events can be ``boosted'' by using a time-dependent bias strategy.