Tight bounds for the cover time of multiple random walks
type: Item
instance of: scholarly article
title: Tight bounds for the cover time of multiple random walks
zbMATH Open document ID: 1227.68030
author: Robert Elsässer
author: Thomas Sauerwald
published in: Theoretical Computer Science
publication date: 2011-06-07T00:00:00Z
review text: The authors study the cover time of \(k\) parallel, independent random walks on undirected graphs that start from the same vertex. The speed-up is defined as the ratio of the cover time of a single random walk to the cover time of these \(k\) random walks. The authors present a new lower bound on the speed-up that depends on the mixing time. It gives a speed-up of \(\Omega(k)\) on many graphs, even if \(k\) is as large as \(n\). They also prove that the speed-up is \(O(k \log n)\) on any graph. For a large class of graphs they improve this bound to \(O(k)\), matching a conjecture of \textit{N. Alon} et al. [``Many random walks are faster than one'', in: 20th annual ACM symposium on parallel algorithms and architectures (SPAA 2008), 119--128 (2008)]. They determine the order of the speed-up for any value of \(1\leq k\leq n\) on hypercubes, random graphs and degree restricted expanders. Their findings reveal a surprisingly sharp threshold behaviour for certain graphs, e.g., the \(d\)-dimensional torus with \(d>2\) and hypercubes.
reviewed by: Klaus Dohmen
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C81
zbMATH DE Number: 5905024
zbMATH Keywords: random walk
zbMATH Keywords: cover time
zbMATH Keywords: graph
zbMATH Keywords: parallel
zbMATH Keywords: speed-up
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.08.010
OpenAlex ID: W2046919262
cites work: A stochastic process on the hypercube with applications to peer-to-peer networks
cites work: On the time taken by random walks on finite groups to visit every state
cites work: Many Random Walks Are Faster Than One
cites work: Q5417719
cites work: Bounds on the cover time
cites work: Trading Space for Time in Undirected s-t Connectivity
cites work: Q3707062
cites work: The electrical resistance of a graph captures its commute and cover times
cites work: The cover time of sparse random graphs
cites work: Multiple Random Walks and Interacting Particle Systems
cites work: Q2934631
cites work: Comparison theorems for reversible Markov chains
cites work: Asymptotic analysis of a random walk on a hypercube with many dimensions
cites work: Automata, Languages and Programming
cites work: How Well Do Random Walks Parallelize?
cites work: Tight Bounds for the Cover Time of Multiple Random Walks
cites work: Q3267900
cites work: A tight lower bound on the cover time for random walks on graphs
cites work: A tight upper bound on the cover time for random walks on graphs
cites work: Q4449241
cites work: An Expansion Tester for Bounded Degree Graphs
cites work: Covering problems for Brownian motion on spheres
cites work: Q3496342
cites work: Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
cites work: Q3135094
cites work: A Technique for Lower Bounding the Cover Time
DOI: 10.1016/J.TCS.2010.08.010
description: scientific article; zbMATH DE number 5905024