Width and height of conditioned Galton-Watson trees

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 n1/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 k2/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.)

©2010 Microsoft Corporation. All rights reserved.
  • SpeakerSvante Janson
  • HostYuval Peres
  • AffiliationUppsala University
  • Duration00:51:56
  • Date recorded7 May 2010
  • Share
    Share this page on Facebook
    Share this page on Twitter
    Share this page on LinkedIn
    E-mail this page
    RSS feeds