Abstract
Let \({\mathcal{T}}\) be a rooted Galton–Watson tree with offspring distribution {p k } that has p 0 = 0, mean m = ∑ kp k > 1 and exponential tails. Consider the λ-biased random walk {X n } n ≥ 0 on \({\mathcal{T}}\) ; this is the nearest neighbor random walk which, when at a vertex v with d v offspring, moves closer to the root with probability λ/(λ + d v ), and moves to each of the offspring with probability 1/(λ + d v ). It is known that this walk has an a.s. constant speed \({\tt v} = \lim_n |X_n|/n\) (where |X n | is the distance of X n from the root), with \({\tt v} > 0\) for 0 < λ < m and \({\tt v} = 0\) for λ ≥ m. For all λ ≤ m, we prove a quenched CLT for \(|X_n| - n{\tt v}\) . (For λ > m the walk is positive recurrent, and there is no CLT.) The most interesting case by far is λ = m, where the CLT has the following form: for almost every \({\mathcal{T}}\) , the ratio \(|X_{[nt]}|/\sqrt{n}\) converges in law as n → ∞ to a deterministic multiple of the absolute value of a Brownian motion. Our approach to this case is based on an explicit description of an invariant measure for the walk from the point of view of the particle (previously, such a measure was explicitly known only for λ = 1) and the construction of appropriate harmonic coordinates.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Athreya K.B. (1994). Large deviation rates for branching processes. I. Single type case. Ann. Appl. Probab. 4: 779–790
Athreya K.B. and Ney P. (1972). Branching Processes. Springer, Heidelberg
Athreya K.B. and Ney P. (1978). A new approach to the limit theory of recurrent Markov chains. Trans. Am. Math. Soc. 245: 493–501
Azuma K. (1967). Weighted sums of certain dependent random variables. Tôhoku Math. J. 19: 357–367
Berger N. and Biskup M. (2007). Quenched invariance principle for simple random walk on percolation clusters. Probab. Theory Relat. Fields 137: 83–120
Billingsley P. (1999). Convergence of Probability Measures. Wiley, New York
Bolthausen E. and Sznitman A.-S. (2002). On the static and dynamic points of view for certain random walks in random environment. Methods Appl. Anal. 9: 345–375
Bolthausen E., Sznitman A.-S. and Zeitouni O. (2003). Cut points and diffusive random walks in random environments. Ann. Inst. H. Poincare 39: 527–555
Carne T.K. (1985). A transmutation formula for Markov chains. Bull Sci. Math. 109: 399–405
Dembo A., Gantert N., Peres Y. and Zeitouni O. (2001). Large deviations for random walks on Galton–Watson trees: averaging and uncertainty. Probab. Theory Relat. Fields 122: 241–288
Doyle, P.G., Snell, J.L.: Random walks and electric networks. Carus Mathematical Monographs, vol. 22. Mathematical Association of America, Washington, DC (1984)
Karatzas I. and Shreve S. (1988). Brownian Motion and Stochastic Calculus, 2nd edn. Springer, Heidelberg
Kozlov S.M. (1985). The method of averaging and walks in inhomogeneous environments. Russ. Math. Surv. 40: 73–145
Lyons R. (1990). Random walks and percolation on trees. Ann. Probab. 18: 931–958
Lyons,R., with Peres, Y.: Probability on trees and networks. Available at http://mypage.iu. edu/~rdlyons/prbtree/prbtree.html
Lyons R., Pemantle R. and Peres Y. (1995). Conceptual proofs of L log L iteria for mean behavior of branching processes. Ann. Probab. 23: 1125–1138
Lyons R., Pemantle R. and Peres Y. (1995). Ergodic theory on Galton–Watson trees: speed of random walk and dimension of harmonic measure. Ergod. Theory Dyn. Syst. 15: 593–619
Lyons R., Pemantle R. and Peres Y. (1996). Biased random walks on Galton–Watson trees. Probab. Theory Relat. Fields 106: 249–264
Ney P.E. and Vidyashankar A.N. (2003). Harmonic moments and large deviation rates for superitical branching processes. Ann. Appl. Probab. 13: 475–489
Pemantle R. and Peres Y. (1995). Galton–Watson trees with the same mean have the same polar sets. Ann. Probab. 23: 1102–1124
Piau D. (1998). Théorème central limite fonctionnel pour une marche au hasard en environment aléatoire. Ann. Probab. 26: 1016–1040
Sidoravicius V. and Sznitman A.-S. (2004). Quenched invariance principles for walks on clusters of percolation or among random conductances. Probab. Theory Relat. Fields 129: 219–244
Sznitman A.-S. (2000). Slowdown estimates and central limit theorem for random walks in random environment. J. Eur. Math. Soc. 2: 93–143
Varopoulos N.Th. (1985). Long range estimates for Markov chains. Bull. Sci. Math. 109: 225–252
Zeitouni, O.: Random walks in random environment. XXXI Summer school in probability, St Flour (2001). Lecture notes in Mathematics, vol. 1837, pp. 193–312. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
Y. Peres research was partially supported by MSRI and by NSF grants #DMS-0104073 and #DMS-0244479. O. Zeitouni research was partially supported by MSRI and by NSF grants #DMS-0302230 and DMS-0503775.
Rights and permissions
About this article
Cite this article
Peres, Y., Zeitouni, O. A central limit theorem for biased random walks on Galton–Watson trees. Probab. Theory Relat. Fields 140, 595–629 (2008). https://doi.org/10.1007/s00440-007-0077-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-007-0077-y