Limit theorems for conditioned non-generic Galton–Watson trees
Annales de l'I.H.P. Probabilités et statistiques, Volume 51 (2015) no. 2, p. 489-511
We study a particular type of subcritical Galton–Watson trees, which are called non-generic trees in the physics community. In contrast with the critical or supercritical case, it is known that condensation appears in certain large conditioned non-generic trees, meaning that with high probability there exists a unique vertex with macroscopic degree comparable to the total size of the tree. Using recent results concerning subexponential distributions, we investigate this phenomenon by studying scaling limits of such trees and show that the situation is completely different from the critical case. In particular, the height of such trees grows logarithmically in their size. We also study fluctuations around the condensation vertex.
Nous étudions une classe particulière d’arbres de Galton–Watson sous-critiques, appelés arbres non-génériques en physique. Contrairement au cas critique ou surcritique, il est connu qu’une condensation apparaît dans certains grands arbres non-génériques conditionnés, c’est-à-dire qu’avec grande probabilité il existe un unique sommet de degré macroscopique comparable à la taille totale de l’arbre. En utilisant des résultats récents relatifs à des lois sousexponentielles, nous étudions ce phénomène en étudiant les limites d’échelles de tels arbres et montrons que la situation est complètement différente du cas critique. En particulier, la hauteur de ces arbres croît logarithmiquement en leur taille. Nous étudions aussi les fluctuations autour du sommet de condensation.
DOI : https://doi.org/10.1214/13-AIHP580
Classification:  60J80,  60F17,  05C80,  05C05
Keywords: condensation, subcritical Galton–Watson trees, scaling limits, subexponential distributions
@article{AIHPB_2015__51_2_489_0,
     author = {Kortchemski, Igor},
     title = {Limit theorems for conditioned non-generic Galton--Watson trees},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {51},
     number = {2},
     year = {2015},
     pages = {489-511},
     doi = {10.1214/13-AIHP580},
     mrnumber = {3335012},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2015__51_2_489_0}
}
Kortchemski, Igor. Limit theorems for conditioned non-generic Galton–Watson trees. Annales de l'I.H.P. Probabilités et statistiques, Volume 51 (2015) no. 2, pp. 489-511. doi : 10.1214/13-AIHP580. http://www.numdam.org/item/AIHPB_2015__51_2_489_0/

[1] D. Aldous. The continuum random tree. III. Ann. Probab. 21 (1993) 248–289. | MR 1207226 | Zbl 0791.60009

[2] I. Armendáriz and M. Loulakis. Conditional distribution of heavy tailed random variables on large deviations of their sum. Stochastic Process. Appl. 121 (2011) 1138–1147. | MR 2775110 | Zbl 1218.60021

[3] K. B. Athreya and P. E. Ney. Branching Processes. Die Grundlehren der Mathematischen Wissenschaften 196. Springer, New York, 1972. | MR 373040 | Zbl 0259.60002

[4] P. Bialas, Z. Burda and D. Johnston. Condensation in the backgammon model. Nuclear Phys. B 493 (1997) 505. | Zbl 0942.82033

[5] P. Billingsley. Convergence of Probability Measures, 2nd edition. Wiley Series in Probability and Statistics: Probability and Statistics. Wiley, New York, 1999. | MR 1700749 | Zbl 0172.21201

[6] N. H. Bingham, C. M. Goldie and J. L. Teugels. Regular Variation. Encyclopedia of Mathematics and its Applications 27. Cambridge Univ. Press, Cambridge, 1989. | MR 1015093 | Zbl 0667.26003

[7] D. Burago, Y. Burago and S. Ivanov. A Course in Metric Geometry. Graduate Studies in Mathematics 33. Amer. Math. Soc., Providence, RI, 2001. | MR 1835418 | Zbl 0981.51016

[8] N. Curien and I. Kortchemski. Percolation on random triangulations and stable looptrees. Preprint. Available at arXiv:1307:6818. | MR 3405619 | Zbl 1342.60164

[9] N. Curien and I. Kortchemski. Random non-crossing plane configurations: A conditioned Galton–Watson tree approach. Random Structures Algorithms. To appear, 2015. | MR 3245291 | Zbl 1301.05310

[10] D. Denisov, A. B. Dieker and V. Shneer. Large deviations for random walks under subexponentiality: The big-jump domain. Ann. Probab. 36 (2008) 1946–1991. | MR 2440928 | Zbl 1155.60019

[11] T. Duquesne. A limit theorem for the contour process of conditioned Galton–Watson trees. Ann. Probab. 31 (2003) 996–1027. | MR 1964956 | Zbl 1025.60017

[12] R. Durrett. Conditioned limit theorems for random walks with negative drift. Z. Wahrsch. Verw. Gebiete 52 (1980) 277–287. | MR 576888 | Zbl 0416.60021

[13] S. Großkinsky, G. M. Schütz and H. Spohn. Condensation in the zero range process: Stationary and dynamical properties. J. Stat. Phys. 113 (2003) 389–410. | MR 2013129 | Zbl 1081.82010

[14] C. R. Heathcote, E. Seneta and D. Vere-Jones. A refinement of two theorems in the theory of branching processes. Teor. Verojatnost. i Primenen. 12 (1967) 341–346. | MR 217889 | Zbl 0166.14202

[15] J. Jacod and A. N. Shiryaev. Limit Theorems for Stochastic Processes, 2nd edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 288. Springer, Berlin, 2003. | MR 1943877 | Zbl 1018.60002

[16] S. Janson. Rounding of continuous random variables and oscillatory asymptotics. Ann. Probab. 34 (2006) 1807–1826. | MR 2271483 | Zbl 1113.60017

[17] S. Janson. Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation. Probab. Surv. 9 (2012) 103–252. | MR 2908619 | Zbl 1244.60013

[18] S. Janson and S. O. Stefánsson. Scaling limits of random planar maps with a unique large face. Ann. Probab. To appear, 2015. Available at arXiv:1212.5072. | MR 3342658

[19] I. Jeon, P. March and B. Pittel. Size of the largest cluster under zero-range invariant measures. Ann. Probab. 28 (2000) 1162–1194. | MR 1797308 | Zbl 1023.60084

[20] T. Jonsson and S. O. Stefánsson. Condensation in nongeneric trees. J. Stat. Phys. 142 (2011) 277–313. | MR 2764126 | Zbl 1225.60140

[21] D. P. Kennedy. The Galton–Watson process conditioned on the total progeny. J. Appl. Probab. 12 (1975) 800–806. | MR 386042 | Zbl 0322.60072

[22] H. Kesten. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. Henri Poincaré Probab. Stat. 22 (1986) 425–487. | Numdam | MR 871905 | Zbl 0632.60106

[23] H. Kesten and B. Pittel. A local limit theorem for the number of nodes, the height, and the number of final leaves in a critical branching process tree. Random Structures Algorithms 8 (1996) 243–299. | MR 1603252 | Zbl 0856.60030

[24] I. Kortchemski. A simple proof of Duquesne’s theorem on contour processes of conditioned Galton–Watson trees. In Séminaire de Probabilités XLV 537–558. Lecture Notes in Math. 2078. Springer, New York, 2013. | MR 3185928 | Zbl 1286.60087

[25] I. Kortchemski. Invariance principles for Galton–Watson trees conditioned on the number of leaves. Stochastic Process. Appl. 122 (2012) 3126–3172. | MR 2946438 | Zbl 1259.60103

[26] J.-F. Le Gall. Random trees and applications. Probab. Surveys 2 (2005) 245–311. | MR 2203728 | Zbl 1189.60161

[27] J.-F. Le Gall. Random real trees. Ann. Fac. Sci. Toulouse Math. (6) 15 (2006) 35–62. | Numdam | MR 2225746 | Zbl 1129.60047

[28] J.-F. Le Gall. Itô’s excursion theory and random trees. Stochastic Process. Appl. 120 (2010) 721–749. | MR 2603061 | Zbl 1191.60093

[29] J. Pitman. Combinatorial Stochastic Processes. Lectures from the 32nd Summer School on Probability Theory Held in Saint-Flour, July 7–24, 2002. Lecture Notes in Math. 1875. Springer, Berlin, 2006. | MR 2245368 | Zbl 1103.60004

[30] 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. Henri Poincaré Probab. Stat. 51 (2) (2015) 512–532. | Numdam | MR 3335013

[31] L. Takács. Combinatorial Methods in the Theory of Stochastic Processes. Robert E. Krieger Publishing Co., Huntington, NY, 1977. Reprint of the 1967 original. | MR 431313 | Zbl 0376.60016