Discrete Mathematics & Theoretical Computer Science, Vol 6, No 2 (2004)

Font Size:  Small  Medium  Large

The Width of Galton-Watson Trees Conditioned by the Size

Michael Drmota, Bernhard Gittenberger


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)pmp where mp 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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page