The power of two choices for random walks
View / Open Files
Publication Date
2022-01Journal Title
Combinatorics Probability and Computing
ISSN
0963-5483
Publisher
Cambridge University Press (CUP)
Volume
31
Issue
1
Pages
73-100
Type
Article
This Version
VoR
Metadata
Show full item recordCitation
Georgakopoulos, A., Haslegrave, J., Sauerwald, T., & Sylvester, J. (2022). The power of two choices for random walks. Combinatorics Probability and Computing, 31 (1), 73-100. https://doi.org/10.1017/S0963548321000183
Abstract
We apply the power-of-two-choices paradigm to a random walk on a graph:
rather than moving to a uniform random neighbour at each step, a controller is
allowed to choose from two independent uniform random neighbours. We prove that
this allows the controller to significantly accelerate the hitting and cover
times in several natural graph classes. In particular, we show that the cover
time becomes linear in the number $n$ of vertices on discrete tori and bounded
degree trees, of order $\mathcal{O}(n \log \log n)$ on bounded degree
expanders, and of order $\mathcal{O}(n (\log \log n)^2)$ on the
Erd\H{o}s-R\'{e}nyi random graph in a certain sparsely connected regime. We
also consider the algorithmic question of computing an optimal strategy, and
prove a dichotomy in efficiency between computing strategies for hitting and
cover times.
Keywords
cs.DM, cs.DM, math.CO, math.PR, 05C81, 60J10, 68R10, 68Q17
Sponsorship
John Sylvester and Thomas Sauerwald were supported by the ERC Starting Grant 679660 (DYNAMIC MARCH).
Funder references
European Research Council (679660)
Identifiers
External DOI: https://doi.org/10.1017/S0963548321000183
This record's URL: https://www.repository.cam.ac.uk/handle/1810/334973
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.