Width and height of conditioned Galton-Watson trees

Опубликовано 18 августа 2016, 23:03

Consider a random Galton-Watson tree conditioned to have size n. We assume that the offspring distribution has mean 1 and finite variance, but no further moment conditions. It is well-known that the width and height both are of the order n^{1/2} (see for example Aldous (1991) for much more detailed results on the shape). I will talk about about proving tail estimates, for example P(width > k) < exp(-c k^2/n). (Note that no such exponential tail bounds are assumed for the offspring distribution.) The proof uses a finite version of the size-biazed Galton-Watson tree studied by Lyons, Pemantle and Peres (1995). (Joint work with Louigi Addario-Berry and Luc Devroye.)