Abstract
We study the cover time of multiple random walks. Given a graph G of n vertices, assume that k independent random walks start from the same vertex. The parameter of interest is the speed-up defined as the ratio between the cover time of one and the cover time of k random walks. Recently Alon et al. developed several bounds that are based on the quotient between the cover time and maximum hitting times. Their technique gives a speed-up of Ω(k) on many graphs, however, for many graph classes, k has to be bounded by \({\mathcal{O}}(\log n)\). They also conjectured that, for any 1 ≤ k ≤ n, the speed-up is at most \({\mathcal{O}}(k)\) on any graph. As our main results, we prove the following:
-
We present a new lower bound on the speed-up that depends on the mixing-time. It gives a speed-up of Ω(k) on many graphs, even if k is as large as n.
-
We prove that the speed-up is \({\mathcal{O}}(k \log n)\) on any graph. Under rather mild conditions, we can also improve this bound to \({\mathcal{O}}(k)\), matching exactly the conjecture of Alon et al.
-
We find the correct order of the speed-up for any value of 1 ≤ k ≤ n on hypercubes, random graphs and expanders. For d-dimensional torus graphs (d > 2), our bounds are tight up to a factor of \({\mathcal{O}}(\log n)\).
-
Our findings also reveal a surprisingly sharp dichotomy on several graphs (including d-dim. torus and hypercubes): up to a certain threshold the speed-up is k, while there is no additional speed-up above the threshold.
The first author was partially supported by the German Research Foundation under contract EL 399/2-1, and by the Integrated Project IST 15964 “Algorithmic Principles for Building Efficient Overlay Networks” of the EU. The second author was partially supported by a postdoctoral fellowship from the German Academic Exchange Service (DAAD).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adler, M., Halperin, E., Karp, R., Vazirani, V.: A Stochastic Process on the Hypercube with Applications to Peer-to-Peer Networks. In: 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 575–584 (2003)
Aleliunas, R., Karp, R., Lipton, R., Lovász, L., Rackoff, C.: Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. In: 20th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1979), pp. 218–223 (1979)
Alon, N., Avin, C., Koucky, M., Kozma, G., Lotker, Z., Tuttle, M.: Many Random Walks are faster than one. In: 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2008), pp. 119–128 (2008)
Avin, C., Koucky, M., Lotker, Z.: How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 121–132. Springer, Heidelberg (2008)
Avin, C., Krishnamachari, B.: The power of choice in random walks: an empirical study. In: 9th International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems, pp. 219–228 (2006)
Broder, A., Karlin, A.: Bounds on the cover time. In: 29th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1988), pp. 479–487 (1988)
Broder, A., Karlin, A., Raghavan, P., Upfal, E.: Trading space for time in undirected s–t-connectivity. SIAM Journal on Computing 23(2), 324–334 (1994)
Carne, T.: A Transmutation Formula for Markov Chains. Bulletin des Sciences Mathematiques 109, 399–405 (1985)
Chandra, A., Raghavan, P., Ruzzo, W., Smolensky, R., Tiwari, P.: The Electrical Resistance of a Graph Captures its Commute and Cover Times. Computational Complexity 6(4), 312–340 (1997)
Cooper, C., Frieze, A., Radzik, T.: Multiple random walks and interacting particle systems. In: 36th International Colloquium on Automata, Languages, and Programming (ICALP 2009) (2009) (to appear)
Dimitrov, N.B., Plaxton, C.G.: Optimal Cover Time for a Graph-Based Coupon Collector Process. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005, vol. 3580, pp. 702–716. Springer, Heidelberg (2005)
Dolev, S., Schiller, E., Welch, J.L.: Random walk for self-stabilizing group communication in ad hoc networks. IEEE Transactions on Mobile Computing 5(7), 893–905 (2006)
Gkantsidis, C., Mihail, M., Saberi, A.: Random walks in peer-to-peer networks. Performance Evaluation 63(3), 241–263 (2006)
Ikeda, S., Kubo, I., Okumoto, N., Yamashita, M.: Impact of Local Topological Information on Random Walks on Finite Graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 1054–1067. Springer, Heidelberg (2003)
Kale, S., Seshadhri, C.: An expansion tester for bounded degree graphs. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 527–538. Springer, Heidelberg (2008)
Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), pp. 482–491 (2003)
Lovász, L.: Random walks on graphs: A survey. Combinatorics, Paul Erdös is Eighty 2, 1–46 (1993)
Motwani, R., Raghavan, P.: Randomized Algorithms, 7th edn. Cambridge University Press, Cambridge (1995)
Pak, I.: Mixing time and long paths in graphs. In: 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 321–328 (2002)
Sinclair, A.: Algorithms for Random Generation and Counting. Birkhäuser, Basel (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Elsässer, R., Sauerwald, T. (2009). Tight Bounds for the Cover Time of Multiple Random Walks. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds) Automata, Languages and Programming. ICALP 2009. Lecture Notes in Computer Science, vol 5555. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02927-1_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-02927-1_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02926-4
Online ISBN: 978-3-642-02927-1
eBook Packages: Computer ScienceComputer Science (R0)