Consider the Galton-Watson tree with offspring distribution $X$ given by $P(X=k) = (1-p)^kp$. Let $D$ be the depth of the process. My question is how to calculate for which values of $p$ we have $\mathbb{E}D<\infty$.

Explanation of terms: a Galton-Watson tree consists of generations. For example the first generation consists of $2$ people (probability $p(1-p)^2$), the second one consists of the children of these two and their amount is also geometric($p$) distributed, and so on, so they continue multiplying in a geometric way.

The depth is defined by the largest generation which has $>0$ children. A result given in my lecture notes is that $P(D\leq t) = G\circ ...\circ G(s)(0)$ where there are $t$ times a $G$, and $G(s)$ is the pgf. So here it looks like a continued fraction.

The lecture's first question is to calculate $P(D=t)$, so I did $P(D\leq t) - P(D<t)$. The next question is for which values $\mathbb{E}D<\infty$. I know that for $p>1/2$ the extinction probability is $1$, but unfortunaltely I calculated that for $p=1/2$, $\mathbb{E}D=\infty$, otherwise it was done.

Is there anyone who can help? Thanks in advance.

  • $\begingroup$ $\newcommand{\P}{\mathbb{P}}\newcommand{\E}{\mathbb{E}}$Do you have an expression for $\P(D=t)$ or $\P(D > t)$ for all $t\in\mathbb{N}$ (in terms of $p$ and $t$)? If so, you could use that to try and consider the infinite series expression for $\E[D]$ and try to determine for which $p$ this series is finite. $\endgroup$ – Minus One-Twelfth Mar 21 at 11:48
  • $\begingroup$ Yeah I thought about that, but $\sum_{i=0}^{\infty} P(D>i) $ is too complicated too calculate for all $p$. For $p=1/2$ however, the sum is infinite. $\endgroup$ – Rocco van Vreumingen Mar 21 at 13:19
  • 1
    $\begingroup$ I got an idea. It is for $p>1/2$, because then the average number of children will be $(1-p)/p<1$, so on average the number of children in the next generation decreases non-asymptotically. $\endgroup$ – Rocco van Vreumingen Mar 22 at 11:27
  • 1
    $\begingroup$ Got it. The expected number of children in the $n$-th generation given $k$ in the first generation, $\mathbb{E}(Z_n|Z_1=k)$ say, is of the form $kc^{n-1}$ where $c=\mathbb{E}X = (1-p)/p<1$. So $P(D<n|Z_1=k)=P(Z_n=0|Z_1=k)\geq 1-kc^{n-1}$ and now we can derive the expectation $\mathbb{E}D$ $\endgroup$ – Rocco van Vreumingen Mar 22 at 15:54

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.