Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-29T06:57:03.662Z Has data issue: false hasContentIssue false
  • English
  • Français

On a Result of Aleliunas et al. Concerning Random Walks on Graphs

Published online by Cambridge University Press:  27 July 2009

José Luis Palacios
José Luis Palacios
Affiliation:
Department of Mathematics New JerseyInstitute of Technology Newark, New Jersey 07102
Get access Rights & Permissions [Opens in a new window]

Abstract

Aleliunas et al. [3] proved that for a random walk on a connected raph G = (V, E) on N vertices, the expected minimum number of steps to visit all vertices is bounded by 2|E|(N - 1), regardless of the initial state. We give here a simple proof of that result through an equality involving hitting times of vertices that can be extended to an inequality for hitting times of edges, thus obtaining a bound for the expected minimum number of steps to visit all edges exactly once in each direction.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 4 , Issue 4 , October 1990 , pp. 489 - 492
Copyright
Copyright © Cambridge University Press 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Aldous, D.J. (1989). An introduction to covering problems for random walks on graphs. Journal of Theoretical Probability 2: 87–89.CrossRefGoogle Scholar
Aldous, D.J. (1989). Bibliography: Random walks on graphs. Preprint. Berkeley, CA: Department of Statistics, University of California.Google Scholar
Aleliunas, R., Karp, R.M., Lipton, R.J., Lovasz, L., & Rackoff, C. (1979). Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual symposium on foundations of computer science, San Juan, Puerto Rico, pp. 218–223.Google Scholar
Lawler, G. (1986). Expected hitting times for a random walk on a connected graph. Discrete Mathematics 61: 85–92.CrossRefGoogle Scholar