Tight bounds for the cover time of multiple random walks (Q541669): Difference between revisions

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.