Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-26T13:37:43.219Z Has data issue: false hasContentIssue false
  • English
  • Français

Hitting times for random walks on vertex-transitive graphs

Published online by Cambridge University Press:  24 October 2008

David Aldous
David Aldous
Affiliation:
Department of Statistics, University of California, Berkeley CA 94720, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

For random walks on finite graphs, we record some equalities, inequalities and limit theorems (as the size of graph tends to infinity) which hold for vertex-transitive graphs but not for general regular graphs. The main result is a sharp condition for asymptotic exponentiality of the hitting time to a single vertex. Another result is a lower bound for the coefficient of variation of hitting times. Proofs exploit the complete monotonicity properties of the associated continuous-time walk.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 106 , Issue 1 , July 1989 , pp. 179 - 191
Copyright
Copyright © Cambridge Philosophical Society 1989

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

[1]Aldous, D. J.. An introduction to covering problems for random walks on graphs. J. Theoret. Probab. 2 (1989), 87–89.CrossRefGoogle Scholar
[2]Aldous, D. J.. Markov chains with almost exponential hitting times. Stochastic Process. Appl. 13 (1982), 305–310.CrossRefGoogle Scholar
[3]Aldous, D. J.. Probability Approximations via the Poisson Clumping Heuristic (Springer-Verlag, 1989).CrossRefGoogle Scholar
[4]Aldous, D. J.. Random walks on large graphs. (Unpublished lecture notes, projected monograph.)Google Scholar
[5]Aleliunas, R. et al. Random walks, universal traversal sequences, and the complexity of maze traversal. In Proc. 20th IEEE Found. Comp. Sci. Symp. (IEEE, 1979), pp. 218–233.Google Scholar
[6]Asmussen, S.. Applied Probability and Queues (Wiley, 1987).Google Scholar
[7]Biggs, N.. Algebraic Graph Theory (Cambridge University Press, 1974).CrossRefGoogle Scholar
[8]Broder, A. and Karlin, A. R.. Bounds on the cover time. J. Theoret. Probab. 2 (1989), 101–120.CrossRefGoogle Scholar
[9]Cox, J. T.. Coalescing random walks and voter model consensus times on the torus. Ann. Probab. (to appear).Google Scholar
[10]Diaconis, P.. Group Theory in Statistics (Institute of Mathematical Statistics, Hayward CA, 1988).Google Scholar
[11]Doyle, P. G. and Snell, J. L.. Random Walks and Electrical Networks (Mathematical Association of America, 1984).CrossRefGoogle Scholar
[12]Flatto, L., Odlyzko, A. M. and Wales, D. B.. Random shuffles and group representations. Ann. Probab. 13 (1985), 154–178.CrossRefGoogle Scholar
[13]Gobel, F. and Jagers, A. A.. Random walks on graphs. Stochastic Process. Appl. 2 (1974), 311–336.CrossRefGoogle Scholar
[14]Keilson, J.. Markov Chain Models – Rarity and Exponentiality (Springer-Verlag, 1979).CrossRefGoogle Scholar
[15]Kemeny, J. G. and Snell, J. L.. Finite Markov Chains (Van Nostrand. 1969).Google Scholar
[16]Letac, G.. Les fonctions spheriques d'un couple de Gelfand symmetrique et les chaines de Markov. Adv. in Appl. Probab. 14 (1982), 272–294.CrossRefGoogle Scholar
[17]Pitman, J. W.. Occupation measures for Markov chains. Adv. in Appl. Probab. 9 (1977). 69–86.CrossRefGoogle Scholar
[18]Takacs, L.. Random flights on regular graphs. Adv. in Appl. Probab. 16 (1984). 618–637.CrossRefGoogle Scholar
[19]Slijpe, A. R. D. van. Random walks on the triangular prism and other vertex-transitive graphs. J. Comput. Appl. Math. 15 (1986), 383–394.CrossRefGoogle Scholar
[20]Varopoulos, N. T.. Isoperimetric inequalities and Markov chains. J. Funct. Anal. 63 (1985). 215–239.CrossRefGoogle Scholar