dc.contributor.author Georgakopoulos, A dc.contributor.author Haslegrave, J dc.contributor.author Sauerwald, T dc.contributor.author Sylvester, J dc.date.accessioned 2022-03-15T00:30:17Z dc.date.available 2022-03-15T00:30:17Z dc.date.issued 2022 dc.identifier.issn 0963-5483 dc.identifier.uri https://www.repository.cam.ac.uk/handle/1810/334973 dc.description.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. dc.description.sponsorship John Sylvester and Thomas Sauerwald were supported by the ERC Starting Grant 679660 (DYNAMIC MARCH). dc.publisher Cambridge University Press (CUP) dc.rights Attribution 4.0 International dc.rights.uri https://creativecommons.org/licenses/by/4.0/ dc.subject 05C81 dc.subject 60J10 dc.subject 68R10 dc.subject 68Q17 dc.title The power of two choices for random walks dc.type Article dc.publisher.department Department of Computer Science And Technology dc.date.updated 2022-03-12T11:16:46Z prism.endingPage 100 prism.issueIdentifier 1 prism.publicationDate 2021 prism.publicationName Combinatorics Probability and Computing prism.startingPage 73 prism.volume 31 dc.identifier.doi 10.17863/CAM.82411 rioxxterms.versionofrecord 10.1017/S0963548321000183 rioxxterms.version VoR dc.contributor.orcid Sylvester, John [0000-0002-6543-2934] dc.identifier.eissn 1469-2163 dc.publisher.url http://dx.doi.org/10.1017/S0963548321000183 rioxxterms.type Journal Article/Review pubs.funder-project-id European Research Council (679660) cam.issuedOnline 2021-05-28 cam.depositDate 2022-03-12 pubs.licence-identifier apollo-deposit-licence-2-1 pubs.licence-display-name Apollo Repository Deposit Licence Agreement
﻿

### This item appears in the following Collection(s)

Except where otherwise noted, this item's licence is described as Attribution 4.0 International