Generating functions. The Galton-Watson branching process

Published

8 September 2026

Draft

This lecture note is still being edited: the text may contain typos, inaccuracies, and locally unpolished passages. If you find something, please let the author know (contact information on the course page).

Distributions of random variables taking values in $\mathbb {Z}_+ = \left\{ 0,1,2,\ldots \right\}$ are conveniently analyzed via generating functions. The general idea is very similar to the method of characteristic functions: pass from distributions (i.e., from numerical maps on sigma-algebras), which are not very convenient to work with, to functions on numbers.

1 Generating functions

Recall that the characteristic function of a random variable is defined as:

\[ \varphi _{\xi }(t) := \mathbb {E}\left[e^{it\xi }\right] = \int _{\mathbb {R}} e^{itx} \; \; \mathbf{P}_{\xi }\left(dx\right) \]

(the second equality is a change of variables in the Lebesgue integral). This is a map from $\mathbb {R}$ to $\mathbb {C}$, i.e., a function on numbers. Moreover, it uniquely characterizes the distribution $\mathbf{P}_{\xi }$ (recall, $\mathbf{P}_{\xi }(B) := \mathbb {P}\left(\xi \in B\right)$, $B \in \mathscr {B}\left(\mathbb {R}\right)$) of the random variable $\xi$.

If $\xi$ takes values in $\mathbb {Z}_+$, it turns out to be more convenient to not use the complex exponential, but simply to form a power series with the probabilities that $\xi$ falls into $0,1,2,\ldots$:

\[ G_{\xi }(z) := \mathbb {E}\left[z^{\xi }\right] = z^0 \cdot \mathbb {P}\left(\xi = 0\right) + z^{1} \cdot \mathbb {P}\left(\xi = 1\right) + \ldots = \sum _{n=0}^{+\infty } \mathbb {P}\left(\xi = n\right) \cdot z^n \]

$G_{\xi }$ is the generating function of $\xi$. It is defined for those $z \in \mathbb {C}$ for which the series converges. The advantage of this approach (in particular, of taking $z$ to be complex) is that methods for working with power series become available to us.

Note that this power series converges absolutely at least for all $z \in \mathbb {C}$ with $\left|z\right| \leq 1$. As a rule, we will consider $z \in [0,1] \subset \mathbb {R}$. Note that in this case the values $G_{\xi }(z)$ also lie in the interval $[0,1]$.

In a slightly more general setting, the generating function of a sequence of real numbers $a = (a_{0}, a_{1}, \ldots )$ is (formally, i.e., initially without much concern for where and how it converges) the power series with these coefficients:

\[ G_{a}(z) := \sum _{k=0}^{+\infty } a_k z^{k} \]

Example 1

A distribution is given.

$X = k_0 \in \mathbb {Z}_+$ a.s.
$X \sim \operatorname {Ber}(p)$
$X \sim \operatorname {Pois}(\lambda )$
$X \sim \operatorname {Geom}(p)$ Compute the generating function and determine the radius of convergence.

Solution

(1)

$G_{\xi }(z) = z^{k_0}$. Radius of convergence: $+\infty$.

(2)

$G_{\xi }(z) = (1-p) + pz$. Radius of convergence: $+\infty$.

(3)

$G_{\xi }(z)= \mathbb {E}\left[z^{\xi }\right]=\sum_{k=0}^{\infty } z^{k} \frac{\lambda^{k}}{k !} e^{-\lambda }=e^{-\lambda } \sum_{k=0}^{\infty } \frac{(z \lambda )^{k}}{k !}=e^{\lambda (z-1)}$. Radius of convergence: $+\infty$.

(4)

$G_{\xi }(z)= \mathbb {E}\left[z^{\xi }\right]=\sum_{k=0}^{\infty } z^{k} (1-p)^kp = p\cdot \sum_{k=0}^{\infty } \left(z(1-p)\right)^k = p \cdot \frac{1}{1 - z(1-p)}$. Radius of convergence: $\left|z(1-p)\right| < 1$ $\iff$ $\left|z\right| < \frac{1}{1-p}$.

Theorem 1 (Basic properties of generating functions) Let us list the basic properties of generating functions.

$G_{\xi }(z)$ is infinitely continuously differentiable on the region $\{ |z|<1\}$;
The generating function uniquely determines the probability mass function:

\[ \mathbb {P}\left(\xi = k\right) = \frac{G_\xi ^{(k)}(0)}{k!} \]
As a consequence of the previous item, the generating function uniquely determines the distribution on $\mathbb {Z}_+ \cup \left\{ +\infty \right\}$. That is, if two random variables $\xi , \eta$, taking values in $\mathbb {Z}_+ \cup \left\{ +\infty \right\}$, have equal generating functions ($G_{\xi }(z) = G_\eta (z)$ for $z \in [0,1)$), then $\operatorname {Law}\left(\xi \right) = \operatorname {Law}\left(\eta \right)$.
If $\xi$ and $\eta$ are independent, then $G_{\xi +\eta }(z)=G_{\xi }(z) \cdot G_{\eta }(z)$;
Let $\mathbb {P}\left(\xi < +\infty \right) = 1$. Then we have

\[ 1 = G_{\xi }(1-) = \lim _{x \to 1-0}G_{\xi }(x) \]

1st moment:

\[ \mathbb {E}\left[\xi \right] = G_{\xi }^{\prime }(1-) = \lim _{x \to 1-0}G^{\prime }_{\xi }(x) \]

In general, the $k$-th factorial moment $\mathbb {E}\left[\xi (\xi -1) \cdot \ldots \cdot (\xi - k + 1)\right]$:

\[ \mathbb {E}\left[\frac{\xi !}{(\xi - k)!}\right] = G_{\xi }^{(k)}(1-) = \lim _{x \to 1-0}G^{(k)}_{\xi }(x) \]

Hence, the variance:

\[ \operatorname {Var}\left[\xi \right] = G_{\xi }^{\prime \prime }(1-) + G_{\xi }^{\prime }(1-) - \left[ G_{\xi }^{\prime }(1-) \right]^2 \]

In general, the $k$-th moment:

\[ \mathbb {E}\left[\xi ^k\right] = \lim _{x \to 1-0} \left( \left(x \frac{d}{dx}\right)^k G_{\xi }(x) \right) \]

In this section we considered random variables $X$ taking only finite (nonnegative integer) values, and consequently their generating functions $G_X$ satisfy $G_X(1)=1$. However, we have already encountered random variables taking values in $\left\{ 0,1,2,\ldots \right\} \cup \left\{ +\infty \right\}$ (see, for example, the hitting time of $1$ for a random walk starting at zero). For such random variables, $G_X(s)= \mathbb {E}\left[s^X\right]$ converges for $|s|<1$, and, moreover,

\[ \lim _{s \uparrow 1} G_X(s)=\sum _k \mathbb {P}(X=k)=1-\mathbb {P}(X=+\infty ) \]

We can no longer find the moments of $X$ via $G_X$; of course, all of them equal $+\infty$. If $\mathbb {P}(X=+\infty )>0$, then $X$ is called a defective random variable, and its distribution is called defective. (Careful: not to be confused with a degenerate distribution — this is the name given to the distribution of a constant.)

2 Definition of the branching process

The model of branching processes was first proposed by F. Galton and H. Watson in 1873 in connection with the analysis of the extinction of aristocratic surnames in Great Britain.

Physical model: at discrete moments of time, particles split into a random number of identical particles. The number of offspring of each particle has the same distribution.

Mathematical model: let $\xi$ be a random variable with values in $\mathbb {Z}_{+} = \left\{ 0,1,2,\ldots \right\}$, let

\[ \left\{ \xi _{k}^{(n)} , \; k, n \in \mathbb {N}\right\} = \left\{ \begin{array}{cccc} \xi _{1}^{(1)} & \xi _{2}^{(1)} & \xi _{3}^{(1)} & \cdots \\ \xi _{1}^{(2)} & \xi _{2}^{(2)} & \xi _{3}^{(2)} & \cdots \\ \vdots & \vdots & \vdots & \ddots \\ \end{array}\right\} \]

be a collection of independent random variables with the same distribution as $\xi$. Define a discrete-time process $(X_n, \; n \in \mathbb {Z}_+)$ inductively:

\[ X_{0} := 1, \qquad X_{n} := \sum _{k=1}^{X_{n-1}} \xi _{k}^{(n)}, n \geqslant 1 \]

$\xi_{k}^{(n)}$ is the number of offspring of the $k$-th member of generation $(n-1)$ (respectively, in generation $n$).
$X_{n}$ is the total number of members in generation $n$. It is computed as the sum of the offspring of each member of generation $n-1$.

The process $\left(X_{n}, n \in \mathbb {Z}_{+}\right)$ is called the Galton-Watson branching process with offspring distribution $\xi$.

It is clear that in real life, a member of any biological species can rarely produce offspring on its own, as in our model. However, the advantage is that our model is simpler than models that account for pairs. It is also suitable for the case where we want to study one particular lineage and its descendants. In this case, each member produces offspring within the lineage “on their own,” since the spouse always comes from outside, not from the lineage.

An example of a branching process (for some fixed elementary outcome ω₀). Hover over a node or arrow to see details.

3 Distribution of the branching process

Let $X=\left(X_{n}, n \in \mathbb {Z}_+\right)$ be the Galton-Watson branching process with offspring distribution $\xi$.

Lemma 1 The generating functions of the elements of the process $X$ satisfy the following recurrence relations: \[ G_{X_{n+1}} = G_{X_{n}} \circ G_{\xi } \] i.e., $G_{X_{n+1}}(z)=G_{X_{n}}\left(G_{\xi }(z)\right)$.

As a consequence, we get $G_{X_{n}} = G_{\xi } \underbrace{\circ \dots \circ }_{n \text{ times}} G_{\xi }$.

Example 2

Prove lemma Lemma 1.

Solution

3 similar solutions.

We have $X_{n+1} = \sum_{k=1}^{X_{n}} \xi_k^{(n+1)}$. The main difficulty in working with this object is that not only the summands $\xi_k^{(n+1)}$ themselves are random in this sum, but also their number $X_n$. This difficulty can be overcome by taking conditional probabilities and expectations given $X_n$, i.e., effectively fixing $X_n$. In that case the sum will have a fixed number of terms:

\[ \begin{align} G_{X_{n+1}}(z) = \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}}\right] & = \mathbb {E}\left[\mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}}|X_n\right]\right] \stackrel{*}{=} \\ \notag & \stackrel{*}{=} \mathbb {E}\left[G_\xi ^{X_n}(z)\right] = G_{X_n} ( G_\xi (z) ) \end{align} \tag{1}\]

Equality $*$ holds because if $X_n$ is known (and equal to $k_0$, say), then the sum $\xi^{(n+1)}_1 + \dots + \xi^{(n+1)}_{X_n}$ equals $\xi^{(n+1)}_1 + \dots + \xi^{(n+1)}_{k_0}$ and simply becomes a sum of $k_0$ independent identically distributed random variables with distribution $\operatorname {Law}\left(\xi \right)$.
Let us spell out Equation 1 in a bit more detail. $X_n$ is a discrete random variable with $\mathbb {Z}_+$ as the support of its distribution, so the conditional expectation with respect to it can be written explicitly. For fixed $z \in \mathbb {C}, \; \left|z\right| \leq 1$ we have

\[ \begin{align} \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}}|X_n\right] & \stackrel{\text{a.s.}}{=} \sum _{k \in \mathbb {Z}_+} \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}} \mid X_n = k\right] \\ & \quad \cdot \; \mathbb {1}_{X_n = k} \enclose {circle}{=} \\ \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}} \; \mid \; X_n = k\right] & = \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{k}}\mid X_n = k\right] = \\ & = \bigg\rvert \text{$X_n$ and $\xi _i^{(n+1)}$ independent} \bigg\rvert = \\ & = \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{k}} \right] = \\ & = \mathbb {E}\left[z^{\xi ^{(n+1)}_1}\right] \cdot \mathbb {E}\left[z^{\xi ^{(n+1)}_2}\right] \cdot \cdots \cdot \mathbb {E}\left[z^{\xi ^{(n+1)}_{k}}\right] = \\ & = G_\xi (z) \cdot G_\xi (z) \cdot \cdots \cdot G_\xi (z) = G_\xi ^{k}(z) \\ & \enclose {circle}{=} \sum _{k\in \mathbb {Z}_+} G_\xi ^{k}(z) \cdot \; \mathbb {1}_{X_n = k} \\ G_{X_{n+1}}(z) = \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}}\right] & = \mathbb {E}\left[\mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}}|X_n\right]\right] = \\ & = \mathbb {E}\left[ \sum _{k\in \mathbb {Z}_+} G_\xi ^{k}(z) \cdot \; \mathbb {1}_{X_n = k}\right] = \\ & = \sum _{k\in \mathbb {Z}_+} G_\xi ^{k}(z) \cdot \mathbb {P}\left(X_n = k\right) = \mathbb {E}\left[\left(G_\xi (z)\right)^{X_n}\right] \\ & = G_{X_n}(G_\xi (z)) \end{align} \]
Alternatively, all of this can be written out as follows:

\[ \begin{align} G_{X_{n+1}}(z) & = \mathbb {E}\left[z^{\sum _{k=1}^{X_{n}} \xi _k^{(n+1)}}\right] = \\ & = \mathbb {E}\left[\; \mathbb {1}_{X_n = 0}z^{\sum _{k=1}^{0} \xi _k^{(n+1)}} + \; \mathbb {1}_{X_n = 1}z^{\sum _{k=1}^{1} \xi _k^{(n+1)}} + \; \mathbb {1}_{X_n = 2}z^{\sum _{k=1}^{2} \xi _k^{(n+1)}} + \ldots \right] = \\ & = \mathbb {E}\left[\sum _{m=0}^\infty \; \mathbb {1}_{X_n = m}z^{\sum _{k=1}^{m} \xi _k^{(n+1)}}\right] \stackrel{\ast }{=} \\ & \stackrel{\ast }{=} \sum _{m=0}^\infty \mathbb {E}\left[\; \mathbb {1}_{X_n = m}z^{\sum _{k=1}^{m} \xi _k^{(n+1)}}\right] \stackrel{\ast \ast }{=} \\ & \stackrel{**}{=} \sum _{m=0}^\infty \mathbb {P}\left(X_n = m\right) \mathbb {E}\left[z^{\sum _{k=1}^{m} \xi _k^{(n+1)}}\right] \stackrel{**}{=} \\ & \stackrel{**}{=} \sum _{m=0}^\infty \mathbb {P}\left(X_n = m\right) \prod _{k=1}^m \mathbb {E}\left[z^{\xi _k^{(n+1)}}\right] \stackrel{***}{=} \\ & \stackrel{***}{=} \sum _{m=0}^\infty \mathbb {P}\left(X_n = m\right) \prod _{k=1}^m \underbrace{\mathbb {E}\left[z^{\xi }\right]}_{=G_{\xi }(z)} = \\ & = \sum _{m=0}^\infty \mathbb {P}\left(X_n = m\right) G_{\xi }^m(z) = \\ & = \mathbb {E}\left[G_{\xi }^{X_n}(z)\right] = G_{X_n} ( G_\xi (z) ) \end{align} \]
- holds by the Beppo Levi monotone convergence theorem for the Lebesgue integral;
- holds because of the independence of $X_n, \xi^{(n+1)}_1, \xi^{(n+1)}_2, \ldots$;
- holds because $\xi^{(n+1)}_1, \xi^{(n+1)}_2, \ldots$ are identically distributed according to the law of $\xi$.

Example 3

Suppose that each member of the lineage produces children as follows:

$0$ with probability $1/4$;
$1$ with probability $1/4$;
$2$ with probability $1/3$;
$3$ with probability $1/6$.

What is the probability that the second generation has exactly $6$ members?

Solution

The generating function of $\xi$: \[ G_{\xi }(z) = \sum _{n=0}^{\infty } \mathbb {P}\left(\xi = n\right) \cdot z^n = \frac{1}{4} + \frac{1}{4}z + \frac{1}{3}z^2 + \frac{1}{6}z^3 \] The generating function of the number of people in the second generation: $G_{X_{2}} = G_{\xi } \circ G_{\xi }$. We are only interested in the coefficient of $z^6$. Let us compute: \[ \begin{align} G_{X_{2}}(z) & = G_{\xi } (G_{\xi } (z)) = \\ & =\frac{1}{4} + \frac{1}{4}\cdot \left(\frac{1}{4} + \frac{1}{4}z + \frac{1}{3}z^2 + \frac{1}{6}z^3\right) \\ & \quad + \frac{1}{3}\cdot \left(\frac{1}{4} + \frac{1}{4}z + \frac{1}{3}z^2 + \frac{1}{6}z^3\right)^2 + \frac{1}{6}\cdot \left(\frac{1}{4} + \frac{1}{4}z + \frac{1}{3}z^2 + \frac{1}{6}z^3\right)^3 = \\ & = \ldots + \\ & \quad \left(\frac{1}{3} \cdot \frac{1}{6^2} + \frac{1}{6} \cdot \left(3 \cdot \frac{1}{4} \cdot \frac{1}{6^2} + 3! \cdot \frac{1}{4} \cdot \frac{1}{3} \cdot \frac{1}{6} + \frac{1}{3^3}\right)\right)z^6 + \ldots = \\ & = \ldots + \frac{85}{2592}z^6 + \ldots \end{align} \]

Answer

$\frac{85}{2592} \approx 3.28 \%$.

Problem 1

Find the generating function for the number of particles in the $n$-th generation of the branching process, if

$\xi \sim \operatorname {Ber}(p)$;
$G_{\xi }(z) = 1 - p(1-z)^\alpha , \; \alpha \in (0,1)$. Find the probability that the $2$nd generation has $1$ member. Find the probability that the 3rd generation has $5$ members (in part a) take $p=0.3$, in b) take $p=0.3$, $\alpha = 0.8$).

Hint

To expand the function into a power series, use Wolfram Alpha.

Let us try to express the expectation and variance of $X_{n}$.

Lemma 2 Let $\mathbb {E}\left[\xi \right] = \mu , \; \operatorname {Var}\left[\xi \right] = \sigma^{2}< \infty$. For the branching process $X_n$ we have \[ \mathbb {E}\left[X_{n}\right] = \mu ^n, \qquad \operatorname {Var}\left[X_{n}\right] = \begin{cases} \sigma ^2n, & \mu = 1 \\ \sigma ^2 \mu ^{n-1} \frac{\mu ^n - 1}{\mu - 1}, & \mu \neq 1 \end{cases} \]

Problem 2

Prove the formula for the expectation of $X_n$;
Prove the formula for the variance of $X_n$;

Hint

Use the properties of the generating function.

Ten simulated trajectories of a branching process with offspring law $\operatorname{Pois}(\mu)$. The “extinction or exponential growth” dichotomy is clearly visible: some populations die out even when $\mu > 1$ (the supercritical case), while the survivors grow along the dashed curve $\mathsf E X_n = \mu^n$. Move the slider $\mu$ across the critical value $1$: for $\mu \leqslant 1$ all trajectories eventually die out ($q=1$), while for $\mu>1$ a chance of unbounded growth appears, and the fraction of extinct trajectories among the simulated ones approaches the theoretical extinction probability $q$ (the smallest root of $z=e^{\mu(z-1)}$). The “New trajectories” button recomputes everything with the same $\mu$ but with fresh random numbers.

μ = 1.30

4 The probability of extinction

Denote by $q$ the probability of extinction, i.e., $q= \mathbb {P}\left(\exists n \in \mathbb {N}: \; X_n = 0\right)$. Then the following statement holds.

Lemma 3 The extinction probability $q$ of a branching process with offspring distribution $\xi$ is the smallest nonnegative root of the equation \[ z=G_{\xi }(z), \tag{2}\] i.e., it is a fixed point of the function $G_{\xi }$.

Example 4

Prove lemma Lemma 3.

Solution

Note that each person in a generation produces (among their descendants) a copy of the original Galton-Watson process, which is independent of the other people in the generation and their descendants. That is, for the process to die out, either it must die out immediately at step 1 (i.e., $\xi_1^{(1)} = 0$), or all $\xi_1^{(1)}$ independent copies of the G-W process must eventually die out. The probability of this (given $\xi_1^{(1)} = k$) equals $q^k$ by independence. Altogether,

\[ \begin{align} q = \mathbb {P}\left(\xi _1^{(1)} = 0\right) + \sum _{k=1}^\infty q^k \mathbb {P}\left(\xi _1^{(1)} = k\right) = G_\xi (q) \end{align} \]

Another proof: the events $\left\{ X_n = 0\right\}$ increase in $n$ (an extinct process does not come back to life), and their union is the extinction event. By continuity of the probability measure, $\mathbb {P}\left(X_n = 0\right) = G_{X_n}(0)$ is nondecreasing in $n$ and converges to $q$. Using continuity of $G$, we have

\[ \begin{align} G_\xi (q) & = G_\xi (\lim _{n \to \infty } G_{X_n}(0)) = \lim _{n \to \infty } G_\xi (G_{X_n}(0)) = \lim _{n \to \infty } G_{X_{n+1}}(0) = \\ & = q \end{align} \]

From this we can also deduce that $q$ is the smallest nonnegative root of the equation $z = G_\xi (z)$. Let $z \geq 0$ be an arbitrary root. Then $z$ is a fixed point of all the compositions as well: $G_{X_n}(z) = z$. Generating functions are monotone on $[0, +\infty )$, so

\[ \begin{align} G_{X_n}(0) \leq G_{X_n} (z) = z \end{align} \]

Taking the limit in $n$ on the left-hand side, we get $q \leq z$.

Equation (Equation 2) is the first remarkable formula in the theory of branching processes. Note that $z=1$ is always a solution of (Equation 2). However, when other roots are present, we need to be able to pick out the extinction probability among them. A complete classification of the situations is given by the theorem on the extinction probability.

Theorem 2 Let the random variable $\xi$ not be identically $1$, i.e., $\mathbb {P}\left(\xi = 1\right) < 1$. Denote $\mu = \mathbb {E}\left[\xi \right]$ (possibly $\mu = +\infty )$. Then

If $\mu \leqslant 1$, equation (Equation 2) has only one solution $z=1$ on $[0,1]$. In this case $q=1$.
If $\mu >1$, equation (Equation 2) has a unique solution $z_{0} \in [0,1)$. In this case $q=z_{0}$.

Thus, the extinction probability is the smallest root of the equation $z=G_{\xi }(z)$ in the interval $[0,1]$.

Note that the theorem has a rather vivid interpretation: if the mean number of offspring in the process is no greater than 1, the process is doomed to extinction; otherwise there is a nonzero probability of the population existing forever.

Iterations of the generating function: the staircase $0 \to G_\xi(0) \to G_\xi(G_\xi(0)) \to \ldots$ (red) depicts the growth of the probabilities $\mathsf P(X_n = 0) = G_{X_n}(0)$ toward the extinction probability $q$ — the smallest fixed point of $G_\xi$ on $[0,1]$ (the point where it meets the diagonal). The offspring law is $\operatorname{Geom}(p)$, $\mathsf P(\xi = k) = p(1-p)^k$, with mean $\mu = \frac{1-p}{p}$. Move the slider $p$: as $\mu$ crosses the critical value $1$ (i.e., as $p$ crosses $\frac12$), the intersection point of the curve $G_\xi$ with the diagonal “breaks away” from $1$, and the extinction probability $q$ becomes less than one. The “Step” and “Play” buttons let you build the staircase of iterations one step at a time, while “Reset” returns it to the start.

p = 0.30

Example 5

Find the extinction probability of a branching process with a geometric $\operatorname {Geom}(p)$, $p \in (0,1)$ offspring distribution (i.e., $\mathbb {P}\left(\xi = k\right) = p(1-p)^{k}, \; k \in \mathbb {Z}_{+}$).

Solution

Let us first find the generating function of the offspring distribution.

\[ G_{\xi }(z)= \mathbb {E}\left[z^{\xi }\right] = \sum _{k=0}^{\infty } z^{k} p(1-p)^{k} = \frac{p}{1-z(1-p)} \]

Now we solve the equation $z=G_{\xi }(z)$. The quadratic equation has two roots: $z_{1}=1, z_{2}=p /(1-p)$. According to the corollary of the theorem, we must choose the smallest root in the interval $[0,1]$. Thus, $q = 1$, if $p \geqslant \frac{1}{2}$; $q= \frac{p}{1-p}$, if $p < \frac{1}{2}$.

Answer

$q = 1$, if $p \geqslant \frac{1}{2}$; $q= \frac{p}{1-p}$, if $p < \frac{1}{2}$.

Problem 3

Find the extinction probabilities for branching processes with the following generating function of the number of offspring of a single particle:

$1-p(1-z)^{\alpha }, \alpha \in (0,1)$;
$\left(1+z+z^{2}+z^{3}\right) / 4$.

Problem 4

Find the distribution of the extinction time $\tau_0$ for branching processes with the following generating function of the number of offspring of a single particle:

$p z+1-p$;
$1-p(1-z)^{\alpha }, \alpha \in (0,1)$

Problem 5

A branching process has the following distribution $\xi$ of the number of offspring of a single particle: \[ \mathbb {P}\left(\xi = 0\right) = \frac{1}{4}, \quad \mathbb {P}\left(\xi = 2\right) = \frac{1}{2}, \quad \mathbb {P}\left(\xi = 6\right) = \frac{1}{4} \] Is it true that the extinction probability lies in the interval $(1 / 4,1 / 3)$?

Problem 6

A person has been infected with a rare virus. During a given day, with probability $p<1$ nothing important will happen to them (such as contact with other people or recovery). Given that an important event occurs during the day, with probability $r$ the sick person will infect one other person, with probability $s$ they will infect two, and with probability $t=1-r-s$ they will stop being sick and infect no one. The fates of infected people are independent of one another, as are the events of different days. An infected person becomes potentially dangerous on the day following infection. Let $q$ be the probability that the epidemic ends. Prove that $q$ does not depend on $p$. Find $q$ if

$2 r+3 s \leq 1$
$2 r=s=t$.

5 The total number of particles

Let us now discuss the question of the total number of particles in the branching process. Denote $Y_{n}=1+X_{1}+\ldots +$ $X_{n}$, the total number of particles in the process up to and including time $n$. Then the following recurrence relation holds between the generating functions of $Y_{n}$ and $Y_{n-1}$, analogous to the relations in Lemma 1 for $X_{n}$ itself:

\[ G_{Y_{n+1}}(z)=z G_{\xi }\left(G_{Y_{n}}(z)\right) \tag{3}\]

Example 6

Prove ().

Hint

See Example @G-W_proc:prob_of_extict_lem_proof.

Solution

Note that each member of the first generation produces, among its descendants, a Galton-Watson process independent of the other members and their descendants. Moreover, the number of members of the first generation is distributed according to the law of $\xi$ and is independent of the subsequent number of offspring. That is, we have $Y_{n+1} \overset {d}{=} 1 + \sum_{i=1}^{\xi } Y_n^i =: \tilde{Y}_{n+1}$, where $Y_n^i$ are independent copies of $Y_n$ (independent of each other and of $\xi$). Moreover (for more detail, see the solution of G-W_proc:prob_of_extict_lem_proof) \[ \begin{align} G_{\tilde{Y}_{n+1}}(z) & = \mathbb {E}\left[z^{\tilde{Y}_{n+1}}\right] = \mathbb {E}\left[z \cdot z^{\sum _{i=1}^{\xi } Y_n^i}\right] = \\ & = z \cdot \mathbb {E}\left[z^{\sum _{i=1}^{\xi } Y_n^i}\right] \enclose {circle}{=} \\ \mathbb {E}\left[z^{\sum _{i=1}^{\xi } Y_n^i}\right] & = \mathbb {E}\left[\mathbb {E}\left[z^{\sum _{i=1}^{\xi } Y_n^i} \mid \xi \right]\right] = \mathbb {E}\left[G^\xi _{Y_n}(z)\right] = G_{\xi }(G_{Y_n}(z)) \\ & \enclose {circle}{=} \; z \cdot G_{\xi }(G_{Y_n}(z)) \end{align} \] Since we are dealing with expectations, we may make substitutions up to equality in distribution of the quantity under the expectation. Altogether \[ \begin{align} G_{Y_{n+1}}(z) = z G_\xi (G_{Y_n}(z)) \end{align} \]

Let $Y$ be the total number of particles in the branching process over all time: $Y = \lim_{n \to \infty } Y_{n}$. $Y_{n}$ converges to $Y$ pointwise (i.e., for every $\omega$), and hence also a.s. and in distribution. One can show that this implies pointwise convergence of the generating functions:

\[ G_{Y}(z) = \lim _{n \to \infty } G_{Y_n}(z), \qquad \text{for any } \left|z\right| < 1 \]

$G_{Y}$ can be found as the limit of $G_{Y_n}$, or from the second remarkable equation in the theory of branching processes.

Lemma 4 The function $G_{Y}(z)$, $\left|z\right| < 1$ satisfies \[ G_Y(z) = z G_{\xi }(G_Y(z)). \]

Try to prove this formula yourself.

Problem 7

Suppose that $\xi \sim \operatorname {Geom}(1 - p)$, i.e., $G_{\xi }(z) = \frac{1 - p}{1 - pz}$.

Find the extinction probability of the process;
Find the generating function $G_Y(z)$ of the total number of particles $Y$. Find $\lim_{z \to 1}G_Y(z)$, and compare with the result of the previous part (they should agree).
Find the generating function $G_{X_n}$ for $X_n$.

Hint

For part c): a map of the form $f(z) = \frac{az + b}{cz + d}$ ($a,b,c,d \in \mathbb {C}$, $ad \neq bc$) is called a linear fractional (Möbius) transformation. More precisely, a Möbius transformation is defined as follows: \[ f(z) = \begin{cases} \frac{az + b}{cz + d}, & z \in \mathbb {C} \setminus \left\{ -\frac{d}{c}\right\} \\ \infty , & z = -\frac{d}{c} \\ \frac{b}{d}, & z = \infty \end{cases}, \qquad z \in \overline{\mathbb {C}} \] Möbius transformations, viewed as transformations of the Riemann sphere $\overline{\mathbb {C}}$, form a group under composition. Moreover, this group is homomorphic to the group $\operatorname {GL}_2(\mathbb {C})$ of invertible $2 \times 2$ matrices over $\mathbb {C}$: the map \[ \frac{az + b}{cz + d} \mathrel {\leadsto } \begin{pmatrix} a & b \\ c & d \end{pmatrix} \] turns composition of Möbius transformations into matrix multiplication.

The probability of dying out by generation $n$ for a geometric offspring law with $\theta = \mathsf E \xi$: the exact formula is $\mathsf P(X_n = 0) = \frac{\theta^n - 1}{\theta^{n+1} - 1}$ for $\theta \neq 1$ and $\frac{n}{n+1}$ for $\theta = 1$ (derived from the fractional-linear form $G_\xi(z) = \frac{1}{1+\theta-\theta z}$). Thin lines show the three canonical cases $\theta = 0{,}8$, $\theta = 1$, $\theta = 1{,}25$; the bold highlighted curve follows the slider $\theta$ (or the preset buttons). The bottom panel shows the same distance $q - \mathsf P(X_n=0)$ on a logarithmic scale: it clearly shows that the subcritical and supercritical convergences are geometric (straight lines), while the critical one ($\theta=1$) is polynomial (a slowly bending curve).

θ = 1.25

Problem 8

On the final level of the computer game “Heroes of Loofah and Soap III: The Breath of Moidodyr,” the player must battle the evil Soap Bubble. Each time the player attacks the Bubble, one of two equally likely events occurs: the Bubble may pop, or it may split into two new Bubbles. To win, the player must destroy all Soap Bubbles.

What is the chance of clearing this level?
Let $\tilde{Y}$ be the total number of Bubbles that popped. Find the generating function and distribution of $\tilde{Y}$.
Compute $\mathbb {E}\left[\tilde{Y}\right]$.

Problem 9

Let $\tilde{Y}$ be the total number of particles with no offspring in a Galton-Watson branching process with geometric offspring distribution $\operatorname {Geom}(2/3)$ (that is, $\mathbb {P}\left(\xi =k\right) = \frac{2}{3} \cdot \left(\frac{1}{3}\right)^k$ for $k \in \left\{ 0,1,2, \ldots \right\} )$. Compute $G_{\tilde{Y}}$ and $\mathbb {E}\left[\tilde{Y}\right]$.