Find the probability generating function of a GW process

235 Views Asked by At

Consider a Galton-Watson process with offspring distribution $\mathrm{Poisson}(1)$. That is, $\textbf{p}(k) = \frac{e^{-1}}{k!}$. Given this information, and that $P(z) = \sum_{n\geq0}\mathbb{P}_{\textbf{p}}(|T| = n)z^n$, I want to determine $P(z) = e^{zP(z) - 1}$. I can see that I'm close to what I want, but I'm not quite sure how to put all this information together. How do I write $\mathbb{P}_{\textbf{p}}(|T| = n)$ in terms of its offspring distribution?

If that's not the correct route, I'd appreciate a pointer in the right direction.

P.S. I know that $\mathbb{P}_{\textbf{p}}(|T| = n) = \frac{n^{n-1}e^{-n}}{n!}$, however that is part of what I have to show (using Lagrange Inversion) later, so it can't be used to help me here.

1

There are 1 best solutions below

0
On

When branching processes are concerned, conditioning on the first generation often uncovers the recursive structure of the whole object, hence its properties.

In the present case, call $N$ the total size of the random tree $T$ and $L$ the progeny of the ancestor, assuming the branching process starts from an initial population of $1$. If $L=0$, then $N=1$. If $L=k$ with $k\geqslant1$, then each of the $k$ subtrees starting at the children of the ancestor is an independent copy of the whole tree hence $$N=1+N_1+\cdots+N_k,$$ where $(N_i)$ is i.i.d. and independent of $N$ and distributed as $N$. Turning to generating functions, this yields $$E(z^N)=P(L=0)z+\sum_{k\geqslant1}P(L=k)zE(z^{N_1+\cdots+N_k})=P(L=0)z+\sum_{k\geqslant1}P(L=k)zE(z^N)^k.$$ Thus, $$E(z^N)=z\cdot g_L(E(z^N)),\qquad g_L(z)=P(L=0)+\sum_{k\geqslant1}P(L=k)z^k=E(z^L).$$ If $L$ is Poisson $1$, then $g_L(z)=\mathrm e^{-1+z}$, and $P(z)$ in the question is $E(z^N)$ hence

$$P(z)=z\cdot\mathrm e^{P(z)-1}.$$

The identity in the question is different and it probably refers to $M=N-1$ the size of the tree minus its root, rather than to $N$ itself. Then $Q(z)=E(z^M)$ is such that $P(z)=z\cdot Q(z)$ hence $Q(z)$ solves indeed

$$Q(z)=\mathrm e^{z\cdot Q(z)-1}.$$