Branching process

In probability theory, a branching process is a Markov process that models a population in which each individual in generation n produces some random number of individuals in generation n + 1, according to a fixed probability distribution that does not vary from individual to individual. Branching processes are used to model reproduction; for example, the individuals might correspond to bacteria, each of which generates 0, 1, or 2 offspring with some probability in a single time unit. Branching processes can also be used to model other systems with similar dynamics, e.g., the spread of surnames in genealogy or the propagation of neutrons in a nuclear reactor.

A central question in the theory of branching processes is the probability of ultimate extinction, where no individuals exist after some finite number of generations. It is not hard to show that, starting with one individual in generation zero, the expected size of generation n equals μ ⁿ where μ is the expected number of children of each individual. If μ is less than 1, then the expected number of individuals goes rapidly to zero, which implies ultimate extinction with probability 1 by Markov's inequality. Alternatively, if μ is greater than 1, then the probability of ultimate extinction is less than 1 (but not necessarily zero; consider a process where each individual either dies without issue or has 100 children with equal probability). If μ is equal to 1, then ultimate extinction occurs with probability 1 unless each individual always has exactly one child.

In theoretical ecology, the parameter μ of a branching process is called the basic reproductive rate.

Mathematical formulation

The most common formulation of a branching process is that of the Galton–Watson process. Let Z_n denote the state in period n (often interpreted as the size of generation n), and let X_n,i be a random variable denoting the number of direct successors of member i in period n, where X_n,i are iid over all n ∈ {0,1,2,...} and i ∈ {1,...,Z_n}. Then the recurrence equation is

$Z_{n+1} = \sum_{i=1}^{Z_n} X_{n,i}$

with Z₀ = 1. Alternatively, one can formulate a branching process as a random walk. Let S_i denote the state in period i, and let X_i be a random variable that is iid over all i. Then the recurrence equation is

$S_{i+1} = S_i+X_{i+1}-1 = \sum_{j=1}^{i+1} X_j-i$

with S₀ = 1. To gain some intuition for this formulation, one can imagine a walk where the goal is to visit every node, but every time a previously unvisited node is visited, additional nodes are revealed that must also be visited. Let S_i represent the number of revealed but unvisited nodes in period i, and let X_i represent the number of new nodes that are revealed when node i is visited. Then in each period, the number of revealed but unvisited nodes equals the number of such nodes in the previous period, plus the new nodes that are revealed when visiting a node, minus the node that is visited. The process ends once all revealed nodes have been visited.

See also

• Galton–Watson process
• Random tree
• Branching random walk
• Martingale

References

• C. M. Grinstead and J. L. Snell, Introduction to Probability, 2nd ed. Section 10.3 discusses branching processes in detail together with the application of generating functions to study them.
• G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, 2nd ed., Clarendon Press, Oxford, 1992. Section 5.4 discusses the model of branching processes described above. Section 5.5 discusses a more general model of branching processes known as age-dependent branching processes, in which individuals live for more than one generation.