The Width of Galton-Watson Trees Conditioned by the SizeArticle
Authors: Michael Drmota 1; Bernhard Gittenberger 1
NULL##0000-0002-2639-8227
Michael Drmota;Bernhard Gittenberger
1 Institut für Diskrete Mathematik und Geometrie [Wien]
It is proved that the moments of the width of Galton-Watson trees of size n and with offspring variance σ ^2 are asymptotically given by (σ √n)^pm_p where m_p are the moments of the maximum of the local time of a standard scaled Brownian excursion. This is done by combining a weak limit theorem and a tightness estimate. The method is quite general and we state some further applications.
Louigi Addario-Berry;Luc Devroye;Svante Janson, 2013, Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees, The Annals of Probability, 41, 2, 10.1214/12-aop758, https://doi.org/10.1214/12-aop758.
Michael Drmota, 2004, Stochastic analysis of tree–like data structures, Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences, 460, 2041, pp. 271-307, 10.1098/rspa.2003.1243.