Namespaces
Variants
Actions

Branching process

From Encyclopedia of Mathematics
Jump to: navigation, search


2020 Mathematics Subject Classification: Primary: 60J80 [MSN][ZBL]

A stochastic process describing a wide circle of phenomena connected with the reproduction and transformation of given objects (e.g. of particles in physics, of molecules in chemistry, of some particular population in biology, etc.). The class of branching processes is singled-out by the fundamental assumption that the reproductions of individual particles are mutually independent.

A time-homogeneous branching process $ \mu (t) $ with one type of particles is defined as a Markov process with a countable number of states $ 0, 1 \dots $ the transition probabilities $ P _ {ij} (t) $ of which satisfy the additional branching condition:

$$ \tag{1 } P _ {ij} (t) = \ \sum _ {j _ {1} + \dots + j _ {i} = j } P _ {1 j _ {1} } (t) \dots P _ {1 j _ {i} } (t). $$

The states $ 0, 1 \dots $ of a branching process are interpreted as numbers of particles. The probability $ P _ {ij} (t) $ is equal to the probability

$$ {\mathsf P} \{ \mu (t + t _ {0} ) = j \mid \mu (t _ {0} ) = i \} $$

of transition from state $ i $ to state $ j $ during a time interval of length $ t $. The principal analytical tools of branching processes are the generating functions (cf. Generating function)

$$ \tag{2 } F (t; s) = \ \sum _ {n = 0 } ^ \infty {\mathsf P} \{ \mu (t) = n \mid \mu (0) = 1 \} s ^ {n} . $$

The equality

$$ \tag{3 } F (t + \tau ; s) = F (t; F ( \tau ; s)) $$

follows from the branching condition. In branching processes with discrete time, $ t $ assumes non-negative integral values, and it follows from (3) that $ F(t; s) $ is a $ t $- fold iteration of the function $ F(s) = F(1; s) $. Such a process is sometimes called a Galton–Watson process. In a continuous-time branching process it is assumed that $ t \in [0, \infty ) $ and that the right-side derivative

$$ \left . \frac{\partial F (t; s) }{\partial t } \right | _ {t=0} = f (s) $$

exists. It follows from (3) that $ F(t; s) $ satisfies the differential equation

$$ \tag{4 } \frac{\partial F (t; s) }{\partial t } = \ f (F (t; s)) $$

and the initial condition $ F(0; s) = s $.

If $ A = F ^ { \prime } (1) $ and $ a = f ^ { \prime } (1) $ are finite, the mathematical expectation $ {\mathsf E} \mu (t) $ of the number of particles $ \mu (t) $( under the condition $ \mu (0) = 1 $) is $ A ^ {t} $ for a discrete-time branching process and $ e ^ {at} $ for a continuous-time branching process. Depending on the values of the parameters $ A $ or $ a $, branching processes are subdivided into subcritical ( $ A < 1 $, $ a < 0 $), critical ( $ A=1 $, $ a=0 $) and supercritical ( $ A > 1 $, $ a > 0 $). The main characteristic governed by this classification is the behaviour of $ {\mathsf E} \mu (t) $ as $ t \rightarrow \infty $.

In what follows, the trivial cases $ F(s) \equiv s $ and $ f(s) \equiv 0 $, when

$$ {\mathsf P} \{ \mu (t) = 1 \mid \mu (0) = 1 \} \equiv 1 , $$

will not be discussed.

The probability of extinction is one in subcritical and critical branching processes and is less than one in supercritical processes. If $ {\mathsf E} \mu (t) \cdot \mathop{\rm ln} \mu (t) < \infty $, then, in the subcritical range, the probability $ {\mathsf P} \{ \mu (t) > 0 \} $ of survival of the process behaves asymptotically, as $ t \rightarrow \infty $, as $ K {\mathsf E} \mu (t) $, where $ K $ is a positive constant. In the case of critical branching processes with finite $ {\mathsf E} \mu ^ {2} (t) $, the asymptotic behaviour as $ t \rightarrow \infty $ is

$$ {\mathsf P} \{ \mu (t) > 0 \} \approx { \frac{2}{ {\mathsf D} \mu (t) } } , $$

where $ {\mathsf D} \mu (t) = B t $ in discrete-time branching process and $ {\mathsf D} \mu (t) = bt $ in continuous-time branching process and where $ B = F ^ { \prime\prime } (1) $, $ b = f ^ { \prime\prime } (1) $. A more detailed study of the asymptotic behaviour of the distribution of $ \mu (t) $ as $ t \rightarrow \infty $ shows that the conditional distribution law

$$ \tag{5 } S _ {t} (x) = {\mathsf P} \left \{ \frac{\mu (t) }{ {\mathsf E} \{ \mu (t) \mid \mu (t) > 0 \} } \leq x \mid \mu (t) > 0 \right \} $$

converges weakly as $ t \rightarrow \infty $ towards a limit distribution $ S(x) $ if certain moments of $ \mu (t) $ are finite. In subcritical branching processes the limit law $ S(x) $ is discrete, while in other cases it is absolutely continuous. Of special interest is the case of critical branching processes for which the limit law $ S(x) $ is exponential:

$$ \tag{6 } S (x) = 1 - e ^ {-x} ,\ x \geq 0. $$

The distribution (6) is also a limit distribution for near-critical branching processes. More exactly, if one considers the class of generating functions $ F(s) $ or $ f(s) $ with a bounded third derivative $ F ^ { \prime\prime\prime } (1) $, $ f ^ { \prime\prime\prime } (1) $ and $ F ^ { \prime\prime } (1) \geq B _ {0} > 0 $, $ f ^ { \prime\prime } (1) \geq b _ {0} > 0 $, then

$$ \lim\limits _ {\begin{array}{c} t \rightarrow \infty \\ A \rightarrow 1 \end{array} } \ S _ {t} (x) = \ 1 - e ^ {-x} ,\ \ x \geq 0, $$

where $ S _ {t} (x) $ is defined by formula (5). The phenomena occurring in near-critical processes at $ t \rightarrow \infty $ are said to be transient.

Another model of branching processes is the Bellman–Harris process, in which each particle has a random lifetime with distribution function $ G(t) $. At the end of its lifetime, the particle leaves behind $ n $ daughter particles with probability $ q _ {n} $;

$$ \sum _ {n = 0 } ^ \infty q _ {n} = 1. $$

The lifetimes and the number of daughter particles produced by individual particles are independent. Consider a particle of age zero at the initial moment of time $ t=0 $; then the generating function $ F(t; s) $ of the number of particles $ \mu (t) $ at the moment of time $ t $, given by formula (2), satisfies the non-linear integral equation

$$ \tag{7 } F (t; s) = \ \int\limits _ { 0 } ^ { t } h (F (t - u; s)) dG (u) + s (1 - G (t)), $$

where

$$ h (s) = \ \sum _ {n = 0 } ^ \infty q _ {n} s ^ {n} . $$

If $ G(t) $ is a degenerate distribution function, the Bellman–Harris process is a discrete-time branching process; if $ G(t) $ is an exponential distribution function, one obtains a continuous-time branching process. In the general case, the Bellman–Harris process is a non-Markov branching process.

A branching process may also be complicated by the dependence of the particles on their location in space. For instance, let each particle execute an independent Brownian motion in an $ r $- dimensional domain $ G $ with an absorbing boundary $ \partial G $. A particle located inside the domain $ G $ will be transformed within time $ \Delta t \rightarrow 0 $ with probability

$$ p _ {n} \Delta t + o ( \Delta t),\ \ n \neq 1, $$

into $ n $ particles, and each such particle begins to execute an independent motion along Brownian trajectories starting from its point of genesis. Let $ \mu _ {x,t} (A) $ be the number of particles in a set $ A $ at the moment of time $ t $, that number having been produced by one particle located at the point $ x \in G $ at the initial moment of time 0. The generating function

$$ H (t, x, s( \cdot )) = \ {\mathsf E} \mathop{\rm exp} \left [ \int\limits _ { G } \mathop{\rm ln} s (y) \mu _ {x,t} (dy) \right ] $$

satisfies the quasi-linear parabolic equation

$$ \tag{8 } \Delta H + f (H) = 0 $$

with the initial condition $ H(0, x, s( \cdot )) = s(x) $ and the boundary condition $ H(t, x, s ( \cdot )) \mid _ {x \rightarrow \partial G } = 0 $, where $ \Delta = {\sum _ {i=1} ^ {r} } \partial ^ {2} / \partial x _ {i} ^ {2} $ is the Laplace operator, and $ f(s) = {\sum _ {n} } p _ {n} s ^ {n} $, $ p _ {1} = - \sum _ {n \neq 1 } p _ {n} $.

It is assumed in general branching processes that the propagating particles can be characterized by certain parameters, which may be interpreted as age, location of the particle in space, type, size or energy of the particle, etc. Such processes are studied with the aid of generating functions or functionals, for which non-linear differential and integral equations, generalizing equations (4), (7) and (8), are deduced. One may give the following general descriptions of such models of branching processes. Let particles move, independently of each other, in accordance with Markov's law in some phase space $ X $. It is assumed that the random lifetime of a particle is a Markov time (cf. Markov moment) which depends on its trajectory. At the end of its lifetime the particle generates new particles, which become distributed over the phase space $ X $ in accordance with some probability law. The new particles evolve in a similar manner, independently of each other. In the space of integer-valued measures determined by the number of particles present in subsets of $ X $, the branching process is Markovian. However, branching processes are often studied in simpler reduced spaces as well. In such a case many of them become non-Markovian.

In most of the models discussed above the subdivision of processes into subcritical, critical and supercritical processes retains its meaning. Many properties of simple branching processes described by equation (4) are also displayed by more complex systems. In particular, the limiting distribution of (5), for critical processes, usually turns out to be an exponential distribution (6) (in an appropriate norm).

Branching processes are used in calculations of various real processes — biological, genetic, physical, chemical or technological. In real processes the condition of independent motion of each particle is often not met, and the generated daughter particles may interact with each other. This is true of many biological reproduction processes, in processes of propagation of epidemics (cf. Epidemic process), in bimolecular chemical reactions, etc. However, the initial stages of such processes may be calculated with the aid of suitably chosen models of branching processes. This is done in situations in which the number of active particles in the space is relatively small; at such low concentrations their mutual collisions are practically non-existent, and the state of the system evolves by the collisions between active particles and the particles of the medium. In epidemic processes, for example, sick individuals may be considered as such "active particles" . Phenomena related to genetic mutations, for example, may be calculated with the aid of branching processes. The branching process with a finite number of particle types may serve as a model in computing chain reactions; the branching process with diffusion may serve as a model of neutron processes in nuclear reactors. Phenomena occurring in showers of cosmic particles may also be studied with the aid of branching processes. In telephony, the computation of certain expectation systems may be reduced to branching process models.

See also Branching process with a random medium; Branching process with immigration; Branching processes, regularity of.

References

[S] B.A. Sewastjanow, "Verzweigungsprozesse" , Akad. Wissenschaft. DDR (1974) (Translated from Russian) MR0408018 Zbl 0291.60039
[AN] K.B. Athreya, P.E. Ney, "Branching processes" , Springer (1972) MR0373040 Zbl 0259.60002

Comments

Applications of branching process in biology may be found in [J]. The survey article [JN] gives an up-to-date account of stable population theory and balanced exponential growth, items that are also relevant in biological applications.

References

[AH] S. Asmussen, H. Hering, "Branching processes" , Birkhäuser (1983) MR0701538 Zbl 0516.60095
[J] P. Jagers, "Branching processes with biological applications" , Wiley (1975) MR0488341 Zbl 0356.60039
[JN] P. Jagers, O. Nerman, "The growth and composition of branching populations" Adv. Appl. Probab. , 16 (1984) pp. 221–259 MR0742953 Zbl 0535.60075
How to Cite This Entry:
Branching process. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Branching_process&oldid=46150
This article was adapted from an original article by B.A. Sevast'yanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article