zbMATH — the first resource for mathematics

On the speed of random walks on graphs. (English) Zbl 1044.60034
Summary: R. Lyons, R. Pemantle and Y. Peres [in: Classical and modern branching processes. IMA Vol. Math. Appl. 84, 223–237 (1997; Zbl 0867.60067)] asked whether the asymptotic lower speed in an infinite tree is bounded by the asymptotic speed in the regular tree with the same average number of branches. In the more general setting of random walks on graphs, we establish a bound on the expected value of the exit time from a vertex set in terms of the size and distance from the origin of its boundary, and prove this conjecture. We give sharp bounds for limiting speed (or, when applicable, sublinear rate of escape) in terms of growth properties of the graph. For trees, we get a bound for the speed in terms of the Hausdorff dimension of the harmonic measure on the boundary. As a consequence, two conjectures of Lyons, Pemantle and Peres are resolved, and a new bound is given for the dimension of the harmonic measure defined by the biased random walk on a Galton-Watson tree.

60G50 Sums of independent random variables; random walks
05C90 Applications of graph theory
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Full Text: DOI Euclid
[1] Benjamini, I. and Peres, Y. (1992). Random walks on a tree and capacity in the interval. Ann. Inst. H. Poincaré Probab. Statist. 28 557-592. · Zbl 0767.60061
[2] Chen, D. (1997). Average properties of random walks on Galton-Watson trees. Ann. Inst. H. Poincaré Probab. Statist. 33 359-369. · Zbl 0894.60065
[3] Doob, J. L. (1959). Discrete potential theory and boundaries. J. Math. Mech. 8 433-458. (Erratum: 993.) · Zbl 0101.11503
[4] Häggstr öm, O. (1997). Infinite clusters in dependent automorphism invariant percolation on trees. Ann. Probab. 25 1423-1436. · Zbl 0895.60098
[5] Hawkes, T. E. (1981). Trees generated by a simple branching process. J. London Math. Soc. (2) 24 373-384. · Zbl 0468.60081
[6] Lee, S. (1994). Ph.D. dissertation, Cornell Univ. · Zbl 0925.93449
[7] Lyons, R. (1990). Random walks and percolation on trees. Ann. Probab. 18 931-958. · Zbl 0714.60089
[8] Lyons, R., Pemantle, R. and Peres, Y. (1995). Ergodictheory on Galton-Watson trees: speed of random walk and dimension of harmonicmeasure. Ergodic Theory Dynam. Systems 15 593-619. · Zbl 0819.60077
[9] Lyons, R., Pemantle, R. and Peres, Y. (1996). Biased random walks on Galton-Watson trees. Probab. Theory RelatedFields 106 249-264. · Zbl 0859.60076
[10] Lyons, R., Pemantle, R. and Peres, Y. (1997). Unsolved problems concerning random walks on trees. In Classical andModern Branching Processes (K. Athreya and P. Jagers, eds.) 223-238. Springer, New York. · Zbl 0867.60067
[11] Lyons, R. and Peres, Y. (1999). Probability on Trees andNetworks. Cambridge Univ. Press. To appear. Current version available at http://php.indiana.edu/ rdlyons. URL:
[12] Peres, Y. (1997). Probability on Trees: An Introductory Climb. Ecole d’Eté de Saint Flour XXVII. Lecture Notes in Math. 193-280. Springer, Berlin. · Zbl 0957.60001
[13] Sinclair, A. J. and Jerrum, M. R. (1989). Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. Comput. 82 93-133. · Zbl 0668.05060
[14] Takacs, C. (1997). Random walk on periodictrees. Electron J. Probab. 2. · Zbl 0888.60060
[15] Takacs, C. (1998). Biased random walks on directed trees. Probab. Theory RelatedFields 111 123-139. · Zbl 0906.60056
[16] Takacs, C. and Takacs, R. (1998). Random walks on trees and an inequality of means. J. Theoret. Probab. 11 701-714. · Zbl 0913.60054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.