Sub-Gaussian tail bounds for the width and height of conditioned Galton--Watson trees
Preprint
Abstract
We study the height and width of a Galton--Watson tree with offspring distribution B satisfying E(B)=1, 0 < Var(B) < infinity, 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 <= k <= n.Keywords
All Related Versions
- Version 1, 2010-11-18, ArXiv
- Published version: The Annals of Probability, 41 (2), 1072.
This publication has 11 references indexed in Scilit:
- On the asymptotic joint distribution of height and width in random treesStudia Scientiarum Mathematicarum Hungarica, 2008
- Random cutting and records in deterministic and random treesRandom Structures & Algorithms, 2005
- Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excursionsBulletin of the American Mathematical Society, 2001
- SOME REMARKS ABOUT THE I ENTITY IN LAW FOR THE BESSEL BRIDGEStudia Scientiarum Mathematicarum Hungarica, 2001
- The height and width of simple trees2000
- Branching Processes and Their Applications in the Analysis of Tree Structures and Tree Algorithms1998
- Conceptual Proofs of $L$ Log $L$ Criteria for Mean Behavior of Branching ProcessesThe Annals of Probability, 1995
- The Distribution of Heights of Binary Trees and Other Simple TreesCombinatorics, Probability and Computing, 1993
- The average height of binary trees and other simple treesJournal of Computer and System Sciences, 1982
- On the Altitude of Nodes in Random TreesCanadian Journal of Mathematics, 1978