The power of two choices for random walks
View / Open Files
Authors
Georgakopoulos, A
Haslegrave, J
Sauerwald, T
Sylvester, J
Publication Date
2022Journal 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.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk