Consider a Galton-Watson tree with offspring distribution $\text{B}(n,p)$, for some constant $n$ and $p$. Let $a_i$ denote the number of vertices on the $i$'th level of the tree. It then holds that:


$a_{i+1}\sim \text{B}(n\cdot a_i,p)$

I am looking for a probabilistic upper bound on the tree's growth. For example, a Theorem that gives an upper bound on $\Pr(a_i > c\cdot (np)^i)$, for $c>1$, would be nice.

My guess is that something like this should be known, but I haven't managed to locate it so far. I would be thankful if anyone can point me where to look.

  • 1
    $\begingroup$ Are you interested in behavior when $np \lt 1$, $np = 1$ (critical), or $np \gt 1$? For the critical case, is epubs.siam.org/doi/abs/10.1137/1120020 what you want? $\endgroup$ Sep 5 '14 at 20:47
  • $\begingroup$ I am interested in the case where $np>1$. Specifically, $p=\Theta(\frac{\log n}{n})$. $\endgroup$
    – Yonatan
    Sep 6 '14 at 14:15
  • 1
    $\begingroup$ Ok. I would look for "large deviations supercritical Galton-Watson." I think there are several papers studying this, usually with a more general offspring distribution. $\endgroup$ Sep 6 '14 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.