{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T03:51:47Z","timestamp":1759117907575},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T00:00:00Z","timestamp":1622160000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:italic>n<\/jats:italic> of vertices on discrete tori and bounded degree trees, of order <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000183_inline1.png\" \/><jats:tex-math>$${\\mathcal O}(n\\log \\log n)$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> on bounded degree expanders, and of order <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000183_inline2.png\" \/><jats:tex-math>$${\\mathcal O}(n{(\\log \\log n)^2})$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> on the Erd\u0151s\u2013R\u00e9nyi 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.<\/jats:p>","DOI":"10.1017\/s0963548321000183","type":"journal-article","created":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T07:07:07Z","timestamp":1622185627000},"page":"73-100","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["The power of two choices for random walks"],"prefix":"10.1017","volume":"31","author":[{"given":"Agelos","family":"Georgakopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Haslegrave","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Sauerwald","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Sylvester","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,5,28]]},"reference":[{"key":"S0963548321000183_ref29","doi-asserted-by":"publisher","DOI":"10.1017\/9781316672815"},{"key":"S0963548321000183_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2163-2"},{"key":"S0963548321000183_ref15","first-page":"923","article-title":"On the Laplacian eigenvalues of Gn,p. Combin. Probab.","volume":"16","author":"Coja-Oghlan","year":"2007","journal-title":"Comput."},{"key":"S0963548321000183_ref33","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP798"},{"key":"S0963548321000183_ref31","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"key":"S0963548321000183_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/15M1043431"},{"key":"S0963548321000183_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.08.031"},{"key":"S0963548321000183_ref10","doi-asserted-by":"crossref","unstructured":"[10] Bohman, T. and Frieze, A. (2002) Addendum to \u2018Avoiding a giant component\u2019 [Random Struct. Algor. 19 75\u201385, 2001]. Random Struct. Algor. 20 126\u2013130.","DOI":"10.1002\/rsa.10018"},{"key":"S0963548321000183_ref28","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/058"},{"key":"S0963548321000183_ref14","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"S0963548321000183_ref20","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.175.3.8"},{"key":"S0963548321000183_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"S0963548321000183_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4"},{"key":"S0963548321000183_ref3","doi-asserted-by":"crossref","unstructured":"[3] Avin, C. and Krishnamachari, B. (2008) The power of choice in random walks: An empirical study. Comput. Netw. 52 44\u201360. (1) Performance of Wireless Networks (2) Synergy of Telecommunication and Broadcasting Networks.","DOI":"10.1016\/j.comnet.2007.09.012"},{"key":"S0963548321000183_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20151"},{"key":"S0963548321000183_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335411"},{"key":"S0963548321000183_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"S0963548321000183_ref12","unstructured":"[12] Bollob\u00e1s, B. (2001) Random Graphs, 2nd edition, vol. 73 of Cambridge Studies in Advanced Mathematics. Cambridge University Press."},{"key":"S0963548321000183_ref32","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000552"},{"key":"S0963548321000183_ref25","unstructured":"[25] Haslegrave, J. , Sauerwald, T. and Sylvester, J. (2020) Time Dependent Biased Random Walks. Preprint, arXiv:2006.02475."},{"key":"S0963548321000183_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01270385"},{"key":"S0963548321000183_ref17","unstructured":"[17] Cooper, C. , Frieze, A. M. and Johansson, T. (2018) The cover time of a biased random walk on a random cubic graph. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018, June 25\u201329, 2018, Uppsala, Sweden, Vol. 110 of LIPIcs (J. A. Fill and M. D. Ward, eds), Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 16:1\u201316:12."},{"key":"S0963548321000183_ref26","volume-title":"Matrix Analysis","author":"Horn","year":"2013"},{"key":"S0963548321000183_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007486"},{"key":"S0963548321000183_ref30","first-page":"903","article-title":"The power of choice over preferential attachment","volume":"12","author":"Malyshkin","year":"2015","journal-title":"ALEA Lat. Am. J. Probab. Math. Stat."},{"key":"S0963548321000183_ref1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1167782"},{"key":"S0963548321000183_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"S0963548321000183_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_34"},{"key":"S0963548321000183_ref19","volume-title":"Finite State Markovian Decision Processes","author":"Derman","year":"1970"},{"key":"S0963548321000183_ref2","unstructured":"[2] Aldous, D. and Fill, J. A. (2002) Reversible Markov Chains and Random Walks on Graphs. Unfinished monograph, recompiled 2014."},{"key":"S0963548321000183_ref4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01300124","article-title":"Biased random walks","volume":"16","author":"Azar","year":"1996","journal-title":"Combinatorica"},{"key":"S0963548321000183_ref22","unstructured":"[22] Georgakopoulos, A. , Haslegrave, J. , Sauerwald, T. and Sylvester, J. (2020) Choice and bias in random walks. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12\u201314, 2020, Seattle, Washington, USA, Vol. 151 of LIPIcs (T. Vidick, ed), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 76:1\u201376:19."},{"key":"S0963548321000183_ref24","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20616"},{"key":"S0963548321000183_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20504"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,20]],"date-time":"2021-12-20T10:38:21Z","timestamp":1639996701000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000183\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,28]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["S0963548321000183"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000183","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,28]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}