Metadata
Abstract
We establish lower tail bounds for the height, and upper tail bounds for the width, of critical size-conditioned Bienaymé trees. Our bounds are optimal at this level of generality. We also obtain precise height and width asymptotics when the trees’ offspring distributions lie within the domain of attraction of a Cauchy distribution and satisfy a local regularity condition. Finally, we pose some questions on the possible asymptotic behaviours of the height and width of critical size-conditioned Bienaymé trees.
References
[AB19] Most trees are short and fat, Probab. Theory Relat. Fields, Volume 173 (2019), pp. 1-26 | DOI | Zbl
[ABBHK22] Universal height and width bounds for random trees, Electron. J. Probab., Volume 27 (2022), 118 | DOI | MR | Zbl
[ABBRD + 23] The Foata–Fuchs proof of Cayley’s formula, and its probabilistic uses, Electron. Commun. Probab., Volume 28 (2023), 17 | DOI | MR | Zbl
[ABD24] Random trees have height , Ann. Probab., Volume 52 (2024) no. 6, pp. 2238-2280 | DOI | MR | Zbl
[ABDJ13] Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees, Ann. Probab., Volume 41 (2013) no. 2, pp. 1072-1087 | DOI | MR | Zbl
[Ald93] The continuum random tree. III, Ann. Probab., Volume 21 (1993) no. 1, pp. 248-289 | DOI | MR | Zbl
[Ber19] Notes on random walks in the Cauchy domain of attraction, Probab. Theory Relat. Fields, Volume 175 (2019) no. 1-2, pp. 1-44 | DOI | MR | Zbl
[BGT89] Regular variation, Encyclopedia of Mathematics and Its Applications, 27, Cambridge University Press, 1989 | MR | Zbl
[BS71] Slowly varying functions and asymptotic relations, J. Math. Anal. Appl., Volume 34 (1971) no. 2, pp. 302-315 | DOI | MR | Zbl
[Duq03] A limit theorem for the contour process of conditioned Galton–Watson trees, Ann. Probab., Volume 31 (2003) no. 2, pp. 996-1027 | DOI | MR | Zbl
[DW17] Decomposition of Lévy trees along their diameter, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 53 (2017) no. 2, pp. 539-593 | DOI | MR | Zbl
[Fel71] An Introduction to Probability Theory and Its Applications. Vol. II, John Wiley & Sons, 1971 | MR | Zbl
[FF70] Réarrangements de fonctions et dénombrement, J. Comb. Theory, Volume 8 (1970) no. 4, pp. 361-375 | DOI | MR | Zbl
[Har63] The Theory of Branching Processes, Grundlehren der Mathematischen Wissenschaften, 119, Springer, 1963 | MR | Zbl
[HSVJ67] A refinement of two theorems in the theory of branching processes, Theory Probab. Appl., Volume 12 (1967) no. 2, pp. 297-301 | DOI | Zbl
[Jan12] Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation, Probab. Surv., Volume 9 (2012), pp. 103-252 | DOI | MR | Zbl
[JS11] Condensation in nongeneric trees, J. Stat. Phys., Volume 142 (2011), pp. 277-313 | DOI | MR | Zbl
[Kol38] Zur lösung einer biologischen aufgabe, Mitt. Forsch.-Inst. Math. Mech. Kujbyschew-Univ. Tomsk, Volume 2 (1938) no. 1, pp. 1-12 | Zbl
[Kor13] A simple proof of Duquesne’s theorem on contour processes of conditioned Galton–Watson trees, Séminaire de probabilités. XLV (Lecture Notes in Mathematics), Volume 2078, Springer, 2013, pp. 537-558 | DOI | Zbl
[Kor15] Limit theorems for conditioned non-generic Galton–Watson trees, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 51 (2015) no. 2, pp. 489-511 | DOI | Numdam | MR | Zbl
[Kor17] Sub-exponential tail bounds for conditioned stable Bienaymé–Galton–Watson trees, Probab. Theory Relat. Fields, Volume 168 (2017) no. 1-2, pp. 1-40 | DOI | MR | Zbl
[KR19] Condensation in critical Cauchy Bienaymé–Galton–Watson trees, Ann. Appl. Probab., Volume 29 (2019) no. 3, pp. 1837-1877 | DOI | Zbl
[Le05] Random trees and applications, Probab. Surv., Volume 2 (2005), pp. 245-311 | DOI | MR | Zbl
[LJ98] Branching processes in Lévy processes: the exploration process, Ann. Probab., Volume 26 (1998) no. 1, pp. 213-252 | DOI | MR | Zbl
[LS08] Reduced branching processes with very heavy tails, J. Appl. Probab., Volume 45 (2008) no. 1, pp. 190-200 | DOI | MR | Zbl
[Nev86] Arbres et processus de Galton–Watson, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 22 (1986) no. 2, pp. 199-207 | Numdam | MR | Zbl
[NW07] The critical Galton–Watson process without further power moments, J. Appl. Probab., Volume 44 (2007) no. 3, pp. 753-769 | DOI | MR | Zbl
[Pet75] Sums of Independent Random Variables, Ergebnisse der Mathematik und ihrer Grenzgebiete, 82, Springer, 1975
[Pit06] Combinatorial Stochastic Processes, Lecture Notes in Mathematics, 1875, Springer, 2006 (Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002, with a foreword by Jean Picard) | MR | Zbl
[Sla68] A branching process with mean one and possibly infinite variance, Z. Wahrscheinlichkeitstheor. Verw. Geb., Volume 9 (1968) no. 2, pp. 139-145 | DOI | MR | Zbl
[Sze76] Markov processes associated with critical Galton–Watson processes with application to extinction probabilities, Adv. Appl. Probab., Volume 8 (1976) no. 2, pp. 278-295 | MR | Zbl