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

By Louigi Addario-Berry, Luc Devroye, Svante Janson. 2010

64 citations recorded by the source corpus.

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.

Subfields: Geometry and Topology, Mathematical Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/ef183640517e0681f7294992a3d05a65bc80cbb0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Scaling Limits of Random Graphs from Subcritical Classes (2014, methodology): “A similar result was shown for critical Galton-Watson random trees by Addario-Berry, Devroye and Janson [1], and our proof of these bounds builds on the methods in that paper.”
Branching random walks (2015, background): “It is also possible to allow the harmonic function h to change from a certain generation on; see Addario-Berry, Devroye and Janson [2] for such an example for the Galton– Watson process.”
Sub-exponential tail bounds for conditioned stable Bienaymé–Galton–Watson trees (2015, methodology): “However, a major difference is that the proof of [2] crucially uses the fact that the width and height of tn are of the same order √ n, which breaks down when μ has infinite variance, and the proof thus requires new ideas.”