Spread of visited sites of a random walk along the generations of a branching process

Pierre Andreoletti (Université d'Orléans)
Pierre Debs (Université d'Orléans)


In this paper we consider a null recurrent random walk in random environment on a super-critical Galton-Watson tree. We consider the case where the log-Laplace transform $\psi$ of the branching process satisfies $\psi(1)=\psi'(1)=0$ for which G. Faraud, Y. Hu and Z. Shi have shown that, with probability one,  the largest generation visited by the walk, until the instant $n$, is of the order of $(\log n)^3$. We already proved that the largest generation entirely visited behaves almost surely like $\log n$ up to a constant. Here we study how the walk visits the generations $\ell=(\log n)^{1+ \zeta}$, with $0 < \zeta <2$. We obtain results in probability giving the asymptotic logarithmic behavior of the number of visited sites at a given generation. We prove that there is a phase transition at generation $(\log n)^2$ for the mean of visited sites until $n$ returns to the root. Also we show that the visited sites spread all over the tree until generation $\ell$.

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

Pages: 1-22

Publication Date: May 4, 2014

DOI: 10.1214/EJP.v19-2790


  • Aidékon, Elie. Tail asymptotics for the total progeny of the critical killed branching random walk. Electron. Commun. Probab. 15 (2010), 522--533. MR2737710
  • Aidékon, Elie; Hu, Yueyun; Zindy, Olivier. The precise tail behavior of the total progeny of a killed branching random walk. Ann. Probab. 41 (2013), no. 6, 3786--3878. MR3161464
  • P. Andreoletti and P. Debs. The number of generations entirely visited for recurrent random walks on random environment. J. Theoret. Probab., To be published.
  • 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
  • Biggins, J. D.; Kyprianou, A. E. Seneta-Heyde norming in the branching random walk. Ann. Probab. 25 (1997), no. 1, 337--360. MR1428512
  • Bingham, N. H. On the limit of a supercritical branching process. A celebration of applied probability. J. Appl. Probab. 1988, Special Vol. 25A, 215--228. MR0974583
  • Caravenna, Francesco. A local limit theorem for random walks conditioned to stay positive. Probab. Theory Related Fields 133 (2005), no. 4, 508--530. MR2197112
  • 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
  • Faraud, Gabriel; Hu, Yueyun; Shi, Zhan. Almost sure convergence for stochastically biased random walks on trees. Probab. Theory Related Fields 154 (2012), no. 3-4, 621--660. MR3000557
  • Fleischmann, Klaus; Wachtel, Vitali. Lower deviation probabilities for supercritical Galton-Watson processes. Ann. Inst. H. Poincaré Probab. Statist. 43 (2007), no. 2, 233--255. MR2303121
  • Fleischmann, Klaus; Wachtel, Vitali. On the left tail asymptotics for the limit law of supercritical Galton-Watson processes in the Böttcher case. Ann. Inst. Henri Poincaré Probab. Stat. 45 (2009), no. 1, 201--225. MR2500235
  • Hu, Yueyun; Shi, Zhan. Slow movement of random walk in random environment on a regular tree. Ann. Probab. 35 (2007), no. 5, 1978--1997. MR2349581
  • Hu, Yueyun; Shi, Zhan. Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees. Ann. Probab. 37 (2009), no. 2, 742--789. MR2510023
  • McDiarmid, Colin. Minimal positions in a branching random walk. Ann. Appl. Probab. 5 (1995), no. 1, 128--139. MR1325045
  • Menshikov, Mikhail; Petritis, Dimitri. On random walks in random environment on trees and their relationship with multiplicative chaos. Mathematics and computer science, II (Versailles, 2002), 415--422, Trends Math., Birkhäuser, Basel, 2002. MR1940150
  • Neveu, J. Arbres et processus de Galton-Watson. (French) [Galton-Watson trees and processes] Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 2, 199--207. MR0850756
  • 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
  • Shi, Zhan. Random walks and trees. X Symposium on Probability and Stochastic Processes and the First Joint Meeting France-Mexico of Probability, 1--39, ESAIM Proc., 31, EDP Sci., Les Ulis, 2011. MR2857100
  • Spitzer, Frank. Principles of random walk. The University Series in Higher Mathematics D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto-London 1964 xi+406 pp. MR0171290

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