Repository logo
 

Multiple random walks on graphs: mixing few to cover many†

Published version
Peer-reviewed

Repository DOI


Type

Article

Change log

Authors

Rivera, N 
Sauerwald, T 
Sylvester, J 

Abstract

jats:titleAbstract</jats:title>jats:pRandom 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 runningjats:inline-formulajats:alternatives<jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0963548322000372_inline1.png" />jats:tex-mathk</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 forjats:italicworst-case</jats:italic>start vertices (posed by Alon, Avin, Koucký, Kozma, Lotker and Tuttle in 2008) remains an open problem. First, we improve and tighten various bounds on thejats:italicstationary</jats:italic>cover time whenjats:inline-formulajats:alternatives<jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0963548322000372_inline2.png" />jats:tex-mathk</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 ofjats:inline-formulajats:alternatives<jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0963548322000372_inline3.png" />jats:tex-mathΩ((n/k)logn)</jats:tex-math></jats:alternatives></jats:inline-formula>on the stationary cover time, holding for anyjats:inline-formulajats:alternatives<jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0963548322000372_inline4.png" />jats:tex-mathn</jats:tex-math></jats:alternatives></jats:inline-formula>-vertex graphjats:inline-formulajats:alternatives<jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0963548322000372_inline5.png" />jats:tex-mathG</jats:tex-math></jats:alternatives></jats:inline-formula>and anyjats:inline-formulajats:alternatives<jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0963548322000372_inline6.png" />jats:tex-math1≤k=o(nlogn)</jats:tex-math></jats:alternatives></jats:inline-formula>. Secondly, we establish thejats:italicstationary</jats:italic>cover times of multiple walks on several fundamental networks up to constant factors. Thirdly, we present a framework characterisingjats:italicworst-case</jats:italic>cover times in terms ofjats:italicstationary</jats:italic>cover times and a novel, relaxed notion of mixing time for multiple walks called thejats:italicpartial 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) thejats:italicworst-case</jats:italic>cover times for many networks including expanders, preferential attachment graphs, grids, binary trees and hypercubes.</jats:p>

Description

Keywords

multiple random walks, mixing time, cover time, Markov chains

Journal Title

Combinatorics Probability and Computing

Conference Name

Journal ISSN

0963-5483
1469-2163

Volume Title

Publisher

Cambridge University Press (CUP)
Sponsorship
European Research Council (679660)