Central limit theorem for biased random walk on multi-type Galton-Watson trees

Amir Dembo (Standford University)
Nike Sun (Stanford University)


Let $\mathcal{T}$ be a rooted supercritical multi-type Galton-Watson (MGW) tree with types coming from a finite alphabet, conditioned to non-extinction. The $\lambda$-biased random walk $(X_t)_{t\ge0}$ on $\mathcal{T}$ is the nearest-neighbor random walk which, when at a vertex $v$ with $d_v$ offspring, moves closer to the root with probability $\lambda/(\lambda+d_v)$, and to each of the offspring with probability $1/(\lambda+d_v)$. This walk is recurrent for $\lambda\ge\rho$ and transient for $0\le\lambda<\rho$, with $\rho$ the Perron-Frobenius eigenvalue for the (assumed) irreducible matrix of expected offspring numbers. Subject to finite moments of order $p>4$ for the offspring distributions, we prove the following quenched CLT for $\lambda$-biased random walk at the critical value $\lambda=\rho$: for almost every $\mathcal{T}$, the process $|X_{\lfloor nt \rfloor}|/\sqrt{n}$ converges in law as $n\to\infty$ to a reflected Brownian motion rescaled by an explicit constant. This result was proved under some stronger assumptions by Peres-Zeitouni (2008) for single-type Galton-Watson trees. Following their approach, our proof is based on a new explicit description of a reversing measure for the walk from the point of view of the particle (generalizing the measure constructed in the single-type setting by Peres-Zeitouni), and the construction of appropriate harmonic coordinates. In carrying out this program we prove moment and conductance estimates for MGW trees, which may be of independent interest. In addition, we extend our construction of the reversing measure to a biased random walk with random environment (RWRE) on MGW trees, again at a critical value of the bias. We compare this result against a transience-recurrence criterion for the RWRE generalizing a result of Faraud (2011) for Galton-Watson trees.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-40

Publication Date: September 6, 2012

DOI: 10.1214/EJP.v17-2294


  • Aïdékon, Elie, Speed of the biased random walk on a Galton-Watson tree, Preprint, arXiv:1111.4313v3, 2011.
  • Athreya, Krishna B.; Ney, Peter E. Branching processes. Die Grundlehren der mathematischen Wissenschaften, Band 196. Springer-Verlag, New York-Heidelberg, 1972. xi+287 pp. MR0373040
  • Ben Arous, Gérard; Fribergh, Alexander; Gantert, Nina; Hammond, Alan. Biased random walks on Galton-Watson trees with leaves. Ann. Probab. 40 (2012), no. 1, 280-338. MR2917774
  • Billingsley, Patrick. Probability and measure. Third edition. Wiley Series in Probability and Mathematical Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1995. xiv+593 pp. ISBN: 0-471-00710-2 MR1324786
  • Bingham, N. H.; Doney, R. A. Asymptotic properties of supercritical branching processes. I. The Galton-Watson process. Advances in Appl. Probability 6 (1974), 711-731. MR0362525
  • Bolthausen, Erwin; Sznitman, Alain-Sol. On the static and dynamic points of view for certain random walks in random environment. Special issue dedicated to Daniel W. Stroock and Srinivasa S. R. Varadhan on the occasion of their 60th birthday. Methods Appl. Anal. 9 (2002), no. 3, 345-375. MR2023130
  • Boyd, Stephen; Vandenberghe, Lieven. Convex optimization. Cambridge University Press, Cambridge, 2004. xiv+716 pp. ISBN: 0-521-83378-7 MR2061575
  • Bramson, M.; Ney, P.; Tao, J. The population composition of a multitype branching random walk. Ann. Appl. Probab. 2 (1992), no. 3, 575-596. MR1177900
  • D. A. Croydon, A. Fribergh, and T. Kumagai, phBiased random walk on critical Galton-Watson trees conditioned to survive, Preprint, arXiv:1203.4078, 2012.
  • Dembo, Amir; Zeitouni, Ofer. Large deviations techniques and applications. Second edition. Applications of Mathematics (New York), 38. Springer-Verlag, New York, 1998. xvi+396 pp. ISBN: 0-387-98406-2 MR1619036
  • Durrett, Rick. Probability: theory and examples. Fourth edition. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2010. x+428 pp. ISBN: 978-0-521-76539-8 MR2722836
  • Ethier, Stewart N.; Kurtz, Thomas G. Markov processes. Characterization and convergence. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York, 1986. x+534 pp. ISBN: 0-471-08186-8 MR0838085
  • Faraud, Gabriel. A central limit theorem for random walk in a random environment on marked Galton-Watson trees. Electron. J. Probab. 16 (2011), no. 6, 174-215. MR2754802
  • W. Feller, phAn introduction to probability theory and its applications. Vol. II., 2nd ed., John Wiley & Sons Inc., New York, 1971. MRMR0270403 (42 #5292)
  • Harris, Theodore E. The theory of branching processes. Die Grundlehren der Mathematischen Wissenschaften, Bd. 119 Springer-Verlag, Berlin; Prentice-Hall, Inc., Englewood Cliffs, N.J. 1963 xiv+230 pp. MR0163361
  • Horn, Roger A.; Johnson, Charles R. Matrix analysis. Corrected reprint of the 1985 original. Cambridge University Press, Cambridge, 1990. xiv+561 pp. ISBN: 0-521-38632-2 MR1084815
  • Hu, Yueyun; Shi, Zhan. A subdiffusive behaviour of recurrent random walk in random environment on a regular tree. Probab. Theory Related Fields 138 (2007), no. 3-4, 521-549. MR2299718
  • Kallenberg, Olav. Foundations of modern probability. Second edition. Probability and its Applications (New York). Springer-Verlag, New York, 2002. xx+638 pp. ISBN: 0-387-95313-2 MR1876169
  • Karatzas, Ioannis; Shreve, Steven E. Brownian motion and stochastic calculus. Second edition. Graduate Texts in Mathematics, 113. Springer-Verlag, New York, 1991. xxiv+470 pp. ISBN: 0-387-97655-8 MR1121940
  • Kemeny, John G.; Snell, J. Laurie; Knapp, Anthony W. Denumerable Markov chains. Second edition. With a chapter on Markov random fields, by David Griffeath. Graduate Texts in Mathematics, No. 40. Springer-Verlag, New York-Heidelberg-Berlin, 1976. xii+484 pp. MR0407981
  • Kesten, H.; Stigum, B. P. A limit theorem for multidimensional Galton-Watson processes. Ann. Math. Statist. 37 1966 1211-1223. MR0198552
  • Kurtz, Thomas; Lyons, Russell; Pemantle, Robin; Peres, Yuval. A conceptual proof of the Kesten-Stigum theorem for multi-type branching processes. Classical and modern branching processes (Minneapolis, MN, 1994), 181-185, IMA Vol. Math. Appl., 84, Springer, New York, 1997. MR1601737
  • Kyprianou, Andreas E.; Rahimzadeh Sani, A. Martingale convergence and the functional equation in the multi-type branching random walk. Bernoulli 7 (2001), no. 4, 593-604. MR1849369
  • Liu, Quansheng. On generalized multiplicative cascades. Stochastic Process. Appl. 86 (2000), no. 2, 263-286. MR1741808
  • Lyons, Russell. Random walks and percolation on trees. Ann. Probab. 18 (1990), no. 3, 931-958. MR1062053
  • Lyons, Russell; Pemantle, Robin. Random walk in a random environment and first-passage percolation on trees. Ann. Probab. 20 (1992), no. 1, 125-136. MR1143414
  • Lyons, Russell; Pemantle, Robin; Peres, Yuval. Ergodic theory on Galton-Watson trees: speed of random walk and dimension of harmonic measure. Ergodic Theory Dynam. Systems 15 (1995), no. 3, 593-619. MR1336708
  • Lyons, Russell; Pemantle, Robin; Peres, Yuval. Biased random walks on Galton-Watson trees. Probab. Theory Related Fields 106 (1996), no. 2, 249-264. MR1410689
  • R. Lyons and Y. Peres, phProbability on Trees and Networks, Preprint, 2009.
  • Ney, P. E.; Vidyashankar, A. N. Harmonic moments and large deviation rates for supercritical branching processes. Ann. Appl. Probab. 13 (2003), no. 2, 475-489. MR1970272
  • Pemantle, Robin; Peres, Yuval. Galton-Watson trees with the same mean have the same polar sets. Ann. Probab. 23 (1995), no. 3, 1102-1124. MR1349163
  • Peres, Yuval; Zeitouni, Ofer. A central limit theorem for biased random walks on Galton-Watson trees. Probab. Theory Related Fields 140 (2008), no. 3-4, 595-629. MR2365486
  • Petersen, Karl. Ergodic theory. Corrected reprint of the 1983 original. Cambridge Studies in Advanced Mathematics, 2. Cambridge University Press, Cambridge, 1989. xii+329 pp. ISBN: 0-521-38997-6 MR1073173
  • Petrov, V. V. Sums of independent random variables. Translated from the Russian by A. A. Brown. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 82. Springer-Verlag, New York-Heidelberg, 1975. x+346 pp. MR0388499
  • Williams, David. Probability with martingales. Cambridge Mathematical Textbooks. Cambridge University Press, Cambridge, 1991. xvi+251 pp. ISBN: 0-521-40455-X; 0-521-40605-6 MR1155402
  • Zeitouni, Ofer. Random walks in random environment. Lectures on probability theory and statistics, 189-312, Lecture Notes in Math., 1837, Springer, Berlin, 2004. MR2071631

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.