Tight bounds for the cover time of multiple random walks

We study the cover time of multiple random walks on undirected graphs G = (V, E). We consider k parallel, independent random walks 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. Recently, Alon et al. (2008) [5] derived several upper bounds on the cover time, which imply a speed-up of Omega(k) for several graphs; however, for many of them, k has to be bounded by O(log n). They also conjectured that, for any 1 <= k <= n, the speed-up is at most O(k) on any graph. We prove the following main results: We 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. We prove that the speed-up is O(k log n) on any graph. For a large class of graphs we can also improve this bound to O(k), matching the conjecture of Alon et al. We determine the order of the speed-up for any value of 1 <= k <= n on hypercubes, random graphs and degree restricted expanders. For d-dimensional tori with d > 2, our bounds are tight up to logarithmic factors. Our findings also reveal a surprisingly sharp threshold behaviour for certain graphs, e.g., the d-dimensional torus with d > 2 and hypercubes: there is a value T such that the speed-up is approximately min{T, k} for any 1 <= k <= n. (C) 2010 Elsevier B.V. All rights reserved.