Namespaces
Variants
Actions

Difference between revisions of "Branching process"

From Encyclopedia of Mathematics
Jump to: navigation, search
(refs format)
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
b0175301.png
 +
$#A+1 = 104 n = 0
 +
$#C+1 = 104 : ~/encyclopedia/old_files/data/B017/B.0107530 Branching process
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
{{MSC|60J80}}
 
{{MSC|60J80}}
  
Line 5: Line 17:
 
A [[Stochastic process|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 [[Stochastic process|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b0175301.png" /> with one type of particles is defined as a [[Markov process|Markov process]] with a countable number of states <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b0175302.png" /> the transition probabilities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b0175303.png" /> of which satisfy the additional branching condition:
+
A time-homogeneous branching process $  \mu (t) $
 +
with one type of particles is defined as a [[Markov process|Markov process]] with a countable number of states 0, 1 \dots $
 +
the transition probabilities $  P _ {ij} (t) $
 +
of which satisfy the additional branching condition:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b0175304.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b0175305.png" /> of a branching process are interpreted as numbers of particles. The probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b0175306.png" /> is equal to the probability
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b0175307.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ \mu (t + t _ {0} ) =
 +
j \mid  \mu (t _ {0} ) = i \}
 +
$$
  
of transition from state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b0175308.png" /> to state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b0175309.png" /> during a time interval of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753010.png" />. The principal analytical tools of branching processes are the generating functions (cf. [[Generating function|Generating function]])
+
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|Generating function]])
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753011.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
F (t; s)  = \
 +
\sum _ {n = 0 } ^  \infty 
 +
{\mathsf P} \{ \mu (t) =
 +
n \mid  \mu (0) = 1 \} s  ^ {n} .
 +
$$
  
 
The equality
 
The equality
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753012.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \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 }
  
follows from the branching condition. In branching processes with discrete time, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753013.png" /> assumes non-negative integral values, and it follows from (3) that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753014.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753015.png" />-fold iteration of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753016.png" />. Such a process is sometimes called a Galton–Watson process. In a continuous-time branching process it is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753017.png" /> and that the right-side derivative
+
\right | _ {t=0= f (s)
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753018.png" /></td> </tr></table>
+
exists. It follows from (3) that  $  F(t; s) $
 +
satisfies the differential equation
  
exists. It follows from (3) that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753019.png" /> satisfies the differential equation
+
$$ \tag{4 }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753020.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
\frac{\partial  F (t; s) }{\partial  t }
 +
  = \
 +
f (F (t; s))
 +
$$
  
and the initial condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753021.png" />.
+
and the initial condition $  F(0;  s) = s $.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753023.png" /> are finite, the mathematical expectation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753024.png" /> of the number of particles <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753025.png" /> (under the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753026.png" />) is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753027.png" /> for a discrete-time branching process and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753028.png" /> for a continuous-time branching process. Depending on the values of the parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753029.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753030.png" />, branching processes are subdivided into subcritical (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753032.png" />), critical (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753033.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753034.png" />) and supercritical (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753035.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753036.png" />). The main characteristic governed by this classification is the behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753037.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753038.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753039.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753040.png" />, when
+
In what follows, the trivial cases $  F(s) \equiv s $
 +
and $  f(s) \equiv 0 $,  
 +
when
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753041.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ \mu (t) = 1 \mid  \mu (0) = 1 \}  \equiv  1 ,
 +
$$
  
 
will not be discussed.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753042.png" />, then, in the subcritical range, the probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753043.png" /> of survival of the process behaves asymptotically, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753044.png" />, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753045.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753046.png" /> is a positive constant. In the case of critical branching processes with finite <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753047.png" />, the asymptotic behaviour as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753048.png" /> is
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753049.png" /></td> </tr></table>
+
$$ \tag{5 }
 +
S _ {t} (x)  = {\mathsf P}
 +
\left \{
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753050.png" /> in discrete-time branching process and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753051.png" /> in continuous-time branching process and where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753053.png" />. A more detailed study of the asymptotic behaviour of the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753054.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753055.png" /> shows that the conditional distribution law
+
\frac{\mu (t) }{ {\mathsf E} \{ \mu (t) \mid  \mu (t) > 0 \} }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753056.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
\leq  x \mid  \mu (t) > 0
 +
\right \}
 +
$$
  
converges weakly as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753057.png" /> towards a limit distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753058.png" /> if certain moments of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753059.png" /> are finite. In subcritical branching processes the limit law <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753060.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753061.png" /> is exponential:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753062.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>
+
$$ \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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753063.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753064.png" /> with a bounded third derivative <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753068.png" />, then
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753069.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {\begin{array}{c}
 +
t \rightarrow \infty \\
 +
A \rightarrow 1
 +
\end{array}
 +
} \
 +
S _ {t} (x)  = \
 +
1 - e  ^ {-x} ,\ \
 +
x \geq  0,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753070.png" /> is defined by formula (5). The phenomena occurring in near-critical processes at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753071.png" /> are said to be transient.
+
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|Bellman–Harris process]], in which each particle has a random lifetime with distribution function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753072.png" />. At the end of its lifetime, the particle leaves behind <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753073.png" /> daughter particles with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753074.png" />;
+
Another model of branching processes is the [[Bellman–Harris process|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} $;
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753075.png" /></td> </tr></table>
+
$$
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753076.png" />; then the generating function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753077.png" /> of the number of particles <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753078.png" /> at the moment of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753079.png" />, given by formula (2), satisfies the non-linear integral equation
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753080.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>
+
$$ \tag{7 }
 +
F (t; s)  = \
 +
\int\limits _ { 0 } ^ { t }
 +
h (F (t - u; s))
 +
dG (u) + s (1 - G (t)),
 +
$$
  
 
where
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753081.png" /></td> </tr></table>
+
$$
 +
h (s)  = \
 +
\sum _ {n = 0 } ^  \infty 
 +
q _ {n} s  ^ {n} .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753082.png" /> is a degenerate distribution function, the Bellman–Harris process is a discrete-time branching process; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753083.png" /> 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.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753084.png" />-dimensional domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753085.png" /> with an absorbing boundary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753086.png" />. A particle located inside the domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753087.png" /> will be transformed within time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753088.png" /> with probability
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753089.png" /></td> </tr></table>
+
$$
 +
p _ {n} \Delta t + o
 +
( \Delta t),\ \
 +
n \neq 1,
 +
$$
  
into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753090.png" /> particles, and each such particle begins to execute an independent motion along Brownian trajectories starting from its point of genesis. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753091.png" /> be the number of particles in a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753092.png" /> at the moment of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753093.png" />, that number having been produced by one particle located at the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753094.png" /> at the initial moment of time 0. The generating function
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753095.png" /></td> </tr></table>
+
$$
 +
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
 
satisfies the quasi-linear parabolic equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753096.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>
+
$$ \tag{8 }
 +
\Delta H + f (H)  = 0
 +
$$
  
with the initial condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753097.png" /> and the boundary condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753098.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b01753099.png" /> is the Laplace operator, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b017530100.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b017530101.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b017530102.png" />. It is assumed that the random lifetime of a particle is a Markov time (cf. [[Markov moment|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b017530103.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017530/b017530104.png" />, 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.
+
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|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).
 
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).

Latest revision as of 06:29, 30 May 2020


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=26369
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