Local limits of conditioned Galton-Watson trees: the infinite spine case

Romain Abraham (Université d'Orléans)
Jean-François Delmas (École Nationale des Ponts et Chaussées Université Paris-Est)


We give a necessary and sufficient condition for the convergence in distribution of a conditioned Galton-Watson tree to Kesten's tree. This yields elementary proofs of Kesten's result as well as other known results on local limit of conditioned Galton-Watson trees. We then apply this condition to get new results, in the critical and sub-critical cases, on the limit in distribution of a Galton-Watson tree conditioned on having a  large number of individuals with out-degree in a given set.

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

Pages: 1-19

Publication Date: January 3, 2014

DOI: 10.1214/EJP.v19-2747


  • R. Abraham and J.-F. Delmas, Local limits of conditioned Galton-Watson trees : the condensation case, arXiv:1311.6683.
  • Abraham, Romain; Delmas, Jean-François; He, Hui. Pruning Galton-Watson trees and tree-valued Markov processes. Ann. Inst. Henri Poincaré Probab. Stat. 48 (2012), no. 3, 688--705. MR2976559
  • Asmussen, Søren; Foss, Serguei; Korshunov, Dmitry. Asymptotics for sums of random variables with local subexponential behaviour. J. Theoret. Probab. 16 (2003), no. 2, 489--518. MR1982040
  • 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
  • Billingsley, Patrick. Convergence of probability measures. Second edition. Wiley Series in Probability and Statistics: Probability and Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1999. x+277 pp. ISBN: 0-471-19745-9 MR1700749
  • N. Curien and I. Kortchemski, Random non-crossing plane configurations: a conditioned Galton-Watson tree approach, Random Struct. and Alg. To appear (2014).
  • Duquesne, Thomas. A limit theorem for the contour process of conditioned Galton-Watson trees. Ann. Probab. 31 (2003), no. 2, 996--1027. MR1964956
  • Dwass, Meyer. The total progeny in a branching process and a related random walk. J. Appl. Probability 6 1969 682--686. MR0253433
  • Geiger, Jochen; Kauffmann, Lars. The shape of large Galton-Watson trees with possibly infinite variance. Random Structures Algorithms 25 (2004), no. 3, 311--335. MR2086163
  • Hawkes, John. Trees generated by a simple branching process. J. London Math. Soc. (2) 24 (1981), no. 2, 373--384. MR0631950
  • Ibragimov, I. A.; Linnik, Yu. V. Independent and stationary sequences of random variables. With a supplementary chapter by I. A. Ibragimov and V. V. Petrov. Translation from the Russian edited by J. F. C. Kingman. Wolters-Noordhoff Publishing, Groningen, 1971. 443 pp. MR0322926
  • Janson, Svante. Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Probab. Surv. 9 (2012), 103--252. MR2908619
  • Joffe, A.; Waugh, W. A. O'N. Exact distributions of kin numbers in a Galton-Watson process. J. Appl. Probab. 19 (1982), no. 4, 767--775. MR0675140
  • Jonsson, Thordur; Stefánsson, Sigurdur Örn. Condensation in nongeneric trees. J. Stat. Phys. 142 (2011), no. 2, 277--313. MR2764126
  • Kennedy, Douglas P. The Galton-Watson process conditioned on the total progeny. J. Appl. Probability 12 (1975), no. 4, 800--806. MR0386042
  • Kesten, Harry. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 4, 425--487. MR0871905
  • Kortchemski, Igor. Invariance principles for Galton-Watson trees conditioned on the number of leaves. Stochastic Process. Appl. 122 (2012), no. 9, 3126--3172. MR2946438
  • Kortchemski, Igor. Limit theorems for conditioned non-generic Galton-Watson trees, arXiv:1205.3145, 2012.
  • Lyons, Russell; Pemantle, Robin; Peres, Yuval. Conceptual proofs of $L\log L$ criteria for mean behavior of branching processes. Ann. Probab. 23 (1995), no. 3, 1125--1138. MR1349164
  • Minami, Nariyuki. On the number of vertices with a given degree in a Galton-Watson tree. Adv. in Appl. Probab. 37 (2005), no. 1, 229--264. MR2135161
  • Nagaev, S. V.; Vakhtel, V. I. Limit theorems for probabilities of large deviations of a Galton-Watson process. (Russian) Diskret. Mat. 15 (2003), no. 1, 3--27; translation in Discrete Math. Appl. 13 (2003), no. 1, 1--26 MR1996743
  • Nagaev, S. V.; Vakhtel, V. I., On a local limit theorem for a critical Galton-Watson process, Teor. Veroyatn. Primen. 50 (2005), no. 3, 457--479. MR2223212 (2007g:60100)
  • 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
  • D. Rizzolo, Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set, Ann. Inst. H. Poincaré Probab. Statist., To appear (2014).
  • Spitzer, Frank. Principles of random walk. Second edition. Graduate Texts in Mathematics, Vol. 34. Springer-Verlag, New York-Heidelberg, 1976. xiii+408 pp. MR0388547

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