# An upper bound for the growth of a Galton-Watson tree with binomial offspring distribution

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.

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