Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees

Authors:
  • LALouigi Addario-Berry
    Louigi Addario-Berry
  • LDLuc Devroye
    Luc Devroye
  • SJSvante Janson
    Svante Janson

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$.
All Related Versions

This publication has 30 references indexed in Scilit: