Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees
Authors:
- Louigi Addario-BerryLALouigi Addario-Berry
- Luc DevroyeLDLuc Devroye
- Svante JansonSJSvante Janson
Open Access
- 1 March 2013
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Probability
- Vol. 41 (2) , 1072-1087
Abstract
We study the height and width of a Galton–Watson tree with offspring distribution $\xi$ satisfying $\mathbb{E} \xi=1$, $0<\operatorname{Var} \xi<\infty$, conditioned on having exactly $n$ nodes. Under this conditioning, we derive sub-Gaussian tail bounds for both the width (largest number of nodes in any level) and height (greatest level containing a node); the bounds are optimal up to constant factors in the exponent. Under the same conditioning, we also derive essentially optimal upper tail bounds for the number of nodes at level $k$, for $1\leq k\leq n$.
Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Simply generated trees, conditioned Galton–Watson trees, random allocations and condensationProbability Surveys, 2012
- On the asymptotic joint distribution of height and width in random treesStudia Scientiarum Mathematicarum Hungarica, 2008
- Probabilistic and fractal aspects of Lévy treesProbability Theory and Related Fields, 2004
- SOME REMARKS ABOUT THE I ENTITY IN LAW FOR THE BESSEL BRIDGEStudia Scientiarum Mathematicarum Hungarica, 2001
- On the profile of random treesRandom Structures & Algorithms, 1997
- On the Altitude of Nodes in Random TreesCanadian Journal of Mathematics, 1978
- The Galton-Watson process conditioned on the total progenyJournal of Applied Probability, 1975
- The total progeny in a branching process and a related random walkJournal of Applied Probability, 1969
- On the height of treesJournal of the Australian Mathematical Society, 1967
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963