Abstract
A random walk on a graph is a process that explores the graph in a random way: at each step the walk is at a vertex of the graph, and at each step it moves to a uniformly selected neighbor of this vertex. Random walks are extremely useful in computer science and in other fields. A very natural problem that was recently raised by Alon, Avin, Koucky, Kozma, Lotker, and Tuttle (though it was implicit in several previous papers) is to analyze the behavior of k independent walks in comparison with the behavior of a single walk. In particular, Alon et al. showed that in various settings (e.g., for expander graphs), k random walks cover the graph (i.e., visit all its nodes), Ω(k)-times faster (in expectation) than a single walk. In other words, in such cases k random walks efficiently “parallelize” a single random walk. Alon et al. also demonstrated that, depending on the specific setting, this “speedup” can vary from logarithmic to exponential in k.
In this paper we initiate a more systematic study of multiple random walks. We give lower and upper bounds both on the cover time and on the hitting time (the time it takes to hit one specific node) of multiple random walks. Our study revolves over three alternatives for the starting vertices of the random walks: the worst starting vertices (those who maximize the hitting/cover time), the best starting vertices, and starting vertices selected from the stationary distribution. Among our results, we show that the speedup when starting the walks at the worst vertices cannot be too large - the hitting time cannot improve by more than an O(k) factor and the cover time cannot improve by more than min {k logn,k 2} (where n is the number of vertices). These results should be contrasted with the fact that there was no previously known upper-bound on the speedup and that the speedup can even be exponential in k for random starting vertices. Some of these results were independently obtained by Elsässer and Sauerwald (ICALP 2009). We further show that for k that is not too large (as a function of various parameters of the graph), the speedup in cover time is O(k) even for walks that start from the best vertices (those that minimize the cover time). As a rather surprising corollary of our theorems, we obtain a new bound which relates the cover time C and the mixing time mix of a graph. Specifically, we show that \(C=O(m \sqrt{\mathrm{mix}}\log ^2n)\) (where m is the number of edges).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Alon, N., Avin, C., Koucky, M., Kozma, G., Lotker, Z., Tuttle, M.R.: Many Random Walks Are Faster Than One. ArXiv e-prints 705 (May 2007), http://arxiv.org/abs/0705.0467
Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs (1999), http://www.stat.berkeley.edu/aldous/RWG/book.html
Aleliunas, R., Karp, R.M., Lipton, R.J., Lovász, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: 20th Annual Symposium on Foundations of Computer Science (FOCS), San Juan, Puerto Rico, October 29-31, 1979, pp. 218–223. IEEE Computer Society Press, Los Alamitos (1979)
Ajtai, M., Komlós, J., Szemerédi, E.: Deterministic simulation in LOGSPACE. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC), New York City, May 25-27, 1987, pp. 132–140 (1987)
Barnes, G., Feige, U.: Short random walks on graphs. In: STOC, pp. 728–737 (1993)
Broder, A.Z., Karlin, A.R.: Bounds on the cover time. Symposium on Foundations of Computer Science, 479–487 (1988)
Broder, A.Z., Karlin, A.R., Raghavan, P., Upfal, E.: Trading space for time in undirected s-t connectivity. In: STOC, pp. 543–549 (1989)
Frieze, A., Cooper, C., Radzik, T.: Multiple random walks in random regular graphs. In: ICALP (2009)
Chandra, A.K., Raghavan, P., Ruzzo, W.L., Smolensky, R.: The electrical resistance of a graph captures its commute and cover times. In: STOC 1989: Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 574–586. ACM, New York (1989)
Elsässer, R., Sauerwald, T.: Tight bounds for the cover time of multiple random walks. In: ICALP (2009)
Feige, U.: A spectrum of time-space trade-offs for undirected s-t connectivity. J. Comput. Syst. Sci. 54(2), 305–316 (1997)
Halperin, S., Zwick, U.: An optimal randomised logarithmic time connectivity algorithm for the erew pram. J. Comput. Syst. Sci. 53(3), 395–416 (1996)
Karger, D.R., Nisan, N., Parnas, M.: Fast connected components algorithms for the EREW PRAM. SIAM J. Comput. 28(3), 1021–1034 (1999)
Lovász, L.: Random walks on graphs: A survey. Combinatorics, Paul Erdos is Eighty 2, 353–398 (1996)
Levin, D.A., Wilmer, E., Peres, Y.: Markov Chains and Mixing Times. Oxford University Press, Oxford
Matthews, P.: Covering problems for markov chains. The Annals of Probability 16(3), 1215–1228 (1988)
Sinclair, A.: Improved bounds for mixing rates of markov chains and multicommodity flow. Combinatorics, Probability and Computing 1, 351–370 (1992)
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
Efremenko, K., Reingold, O. (2009). How Well Do Random Walks Parallelize?. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2009 2009. Lecture Notes in Computer Science, vol 5687. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03685-9_36
Download citation
DOI: https://doi.org/10.1007/978-3-642-03685-9_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03684-2
Online ISBN: 978-3-642-03685-9
eBook Packages: Computer ScienceComputer Science (R0)