{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T08:59:59Z","timestamp":1758704399751,"version":"3.40.5"},"reference-count":60,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T00:00:00Z","timestamp":1676419200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Random walks on graphs are an essential primitive for many randomised algorithms and stochastic processes. It is natural to ask how much can be gained by running<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000372_inline1.png\"\/><jats:tex-math>$k$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>multiple random walks independently and in parallel. Although the cover time of multiple walks has been investigated for many natural networks, the problem of finding a general characterisation of multiple cover times for<jats:italic>worst-case<\/jats:italic>start vertices (posed by Alon, Avin, Kouck\u00fd, Kozma, Lotker and Tuttle in 2008) remains an open problem. First, we improve and tighten various bounds on the<jats:italic>stationary<\/jats:italic>cover time when<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000372_inline2.png\"\/><jats:tex-math>$k$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>random walks start from vertices sampled from the stationary distribution. For example, we prove an unconditional lower bound of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000372_inline3.png\"\/><jats:tex-math>$\\Omega ((n\/k) \\log n)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>on the stationary cover time, holding for any<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000372_inline4.png\"\/><jats:tex-math>$n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex graph<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000372_inline5.png\"\/><jats:tex-math>$G$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and any<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000372_inline6.png\"\/><jats:tex-math>$1 \\leq k =o(n\\log n )$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Secondly, we establish the<jats:italic>stationary<\/jats:italic>cover times of multiple walks on several fundamental networks up to constant factors. Thirdly, we present a framework characterising<jats:italic>worst-case<\/jats:italic>cover times in terms of<jats:italic>stationary<\/jats:italic>cover times and a novel, relaxed notion of mixing time for multiple walks called the<jats:italic>partial mixing time<\/jats:italic>. Roughly speaking, the partial mixing time only requires a specific portion of all random walks to be mixed. Using these new concepts, we can establish (or recover) the<jats:italic>worst-case<\/jats:italic>cover times for many networks including expanders, preferential attachment graphs, grids, binary trees and hypercubes.<\/jats:p>","DOI":"10.1017\/s0963548322000372","type":"journal-article","created":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T04:47:50Z","timestamp":1676436470000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Multiple random walks on graphs: mixing few to cover many"],"prefix":"10.1017","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3368-9708","authenticated-orcid":false,"given":"Nicol\u00e1s","family":"Rivera","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0882-283X","authenticated-orcid":false,"given":"Thomas","family":"Sauerwald","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6543-2934","authenticated-orcid":false,"given":"John","family":"Sylvester","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2023,2,15]]},"reference":[{"key":"S0963548322000372_ref48","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.009"},{"key":"S0963548322000372_ref24","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.85"},{"key":"S0963548322000372_ref55","first-page":"355","volume-title":"Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011","author":"Pettarin","year":"2011"},{"key":"S0963548322000372_ref50","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"S0963548322000372_ref59","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.86"},{"key":"S0963548322000372_ref40","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384303"},{"key":"S0963548322000372_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060406"},{"key":"S0963548322000372_ref7","first-page":"1702","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018","author":"Ben-Hamou","year":"2018"},{"key":"S0963548322000372_ref46","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnx082"},{"key":"S0963548322000372_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_14"},{"key":"S0963548322000372_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274"},{"key":"S0963548322000372_ref28","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989263"},{"key":"S0963548322000372_ref56","first-page":"99:1","volume-title":"48th International Colloquium on Automata, Languages, and Programming, ICALP 2021","author":"Rivera","year":"2021"},{"key":"S0963548322000372_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790190144"},{"key":"S0963548322000372_ref47","doi-asserted-by":"publisher","DOI":"10.1017\/9781316672815"},{"key":"S0963548322000372_ref37","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484260"},{"key":"S0963548322000372_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.010"},{"key":"S0963548322000372_ref25","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2005.1498436"},{"key":"S0963548322000372_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"S0963548322000372_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048274"},{"key":"S0963548322000372_ref44","first-page":"353","volume-title":"Combinatorics, Paul Erd\u0151s is Eighty, Vol. 2 (Keszthely, 1993)","author":"Lov\u00e1sz","year":"1996"},{"key":"S0963548322000372_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831000012X"},{"key":"S0963548322000372_ref22","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1471"},{"key":"S0963548322000372_ref54","doi-asserted-by":"publisher","DOI":"10.1007\/s10959-013-0497-9"},{"key":"S0963548322000372_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000125"},{"key":"S0963548322000372_ref39","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316330"},{"key":"S0963548322000372_ref57","first-page":"31","article-title":"Distributed random walks","volume":"60","author":"Sarma","year":"2013","journal-title":"J. ACM"},{"key":"S0963548322000372_ref45","doi-asserted-by":"publisher","DOI":"10.1145\/514191.514206"},{"key":"S0963548322000372_ref2","unstructured":"[2] Aldous, D. and Fill, J. A. (2002) Reversible Markov chains and random walks on graphs. Unfinished monograph, recompiled 2014."},{"key":"S0963548322000372_ref35","first-page":"36","volume-title":"SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures","author":"Karger","year":"2004"},{"key":"S0963548322000372_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(87)90006-6"},{"key":"S0963548322000372_ref36","first-page":"163","volume-title":"Proceedings on 33rd Annual ACM Symposium on Theory of Computing, STOC 2001","author":"Kempe","year":"2001"},{"key":"S0963548322000372_ref58","first-page":"315","volume-title":"Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010","author":"Sauerwald","year":"2010"},{"key":"S0963548322000372_ref10","first-page":"1","volume-title":"PODC \u201921: ACM Symposium on Principles of Distributed Computing, 2021","author":"Clementi","year":"2021"},{"key":"S0963548322000372_ref31","first-page":"44:1","volume-title":"34th Symposium on Theoretical Aspects of Computer Science, STACS 2017","author":"Ivaskovic","year":"2017"},{"key":"S0963548322000372_ref30","unstructured":"[30] Hermon, J. and Sousi, P. (2021) Covering a graph with independent walks."},{"key":"S0963548322000372_ref33","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892134"},{"key":"S0963548322000372_ref38","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00055"},{"key":"S0963548322000372_ref41","first-page":"1612","volume-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012","author":"Lam","year":"2012"},{"volume-title":"Markov Chains and Mixing Times","year":"2009","author":"Levin","key":"S0963548322000372_ref42"},{"key":"S0963548322000372_ref19","first-page":"476","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009","author":"Efremenko","year":"2009"},{"key":"S0963548322000372_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-014-0168-6"},{"key":"S0963548322000372_ref26","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731721"},{"key":"S0963548322000372_ref43","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1028903453"},{"key":"S0963548322000372_ref17","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.175.3.8"},{"key":"S0963548322000372_ref53","doi-asserted-by":"publisher","DOI":"10.1137\/15M1010737"},{"key":"S0963548322000372_ref60","doi-asserted-by":"publisher","DOI":"10.1137\/080744888"},{"key":"S0963548322000372_ref4","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"S0963548322000372_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548321000183"},{"key":"S0963548322000372_ref11","first-page":"1","volume-title":"Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011","author":"Cooper","year":"2011"},{"key":"S0963548322000372_ref15","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1002\/rsa.20826","article-title":"Planar graphs: Random walks and bipartiteness testing","volume":"55","author":"Czumaj","year":"2019","journal-title":"Random Struct. Algorithms"},{"key":"S0963548322000372_ref32","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2017.11.017"},{"key":"S0963548322000372_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048272"},{"key":"S0963548322000372_ref51","first-page":"119","volume-title":"Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2019","author":"Oliveira","year":"2019"},{"key":"S0963548322000372_ref13","first-page":"21","article-title":"A note on the vacant set of random walks on the hypercube and other regular graphs of high degree","volume":"4","author":"Cooper","year":"2014","journal-title":"Mosc. J. Comb. Number Theory"},{"key":"S0963548322000372_ref52","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v17-2274"},{"key":"S0963548322000372_ref29","doi-asserted-by":"publisher","DOI":"10.1214\/18-EJP144"},{"key":"S0963548322000372_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.007"},{"key":"S0963548322000372_ref27","first-page":"28:1","volume-title":"37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020","author":"Guinard","year":"2020"},{"key":"S0963548322000372_ref49","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T22:29:50Z","timestamp":1701901790000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000372\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,15]]},"references-count":60,"alternative-id":["S0963548322000372"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000372","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2023,2,15]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. 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 (https:\/\/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"}]}}