Tight bounds for the cover time of multiple random walks (Q541669): Difference between revisions
From MaRDI portal
Changed an Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 07:57, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Tight bounds for the cover time of multiple random walks |
scientific article |
Statements
Tight bounds for the cover time of multiple random walks (English)
0 references
7 June 2011
0 references
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.
0 references
random walk
0 references
cover time
0 references
graph
0 references
parallel
0 references
speed-up
0 references