Branching Processes — Mathematics Knowledge System

Overview

A branching process models the evolution of a population where each individual independently produces a random number of offspring. The Galton-Watson process is the simplest: starting with Z_0 = 1 individual, each produces offspring independently according to a distribution {p_k}. The key questions are: does the population go extinct, and if so, with what probability? Extinction probability is the smallest non-negative fixed point of the probability generating function (PGF) of the offspring distribution. The process provides a model for biological populations, nuclear chain reactions, and epidemic spread.

Intuition

Think of a nuclear chain reaction: each uranium atom may split into 0, 1, 2, or more new atoms, each of which can split again. If the average number of offspring mu = E[Z] < 1 (subcritical), the chain reaction dies out almost surely. If mu > 1 (supercritical), there is a positive probability of perpetual growth (and the bomb goes off). The critical case mu = 1 (critical) is fascinating: extinction still occurs with probability 1, but the expected population is constant -- it's a martingale that converges to 0 a.s. The PGF is the key tool: extinction probability q is the smallest solution to G(q) = q.

Formal Definition

Definition

A Galton-Watson branching process {Z_n} is defined by Z_0 = 1 and the recurrence with offspring distribution {p_k}.

Z_0 = 1, \quad Z_{n+1} = \sum_{k=1}^{Z_n} X_k^{(n)}, \quad X_k^{(n)} \overset{\text{i.i.d.}}{\sim} \{p_j\}

Galton-Watson recursion

G(s) = \sum_{k=0}^{\infty} p_k s^k = \mathbb{E}[s^{Z_1}], \quad s \in [0,1]

Probability generating function (PGF)

\mathbb{E}[Z_n] = \mu^n, \quad \mu = G'(1) = \mathbb{E}[Z_1]

Mean population at generation n

q = \min\{s \in [0,1]: G(s) = s\}

Extinction probability: smallest fixed point of G

Notation

Notation	Meaning
$Z_n$	Population size in generation n
$G(s)$	Probability generating function of offspring distribution
$\mu = G'(1)$	Mean number of offspring per individual
$q$	Extinction probability = smallest fixed point of G in [0,1]

Theorems

Theorem 1: Extinction Probability Theorem

\text{Let } q = P(Z_n \to 0) \text{ be the extinction probability. Then } q \text{ is the smallest non-negative root of } G(s) = s. \text{ Moreover: } q = 1 \text{ if } \mu \le 1 \text{ (subcritical or critical), and } q < 1 \text{ if } \mu > 1 \text{ (supercritical), provided } p_0 > 0.

Theorem 2: Criticality Classification

\text{If } \mu < 1{:} \text{ subcritical, } Z_n \to 0 \text{ a.s. exponentially fast.}\quad \text{If } \mu = 1 \text{ with } p_1 < 1{:} \text{ critical, } Z_n \to 0 \text{ a.s. but } \mathbb{E}[Z_n] = 1 \forall n.\quad \text{If } \mu > 1{:} \text{ supercritical, } P(Z_n \to \infty) = 1-q > 0.

Theorem 3: Kesten-Stigum Theorem

\text{For a supercritical process with } \mu > 1 \text{ and } \mathbb{E}[Z_1 \log Z_1] < \infty{:}\quad W_n = Z_n / \mu^n \to W \text{ a.s. and in } L^1, \text{ with } P(W > 0) = 1 - q.

Worked Examples

1
Compute the PGF: G(s) = (1/4) + (1/2)s + (1/4)s^2.
$G(s) = \tfrac{1}{4} + \tfrac{1}{2}s + \tfrac{1}{4}s^2$
2
Mean offspring: mu = G'(1) = 1/2 + (1/2)(1) = 1. Critical case, so q = 1.
$\mu = G'(1) = \tfrac{1}{2} + \tfrac{1}{2} = 1 \implies q = 1$
3
Verify: G(s) = s gives (1/4)s^2 - (1/2)s + (1/4) = 0, so (s-1)^2 = 0, confirming q = 1 as a double root.
$G(s) = s \iff \tfrac{1}{4}(s-1)^2 = 0 \implies q = 1$

✓ Answer

The process is critical (mu = 1) and the extinction probability is q = 1.

Practice Problems

Mediumfree response

A virus spreads so that each infected person infects exactly 0, 1, or 3 others with probabilities 0.5, 0.3, 0.2. Is the epidemic subcritical, critical, or supercritical? Find the mean extinction condition.

Mediumproof writing

Prove that W_n = Z_n / mu^n is a martingale for the supercritical Galton-Watson process (mu > 1).

Common Mistakes

Common Mistake

A critical process (mu = 1) survives forever with positive probability

A critical branching process with p_0 > 0 and p_1 < 1 goes extinct with probability 1. The mean E[Z_n] = 1 but the random variable Z_n concentrates near 0.

Common Mistake

The extinction probability equals 1 - mu for supercritical processes

The extinction probability q is the smallest root of G(s) = s, not simply 1 - mu. It must be computed from the PGF.

Quiz

Historical Background

Francis Galton and Henry Watson introduced the Galton-Watson process in 1874 to study the extinction of family surnames in Victorian England. They derived the extinction probability equation but made an error, which was corrected by Steffensen in 1930. The process was later connected to the theory of random graphs, percolation, and epidemic models. Harry Kesten and Stigum (1966) proved the fundamental limit theorem for supercritical branching processes.

1874
Galton and Watson introduce the branching process to study extinction of surnames
Francis Galton, Henry Watson
1930
Steffensen corrects Galton and Watson's error on the extinction probability
J.F. Steffensen
1966
Kesten and Stigum prove the fundamental limit theorem for supercritical branching processes
Harry Kesten, Bert Stigum

Summary

The Galton-Watson process models independent reproduction: Z_{n+1} = sum of Z_n i.i.d. offspring counts.
Extinction probability q = smallest fixed point of the PGF G(s) = s: q = 1 if mu <= 1; q < 1 if mu > 1.
Subcritical (mu < 1): certain extinction; critical (mu = 1): certain extinction despite constant mean; supercritical (mu > 1): positive survival probability.
The normalized process W_n = Z_n/mu^n is a martingale converging to a limit W > 0 on the survival event.

References

BookDurrett, R. -- Probability: Theory and Examples, 4th ed., Chapter 5
BookAthreya, K.B. and Ney, P.E. -- Branching Processes
WebsiteWikipedia -- Galton-Watson process