Multiple random walks on graphs: mixing few to cover many

Rivera, Nicolas, Sauerwald, Thomas and Sylvester, John ORCID: 0000-0002-6543-2934 (2023) Multiple random walks on graphs: mixing few to cover many. COMBINATORICS PROBABILITY & COMPUTING, 32 (4). pp. 1-44.

Access the full-text of this item by clicking on the Open Access link.

Official URL: http://dx.doi.org/10.1017/s0963548322000372

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ý, 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>

Item Type:	Article
Uncontrolled Keywords:	multiple random walks, mixing time, cover time, Markov chains
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	24 Feb 2023 14:45
Last Modified:	11 Dec 2023 04:10
DOI:	10.1017/S0963548322000372
Open Access URL:	https://doi.org/10.1017/S0963548322000372
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3168587