Many random walks are faster than one

ABSTRACT

We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - the expected time required to visit every node in a graph at least once - and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probablistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

REFERENCES

• 1: Alanyali, M., Saligrama, V., and Sava, O. A random-walk model for distributed computation in energy-limited network. In In Proc. of 1st Workshop on Information Theory and its Application (San Diego, 2006).
• 2: Aldous, D. J. On the time taken by random on finite groups to visit every state. Z. Wahrsch. Verw. Gebiete 62, 3 (1983), 361--374.
• 3: Aldous, D. J. Lower bounds for covering times for reversible markov chains and random walks on graphs. J. Theoret. Probab. 2, 1 (1989), 91--100.
• 4: Aldous, D. J. Threshold limits for cover times. Journal of Theoretical Probability V4, 1 (1991), 197--211.
• 5: Romas Aleliunas , Richard M. Karp , Richard J. Lipton , Laszlo Lovasz , Charles Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, Proceedings of the 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), p.218-223, October 29-31, 1979
• 6: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 7: Roy Armoni , Amnon Ta-Shma , Avi Widgerson , Shiyu Zhou, An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs, Journal of the ACM (JACM), v.47 n.2, p.294-311, March 2000 [doi>10.1145/333979.333984]
• 8: Chen Avin , Carlos Brito, Efficient and robust query processing in dynamic environments using random walk techniques, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984663]
• 9: Avin, C., and Ercal, G. On the cover time of random geometric graphs. In Proc. Automata, Languages and Programming, 32nd International Colloquium, ICALP05 (2005), pp. 677--689.
• 10: Ziv Bar-Yossef , Roy Friedman , Gabriel Kliot, RaWMS -: random walk based lightweight membership service for wireless ad hoc network, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132932]
• 11: Uriel Feige, A spectrum of time-space trade-offs for undirected s-tconnectivity, Journal of Computer and System Sciences, v.54 n.2, p.305-316, April 1997 [doi>10.1006/jcss.1997.1471]
• 12: David Braginsky , Deborah Estrin, Rumor routing algorthim for sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570742]
• 13: Broder, A., and Karlin, A. Bounds on the cover time. J. Theoret. Probab. 2 (1989), 101--120.
• 14: A. Z. Broder , A. R. Karlin , P. Raghavan , E. Upfal, Trading space for time in undirected s-t connectivity, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.543-549, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73059]
• 15: A. K. Chandra , P. Raghavan , W. L. Ruzzo , R. Smolensky, The electrical resistance of a graph captures its commute and cover times, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.574-586, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73062]
• 16: Colin Cooper , Alan Frieze, The cover time of sparse random graphs., Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 17: Shlomi Dolev , Elad Schiller , Jennifer Welch, Random Walk for Self-Stabilizing Group Communication in Ad-Hoc Networks, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.70, October 13-16, 2002
• 18: Uriel Feige, A tight lower bound on the cover time for random walks on graphs, Random Structures & Algorithms, v.6 n.4, p.433-438, July 1995 [doi>10.1002/rsa.3240060406]
• 19: Uriel Feige, A tight upper bound on the cover time for random walks on graphs, Random Structures & Algorithms, v.6 n.1, p.51-54, Jan. 1995 [doi>10.1002/rsa.3240060106]
• 20: Greg Barnes , Uriel Feige, Short Random Walks on Graphs, SIAM Journal on Discrete Mathematics, v.9 n.1, p.19-28, Feb. 1996 [doi>10.1137/S0895480194264988]
• 21: Gkantsidis, C., Mihail, M., and Saberi, A. Random walks in peer-to-peer networks. In in Proc. 23 Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). to appear (2004).
• 22: Shay Halperin , Uri Zwick, An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM, Journal of Computer and System Sciences, v.53 n.3, p.395-416, Dec. 1996 [doi>10.1006/jcss.1996.0078]
• 23: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 24: Johan Jonasson, On the Cover Time for Random Walks on Random Graphs, Combinatorics, Probability and Computing, v.7 n.3, p.265-279, September 1998 [doi>10.1017/S0963548398003538]
• 25: Jonasson, J., and Schramm, O. On the cover time of planar graphs. Electronic Communications in Probability 5 (2000), 85--90.
• 26: David R. Karger , Noam Nisan , Michal Parnas, Fast Connected Components Algorithms for the EREW PRAM, SIAM Journal on Computing, v.28 n.3, p.1021-1034, Feb. 1999 [doi>10.1137/S009753979325247X]
• 27: Lovász, L. Random walks on graphs: A survey. In Combinatorics, Paul Erdös is eighty, Vol. 2 (Keszthely, 1993), vol. 2 of Bolyai Soc. Math. Stud. János Bolyai Math. Soc., Budapest, 1996, pp. 353--397.
• 28: Matthews, P. Covering problems for brownian motion on spheres. Ann. Probab. 16, 1 (1988), 189--199.
• 29: N. Nisan , E. Szemeredi , A. Wigderson, Undirected connectivity in O(log/sup 1.5/n) space, Proceedings of the Proceedings., 33rd Annual Symposium on Foundations of Computer Science, p.24-29, October 24-27, 1992 [doi>10.1109/SFCS.1992.267822]
• 30: Sadagopan, N., Krishnamachari, B., and Helmy, A. Active query forwarding in sensor networks (acquire). Journal of Ad Hoc Networks 3, 1 (January 2005), 91--113.
• 31: Sergio D. Servetto , Guillermo Barrenechea, Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570741]
• 32: Israel A. Wagner , Michael Lindenbaum , Alfred M. Bruckstein, Robotic Exploration, Brownian Motion and Electrical Resistance, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.116-130, October 08-10, 1998
• 33: Zuckerman, D. Covering times of random walks on bounded degree trees and other graphs. Journal of Theoretical Probability V2, 1 (1989), 147--157.
• 34: D. Zuckerman, A technique for lower bounding the cover time, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.254-259, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100249]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
cover time, distributed algorithms, graph search, random walks, speed-up