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. 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:	23 Mar 2023 04:03
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