Branching process

In probability theory, a branching process is a type of mathematical object known as a stochastic process, which consists of collections of random variables indexed by some set, usually natural or non-negative real numbers. The original purpose of branching processes was to serve as a mathematical model of a population in which each individual in generation $n$ produces some random number of individuals in generation $n+1$ , according, in the simplest case, to a fixed probability distribution that does not vary from individual to individual.^[1] ^[2] 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 (Galton-Watson processes) or the propagation of neutrons in a nuclear reactor^[3].

Branching process theory provides a tractable framework for calculating extinction probabilities for population processes in cases where individuals act independently. Using Wald's equation, it can be shown 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 μ < 1, then the expected number of individuals goes rapidly to zero, which implies ultimate extinction with probability 1 by Markov's inequality. Alternatively, if μ > 1, then the probability of ultimate extinction is less than 1 (but not necessarily zero; consider a process where each individual either has 0 or 100 children with equal probability. In that case, μ = 50, but probability of ultimate extinction is greater than 0.5, since that's the probability that the first individual has 0 children). If μ = 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 number.

Mathematical formulation

Discrete time branching processes

The most common formulation of a branching process is that of the Galton–Watson process, which is a discrete time 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 independent and identically distributed random variables over all n ∈{ 0, 1, 2, ...} and i ∈ {1, ..., Z_n}. The value of the process in the next generation is given by

Z_{n+1}=\sum _{i=1}^{Z_{n}}X_{n,i}

Alternatively, the branching process can be formulated 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, 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.

Continuous-time branching processes

In continuous-time branching processes, each individual waits for a random time (which is a continuous random variable), and then divides according to the given distribution. The waiting time for different individuals are independent, and are independent with the number of children. In Markov processes, the waiting time is an exponential random variable.

Extinction problem for a branching process

The ultimate extinction probability is given by

\lim _{n\to \infty }\Pr(Z_{n}=0).

For any nontrivial cases (trivial cases are ones in which the probability of having no offspring is zero for every member of the population - in such cases the probability of ultimate extinction is 0), the probability of ultimate extinction equals one if μ ≤ 1 and strictly less than one if μ > 1.

The process can be analyzed using the method of probability generating function. Let p₀, p₁, p₂, ... be the probabilities of producing 0, 1, 2, ... offspring by each individual in each generation. Let d_m be the extinction probability by the m^th generation, starting with a single individual (i.e. $Z_{0}=1$ ). Obviously, d₀ = 0 and d₁ = p₀. Since the probabilities for all paths that lead to 0 by the m^th generation must be added up, the extinction probability is nondecreasing in generations. That is,

0=d_{0}\leq d_{1}\leq d_{2}\leq \cdots \leq 1.

Therefore, d_m converges to a limit d, and d is the ultimate extinction probability. If there are j offspring in the first generation, then to die out by the mth generation, each of these lines must die out in m − 1 generations. Since they proceed independently, the probability is (d_m−1) ^j. Thus,

d_{m}=p_{0}+p_{1}d_{m-1}+p_{2}(d_{m-1})^{2}+p_{3}(d_{m-1})^{3}+\cdots .\,

The right-hand side of the equation is a probability generating function. Let h(z) be the ordinary generating function for p_i:

h(z)=p_{0}+p_{1}z+p_{2}z^{2}+\cdots .\,

Using the generating function, the previous equation becomes

d_{m}=h(d_{m-1}).\,

Since d_m → d, d can be found by solving

d=h(d).\,

This is also equivalent to finding the intersection point(s) of lines y = z and y = h(z) for z ≥ 0. y = z is a straight line. y = h(z) is an increasing (since $h'(z)=p_{1}+2p_{2}z+3p_{3}z^{2}+\cdots \geq 0$ ) and convex (since $h''(z)=2p_{2}+6p_{3}z+12p_{4}z^{2}+\cdots \geq 0$ ) function. There are at most two intersection points. Since (1,1) is always an intersect point for the two functions, there only exist three cases:

Three cases of y = h(z) intersecting with y = z.

There is another intersection point at z < 1 (see the red curve in the graph).
There is only one intersection point at z = 1.(See the green curve in the graph)
There is another intersection point at z > 1.(See the black curve in the graph)

In case 1, the ultimate extinction probability is strictly less than one. For case 2 and 3, the ultimate extinction probability equals to one.

By observing that h′(1) = p₁ + 2p₂ + 3p₃ + ... = μ is exactly the expected number of offspring a parent could produce, it can be concluded that for a branching process with generating function h(z) for the number of offspring of a given parent, if the mean number of offspring produced by a single parent is less than or equal to one, then the ultimate extinction probability is one. If the mean number of offspring produced by a single parent is greater than one, then the ultimate extinction probability is strictly less than one.

Example of extinction problem

Consider a parent can produce at most two offspring. The extinction probability in each generation is:

d_{m}=p_{0}+p_{1}d_{m-1}+p_{2}(d_{m-1})^{2}.\,

with d₀ = 0. For the ultimate extinction probability, we need to find d which satisfies d = p₀ + p₁d + p₂d².

Taking as example probabilities for the numbers of offspring produced p₀ = 0.1, p₁ = 0.6, and p₂ = 0.3, the extinction probability for the first 20 generations is as follows:

Generation # (1–10)	Extinction probability	Generation # (11–20)	Extinction probability
1	0.1	11	0.3156
2	0.163	12	0.3192
3	0.2058	13	0.3221
4	0.2362	14	0.3244
5	0.2584	15	0.3262
6	0.2751	16	0.3276
7	0.2878	17	0.3288
8	0.2975	18	0.3297
9	0.3051	19	0.3304
10	0.3109	20	0.331

In this example, we can solve algebraically that d = 1/3, and this is the value to which the extinction probability converges with increasing generations.

Multitype branching processes

In multitype branching processes, individuals are not identical, but can be classified into n types. After each time step, an individual of type i will produce individuals of different types, and $\mathbf {X} _{i}$ , a random vector representing the numbers of children in different types, satisfies a probability distribution on $\mathbb {N} ^{n}$ .

For example, consider the population of cancer stem cells (CSCs) and non-stem cancer cells (NSCCs). After each time interval, each CSC has probability $p_{1}$ to produce two CSCs (symmetric division), probability $p_{2}$ to produce one CSC and one NSCC (asymmetric division), probability $p_{3}$ to produce one CSC (stagnation), and probability $1-p_{1}-p_{2}-p_{3}$ to produce nothing (death); each NSCC has probability $p_{4}$ to produce two NSCCs (symmetric division), probability $p_{5}$ to produce one NSCC (stagnation), and probability $1-p_{4}-p_{5}$ to produce nothing (death).^[4]

Law of large numbers for multitype branching processes

For multitype branching processes that the populations of different types grow exponentially, the proportions of different types converge almost surely to a constant vector as long as the expectation-matrix satisfies the conditions of the Perron-Frobenius theorem (irreducibility and primitivity). This is the strong law of large numbers for multitype branching processes.

For continuous-time cases, proportions of the population expectation satisfy an ODE system, which has a unique attracting fixed point. This fixed point is just the vector that the proportions converge to in the law of large numbers.

The monograph by Athreya and Ney ^[5] summarizes a common set of conditions under which this law of large numbers is valid. Later there are some improvements through discarding different conditions.^[6]^[7]

References

^ Harris, Theodore E. (1963). The Theory of Branching Processes.
^ Athreya, K. B. (2006). "Branching Process". Encyclopedia of Environmetrics. doi:10.1002/9780470057339.vab032. ISBN 978-0-471-89997-6.
^ Ulam, S. M. (1990). Analogies Between Analogies: The mathematical reports of S. M. Ulam and his Los Alamos collaborators.
^ Chen, Xiufang; Wang, Yue; Feng, Tianquan; Yi, Ming; Zhang, Xingan; Zhou, Da (2016). "The overshoot and phenotypic equilibrium in characterizing cancer dynamics of reversible phenotypic plasticity". Journal of Theoretical Biology. 390: 40–49. arXiv:1503.04558. Bibcode:2016JThBi.390...40C. doi:10.1016/j.jtbi.2015.11.008. PMID 26626088. S2CID 15335040.
^ Athreya, Krishna B.; Ney, Peter E. (1972). Branching Processes. Berlin: Springer-Verlag. pp. 199–206. ISBN 978-3-642-65371-1.
^ Janson, Svante (2003). "Functional limit theorems for multitype branching processes and generalized Pólya urns". Stochastic Processes and Their Applications. 110 (2): 177–245. doi:10.1016/j.spa.2003.12.002.
^ Jiang, Da-Quan; Wang, Yue; Zhou, Da (2017). "Phenotypic equilibrium as probabilistic convergence in multi-phenotype cell population dynamics". PLOS ONE. 12 (2) e0170916. Bibcode:2017PLoSO..1270916J. doi:10.1371/journal.pone.0170916. PMC 5300154. PMID 28182672.

C. M. Grinstead and J. L. Snell, Introduction to Probability Archived 2011-07-27 at the Wayback Machine, 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.

[1] Harris, Theodore E. (1963). The Theory of Branching Processes.

[2] Athreya, K. B. (2006). "Branching Process". Encyclopedia of Environmetrics. doi:10.1002/9780470057339.vab032. ISBN 978-0-471-89997-6.

[3] Ulam, S. M. (1990). Analogies Between Analogies: The mathematical reports of S. M. Ulam and his Los Alamos collaborators.

[4] Chen, Xiufang; Wang, Yue; Feng, Tianquan; Yi, Ming; Zhang, Xingan; Zhou, Da (2016). "The overshoot and phenotypic equilibrium in characterizing cancer dynamics of reversible phenotypic plasticity". Journal of Theoretical Biology. 390: 40–49. arXiv:1503.04558. Bibcode:2016JThBi.390...40C. doi:10.1016/j.jtbi.2015.11.008. PMID 26626088. S2CID 15335040.

[5] Athreya, Krishna B.; Ney, Peter E. (1972). Branching Processes. Berlin: Springer-Verlag. pp. 199–206. ISBN 978-3-642-65371-1.

[6] Janson, Svante (2003). "Functional limit theorems for multitype branching processes and generalized Pólya urns". Stochastic Processes and Their Applications. 110 (2): 177–245. doi:10.1016/j.spa.2003.12.002.

[7] Jiang, Da-Quan; Wang, Yue; Zhou, Da (2017). "Phenotypic equilibrium as probabilistic convergence in multi-phenotype cell population dynamics". PLOS ONE. 12 (2) e0170916. Bibcode:2017PLoSO..1270916J. doi:10.1371/journal.pone.0170916. PMC 5300154. PMID 28182672.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

v t e Stochastic processes
Discrete time	Bernoulli process Branching process Chinese restaurant process Galton–Watson process Independent and identically distributed random variables Markov chain Moran process Random walk Loop-erased Self-avoiding Biased Maximal entropy
Continuous time	Additive process Airy process Bessel process Birth–death process pure birth Brownian motion Bridge Dyson Excursion Fractional Geometric Meander Cauchy process Contact process Continuous-time random walk Cox process Diffusion process Empirical process Feller process Fleming–Viot process Gamma process Geometric process Hawkes process Hunt process Interacting particle systems Itô diffusion Itô process Jump diffusion Jump process Lévy process Local time Markov additive process McKean–Vlasov process Ornstein–Uhlenbeck process Poisson process Compound Non-homogeneous Quasimartingale Schramm–Loewner evolution Semimartingale Sigma-martingale Stable process Superprocess Telegraph process Variance gamma process Wiener process Wiener sausage
Both	Branching process Gaussian process Hidden Markov model (HMM) Markov process Martingale Differences Local Sub- Super- Random dynamical system Regenerative process Renewal process Stochastic chains with memory of variable length White noise
Fields and other	Dirichlet process Gaussian random field Gibbs measure Hopfield model Ising model Potts model Boolean network Markov random field Percolation Pitman–Yor process Point process Cox Determinantal Poisson Random field Random graph
Time series models	Autoregressive conditional heteroskedasticity (ARCH) model Autoregressive integrated moving average (ARIMA) model Autoregressive (AR) model Autoregressive moving-average (ARMA) model Generalized autoregressive conditional heteroskedasticity (GARCH) model Moving-average (MA) model
Financial models	Binomial options pricing model Black–Derman–Toy Black–Karasinski Black–Scholes Chan–Karolyi–Longstaff–Sanders (CKLS) Chen Constant elasticity of variance (CEV) Cox–Ingersoll–Ross (CIR) Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White Korn-Kreer-Lenssen LIBOR market Rendleman–Bartter SABR volatility Vašíček Wilkie
Actuarial models	Bühlmann Cramér–Lundberg Risk process Sparre–Anderson
Queueing models	Bulk Fluid Generalized queueing network M/G/1 M/M/1 M/M/c
Properties	Càdlàg paths Continuous Continuous paths Ergodic Exchangeable Feller-continuous Gauss–Markov Markov Mixing Piecewise-deterministic Predictable Progressively measurable Self-similar Stationary Time-reversible
Limit theorems	Central limit theorem Donsker's theorem Doob's martingale convergence theorems Ergodic theorem Fisher–Tippett–Gnedenko theorem Large deviation principle Law of large numbers (weak/strong) Law of the iterated logarithm Maximal ergodic theorem Sanov's theorem Zero–one laws (Blumenthal, Borel–Cantelli, Engelbert–Schmidt, Hewitt–Savage, Kolmogorov, Lévy)
Inequalities	Burkholder–Davis–Gundy Doob's martingale Doob's upcrossing Kunita–Watanabe Marcinkiewicz–Zygmund
Tools	Cameron–Martin theorem Convergence of random variables Doléans-Dade exponential Doob decomposition theorem Doob–Meyer decomposition theorem Doob's optional stopping theorem Dynkin's formula Feynman–Kac formula Filtration Girsanov theorem Infinitesimal generator Itô integral Itô's lemma Kolmogorov continuity theorem Kolmogorov extension theorem Kosambi–Karhunen–Loève theorem Lévy–Prokhorov metric Malliavin calculus Martingale representation theorem Optional stopping theorem Prokhorov's theorem Quadratic variation Reflection principle Skorokhod integral Skorokhod's representation theorem Skorokhod space Snell envelope Stochastic differential equation Tanaka Stopping time Stratonovich integral Uniform integrability Usual hypotheses Wiener space Classical Abstract
Disciplines	Actuarial mathematics Control theory Econometrics Ergodic theory Extreme value theory (EVT) Large deviations theory Mathematical finance Mathematical statistics Probability theory Queueing theory Renewal theory Ruin theory Signal processing Statistics Stochastic analysis Time series analysis Machine learning
List of topics Category