2
$\begingroup$

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_0=1$

$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.

$\endgroup$
3
  • 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, 2014 at 20:47
  • $\begingroup$ I am interested in the case where $np>1$. Specifically, $p=\Theta(\frac{\log n}{n})$. $\endgroup$ Sep 6, 2014 at 14:15
  • 2
    $\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, 2014 at 15:20

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.