Informally, a branching process 2 is described as follows, where \(\{p_k\}_{k\ge0}\) is a fixed probability mass function (pmf).
A population starts with a single ancestor who forms generation number \(0\).
This initial individual splits into \(k\) offspring with probability \(p_k\) for each \(k\ge 0\); the resulting offspring constitute the first generation.
Each of the offspring in the first generation splits independently into a random number of offspring, again according to the pmf \(\{p_k\}_{k\ge 0}\), and the resulting offspring constitute the second generation.
This process continues until extinction, which occurs when all the members of a generation fail to produce offspring.
This model has a number of applications in biology (eg., it can be thought as a model of population growth), physics (chain reaction in nuclear fission), queueing theory, etc. Originally it arose from a study of the likelihood of survival of family names (“how fertile must a family be to ensure that in future generations the family name will not die out?”).
Formally, let \(\{Z_{n,k}\}\), \(n\ge1\), \(k\ge1\), be a family of i.i.d. random variables in \({\mathbb{Z}}^+\), each having a common probability mass function \(\{p_k\}_{k\ge0}\). Then the branching process \((Z_n)_{n\ge0}\) (generated by \(\{p_k\}_{k\ge0}\)) is defined by setting \(Z_0=1\), and, for \(n\ge1\), \[\begin{equation} \label{eq:branch-process-recursion} Z_n\stackrel{{\sf def}}{=}Z_{n,1}+Z_{n,2}+\dots+Z_{n,Z_{n-1}}\,, \end{equation}\] where the empty sum is interpreted as zero. Notice that \(Z_n\) is a Markov chain in \({\mathbb{Z}}^+\). We shall use \({\mathsf{P}}(\,\cdot\,)\equiv{\mathsf{P}}_1(\,\cdot\,)\) and \({\mathsf{E}}(\,\cdot\,)\equiv{\mathsf{E}}_1(\,\cdot\,)\) to denote the corresponding probability measure and the expectation operator. 3 If \(\varphi_n(s)\equiv{\mathsf{E}}(s^{Z_n})\) is the generating function of \(Z_n\), a straightforward induction based on ([eq:branch-process-recursion]) and ([eq:GN-GX]) implies that \[\varphi_0(s)\equiv s\,,\qquad \varphi(s)\equiv\varphi_1(s)\equiv{\mathsf{E}}{s^{Z_1}}\,,\] \[\begin{equation} \label{eq:branch-process-gener-fn} \varphi_k(s)=\varphi_{k-1}\bigl(\varphi(s)\bigr)\equiv\varphi\bigl(\varphi_{k-1}(s)\bigr)=\underset{k \text{ times }}{\underbrace{\varphi(\dots \varphi(s)\dots)\dots)}} \quad k>1 . \end{equation}\] Usually explicit calculations are hard, but at least in principle, equations ([eq:branch-process-gener-fn]) determine the distribution of \(Z_n\) for any \(n\ge0\).
Let \(\varphi_1(s)\equiv\varphi(s)=q+ps\) for some \(0<p=1-q<1\). Then \[\varphi_n(s)\equiv q(1+p+\dots+p^{n-1})+p^ns=1+p^n(s-1)\,.\] Notice that here we have \(\varphi_n(s)\to1\) as \(n\to\infty\), for all \(s\in[0,1]\). In other words, the distribution of \(Z_n\) converges to that of \(Z_\infty\equiv0\), recall Theorem [thm:convergence-in-distribution-via-generating-functions].
The following result is a straightforward corollary of ([eq:GN-GX]).
In a branching process \((Z_n)_{n\ge0}\) with \(Z_0=1\), let the offspring distribution have mean \(m\). Then \({\mathsf{E}}(Z_n)=m^n\) for all \(n\ge 1\).
Recall that a random variable \(X\) with values in \(\mathbb{Z}_{\ge 0}\) has finite mean equal to \(G_X'(1_{-}):=\lim_{s\uparrow 1} G_{X}'(s)\), if and only if this limit exists and is finite. Since \(Z_1\) is assumed to have finite mean \(m\), this implies that \(\varphi'(1_{-}):=\lim_{s\uparrow 1} \varphi'(s)=m\) (where \(\varphi\) is the generating function of \(Z_1\)). We also know by ([eq:GN-GX]) that the generating function of \(Z_n\) is given by \(\varphi_n\) which is just the composition of \(\varphi\) with itself \(n\) times. By the chain rule, and since \(\varphi_k(1)=1\) for all \(k\), we see that \[\lim_{s\uparrow 1} \varphi_n'(1_{-})=\varphi'(1_{-})^n=m^n,\] implying the result. This can alternatively be shown by induction, using a conditioning argument.
In a branching process \((Z_n)_{n\ge0}\) with \(Z_0=1\), let the offspring distribution have mean \(m\), variance \(\sigma^2\), and generating function \(\varphi\). Write \(\varphi_n\) for the generating function of the \(n\)th generation size \(Z_n\), \(\varphi_n(s)\equiv{\mathsf{E}}(s^{Z_n})\).
Using ([eq:branch-process-gener-fn]) or otherwise, show that \({\mathsf{Var}}(Z_n)=\sigma^2m^{n-1}(m^n-1)/(m-1)\) if \(m\neq1\) and \({\mathsf{Var}}(Z_n)=\sigma^2n\) if \(m=1\).
Deduce that \({\mathsf{E}}\bigl((Z_n/m^n)^2\bigr)\) is uniformly bounded for \(m\ne 1\).
This result suggests that if \(m\equiv{\mathsf{E}}(Z_1) \neq1\), the branching process might explode (for \(m>1\)) or die out (for \(m<1\)). One therefore classifies branching process as either critical (if \(m=1\)), subcritical (\(m<1\)), or supercritical (\(m>1\)).
It is straightforward to describe the case \(m<1\). Indeed, the Markov inequality ([eq:Markov]) implies that \[{\mathsf{P}}(Z_n>0)={\mathsf{P}}(Z_n\ge1)\le{\mathsf{E}}(Z_n)=m^n\,,\] so that \({\mathsf{P}}(Z_n>0)\to0\) as \(n\to\infty\) (ie., \(Z_n\to0\) in probability). We also notice that the average total population in this case is finite, \({\mathsf{E}}\bigl(\sum_{n\ge0}Z_n\bigr)=\sum_{n\ge0}m^n=(1-m)^{-1}<\infty\).
The extinction event \({\mathcal{E}}\) is the event \({\mathcal{E}}=\cup_{n=1}^\infty\bigl\{Z_n=0\bigr\}\). Since \(\bigl\{Z_n=0\bigr\}\subset\bigl\{Z_{n+1}=0\bigr\}\) for all \(n\ge0\), the extinction probability \(\rho\) is defined as \[\rho={\mathsf{P}}({\mathcal{E}})=\lim_{n\to\infty}{\mathsf{P}}\bigl(Z_n=0\bigr)\,,\] where \({\mathsf{P}}\bigl(Z_n=0\bigr)\equiv\varphi_n(0)\) is the extinction probability before \((n+1)\)st generation.
The following result helps to derive the extinction probability \(\rho\) without needing to compute the iterates \(\varphi_n(\,\cdot\,)\) precisely. To avoid trivialities we shall assume that \(p_0={\mathsf{P}}(Z=0)\) satisfies 4 \(0<p_0<1\); notice that under this assumption \(\varphi(s)\) is a strictly increasing function of \(s\in[0,1]\).
If \(0<p_0<1\), then the extinction probability \(\rho\) is given by the smallest positive solution to the equation \[\begin{equation} \label{eq:extinction-probability-solution} s=\varphi(s)\,. \end{equation}\] In particular, if \(m={\mathsf{E}}Z_1\le1\), then \(\rho=1\); otherwise, we have \(0<\rho<1\).
In words, if the branching process is subcritical or critical then it eventually becomes extinct with probability one. However, if it is supercritical, the process has a positive probability to survive for all time.
There is a clear probablistic intuition behind the relation \(\rho=\varphi(\rho)\). Indeed, if \(\rho={\mathsf{P}}_1({\mathcal{E}})\) is the extinction probability starting from a single individual, \(Z_0=1\), then by independence we get \({\mathsf{P}}_k({\mathcal{E}})\equiv{\mathsf{P}}({\mathcal{E}}\mid Z_0=k)=\rho^k\), and thus the first step decomposition for the Markov chain \(Z_n\) gives \[\begin{aligned} \rho={\mathsf{P}}({\mathcal{E}})&=\sum_{k\ge0}{\mathsf{P}}({\mathcal{E}},Z_1=k)=\sum_{k\ge0}{\mathsf{P}}({\mathcal{E}}\mid Z_1=k){\mathsf{P}}(Z_1=k) \\ &=\sum_{k\ge0}\rho^k\,{\mathsf{P}}(Z_1=k)\equiv{\mathsf{E}}\bigl(\rho^{Z_1}\bigr)\equiv\varphi(\rho)\,, \end{aligned}\] in agreement with ([eq:extinction-probability-solution]).
Let us now give the proof of Theorem [thm:branching-extinction]. You may find it helpful to draw a picture!
Denote \(\rho_n={\mathsf{P}}\bigl(Z_n=0\bigr)\equiv\varphi_n(0)\). By continuity and strict monotonicity of \(\varphi(\,\cdot\,)\) we have (recall ([eq:branch-process-gener-fn])) \[0<\rho_1=\varphi(0)<\rho_2=\varphi(\rho_1)<\dots<1\,,\] so that the extinction probability \(\rho\in (0,1]\) is the increasing limit of \(\rho_n\) as \(n\to \infty\), and satisfies \[\rho=\lim_n\varphi_n(0)=\lim_n \varphi(\varphi_{n-1}(0))=\varphi(\lim_n \varphi_{n-1}(0))=\varphi(\rho).\] On the other hand, if \(\bar\rho\) is any other fixed point of \(\varphi(\,\cdot\,)\) in \([0,1]\), ie., \(\bar\rho=\varphi(\bar\rho)\), then \(\bar\rho=\varphi_n(\bar\rho)\ge \varphi_n(0)\) for all \(n\), meaning that \(\bar\rho \ge \lim_{n\to \infty} \varphi_n(0)=\rho\). So, \(\rho\) is indeed the smallest positive solution to ([eq:extinction-probability-solution]).
Next, we turn to the extinction criterion in terms of \(m\). For this, observe that \(\varphi(\,\cdot\,)\) is convex on \([0,1]\), since \(\varphi''(s)={\mathsf{E}}(Z_1(Z_1-1)s^{Z_1-2})\ge 0\) for \(s\in [0,1]\) (actually unless \(p_1=1-p_0\), i.e., if there is some possibility of having more than 1 child, \(\varphi''(s)\) is strictly positive and so \(\varphi\) is strictly convex on \((0,1)\)). Hence if \(m=\varphi'(1_{-})>1\) we must have \(\varphi(s_0)<s_0\) for some \(s_0<1\) and therefore the curves \(y=s\) and \(y=\varphi(s)\) must cross at some point strictly in \((0,1)\) (recall that \(\varphi(0)=p_0>0\)). A completely rigorous way to justify this is to define \(f(s):=\varphi(s)-s\), which is continuous on \([0,s_0]\) with \(f(s_0)<0\) and \(f(0)>0\), so by the intermediate value theorem satisfies \(f(s)=0\), i.e. \(\varphi(s)=s\), for some \(s\in (0,s_0)\). Conversely, suppose that \(m\le 1\) and \(p_1\ne 1-p_0\). Then the condition \(m=\varphi'(1_{-})\le1\) together with strict convexity implies that \(\varphi(s)-s\) is strictly decreasing on \([0,1]\), from \(p_0\) at \(0\) to \(0\) at \(1\), and therefore cannot be \(0\) for any \(s<1\). The case \(p_1=1-p_0\) give \(\varphi(s)=p_0+p_1 s\) and it is immediate that the smallest solution of \(\varphi(s)=s\) in \([0,1]\) is at \(1\). This completes the proof.
If \(s\in[0,1)\), we have \(\varphi_n(s)\equiv{\mathsf{E}}\bigl(s^{Z_n}\bigr)\to\rho\in(0,1]\) as \(n\to\infty\).
As a result, the distribution of \(Z_n\) converges to that of \(Z_\infty\), where \({\mathsf{P}}(Z_\infty=0)=\rho\) and \({\mathsf{P}}(Z_\infty=\infty)=1-\rho\).
For a branching process with generating function \(\varphi(s)=as^2+bs+c\), where \(a>0\), \(b>0\), \(c>0\), \(\varphi(1)=1\), compute the extinction probability \(\rho\) and give the condition for sure extinction. Can you interpret your results?
Let \((Z_n)_{n\ge0}\) be a branching process with generating function \(\varphi(s)\equiv{\mathsf{E}}{s^{Z_1}}\) satisfying \(0<\varphi(0)<1\). Let \[\bar\varphi_n(u)\stackrel{{\sf def}}{=}{\mathsf{E}}\bigl(u^{\bar{Z}_n}\bigr)\] be the generating function of \[\bar{Z}_n=\sum_{k=0}^nZ_k,\] the total population size up to time \(n\).
Show that \(\bar\varphi_{n+1}(u)=u\,\varphi\bigl(\bar\varphi_n(u)\bigr)\) for all \(n\ge0\) and \(u\ge0\).
If \(u\in(0,1)\), show that \(\bar\varphi_n(u)\to\bar\varphi(u)\stackrel{{\sf def}}{=}{\mathsf{E}}\bigl(u^{\bar{Z}}\bigr)\) as \(n\to\infty\), where \(\bar{Z}\) is the total population size, \(\sum_{k\ge0}Z_k\), of \((Z_n)_{n\ge0}\). Show that the limiting generating function \(\bar\varphi(u)\) is given by the smallest positive solution \(s\) to the equation \(s=u\varphi(s)\).
Let the process \((Z_n)_{n\ge0}\) be subcritical (\(\varphi'(1_{-})<1\)) with offspring distribution having exponential tails (\(\varphi(s)<\infty\) for some \(s>1\)). Show that for some \(u>1\) the equation \(s=u\varphi(s)\) has positive solutions \(s\), the smallest of which coincides with \(\bar\varphi(u)={\mathsf{E}}\bigl(u^{\bar{Z}}\bigr)\).
Let the process \((Z_n)_{n\ge0}\) be supercritical (\({\mathsf{E}}{Z_1}>1\)) with \(0<{\mathsf{P}}(Z_1=0)<1\) and let \(u>1\) be such that the equation \(s=u\varphi(s)\) has positive solutions \(s\). Show that \(\bar\varphi_n(u)\to\infty\), in agreement with the fact that with positive probability the process \((Z_n)_{n\ge0}\) survives forever, \({\mathsf{P}}(\bar{Z}=\infty)>0\).
In the setting of part d), let \(\hat\varphi_n(u)\stackrel{{\sf def}}{=}{\mathsf{E}}\bigl(u^{\bar{Z}_n}\mathsf{1}_{Z_n=0}\bigr)\), the generating function of the total population on the event that the process \((Z_n)_{n\ge0}\) dies out by time \(n\). Show that \(\hat\varphi_{n+1}(u)=u\varphi\bigl(\hat\varphi_n(u)\bigr)\) for all \(n\ge0\) and \(u\ge0\). Deduce that for each \(u>1\) such that the fixed point equation \(s=u\varphi(s)\) has positive solutions \(s\), we have \(\hat\varphi_n(u)\to{\mathsf{E}}\bigl(u^{\bar{Z}}\mathsf{1}_{\bar{Z}<\infty}\bigr)\), where the latter coincides with the smallest positive \(s\) satisfying \(s=u\varphi(s)\).
We now turn to classification of states for the Markov chain \(Z_n\) in \({\mathbb{Z}}^+\). Of course, since \(0\) is an absorbing state, it is recurrent.
If \(p_1={\mathsf{P}}(Z_1=1)\neq1\), then every state \(k\in{\mathbb{N}}\) is transient. As a result, \[{\mathsf{P}}(Z_n\to\infty)=1-{\mathsf{P}}(Z_n\to0)=1-\rho\,.\]
We first show that every \(k\in{\mathbb{N}}\) is transient. If \(p_0=0\), then \(Z_n\) is a non-decreasing Markov chain (ie., \(Z_{n+1}\ge Z_n\)), so that for every \(k\in{\mathbb{N}}\) the first passage probability \(f_{kk}\) satisfies \[f_{kk}={\mathsf{P}}\bigl(Z_{n+1}=k\mid Z_n=k\bigr)={\mathsf{P}}_k(Z_1=k)=(p_1)^k<1\,.\] On the other hand, for \(p_0\in(0,1]\) we have \[f_{kk}\le{\mathsf{P}}\bigl(Z_{n+1}\neq0\mid Z_n=k\bigr)={\mathsf{P}}_k(Z_1\neq0)=1-{\mathsf{P}}_k(Z_1=0)=1-(p_0)^k<1\,.\] This means that \[{\mathsf{P}}(Z_n=k \text{ i.o.})=\lim_{m\to \infty} {\mathsf{P}}(Z_n \text{ returns to } k \text{ at least } m \text{ times})\le \lim_{m\to \infty} f_{kk}^{m-1}=0\] and the state \(k\) is transient.
Fix arbitrary \(K>0\). Since the states \(1\), \(2\), …, \(K\) are transient, we see that \({\mathsf{P}}\bigl(\{Z_n=0\}\cup\{Z_n>K\}\bigr)\to1\) as \(n\to \infty\) and therefore \[{\mathsf{P}}\bigl(Z_n\to0\text{ or }Z_n\to\infty\bigr)=1\,.\] As the LHS above equals \({\mathsf{P}}(Z_n\to0)+{\mathsf{P}}(Z_n\to\infty)\), the result follows from the observation that \({\mathsf{P}}(Z_n\to0)\equiv{\mathsf{P}}({\mathcal{E}})=\rho\).
For a supercritical branching process \((Z_n)_{n\ge0}\), let \(T_0=\min\{n\ge0:Z_n=0\}\) be its extinction time and let \(\rho={\mathsf{P}}(T_0<\infty)>0\) be its extinction probability. Define \((\widehat{Z}_n)_{\ge0}\) as \(Z_n\) conditioned on extinction, ie., \(\widehat{Z}_n=\bigl(Z_n\mid T_0<\infty\bigr)\).
Show that the transition probabilities \(\hat{p}_{xy}\) of \((\widehat{Z}_n)_{n\ge0}\) and the transition probabilities \(p_{xy}\) of the original process \((Z_n)_{n\ge0}\) are related via \(\hat{p}_{xy}=p_{xy}\rho^{y-x}\), \(x,y\ge0\).
Deduce that the generating functions \(\widehat\varphi(s)\equiv{\mathsf{E}}_1\bigl[s^{\widehat{Z}_1}\bigr]\) and \(\varphi(s)\equiv{\mathsf{E}}_1\bigl[s^{Z_1}\bigr]\) are related via 5 \(\widehat\varphi(s)=\frac1\rho\varphi(\rho s)\), \(0\le s\le1\).
If the offspring distribution of \((Z_n)_{n\ge0}\) is \({\mathsf{Poi}}(\lambda)\) with \(\lambda>1\), use the fixed point equation \(\rho=e^{\lambda(\rho-1)}\) to show that \(\widehat\varphi(s)=e^{\lambda\rho(s-1)}\), ie., that the offspring distribution for \((\widehat{Z}_n)_{n\ge0}\) is just \({\mathsf{Poi}}(\lambda\rho)\).
Let \((Z_n)_{n\ge0}\) be a supercritical branching process with offspring distribution \(\{p_k\}_{k\ge0}\), offspring generating function \(\varphi(s)\) and extinction probability \(\rho\in[0,1)\).
If \(Z_0=1\), let \(\tilde p_k\) be the probability that conditioned on survival the first generation has exactly \(k\) individuals with an infinite line of descent. Show that \[\tilde p_k=\frac1{1-\rho}\sum_{n=k}^\infty p_n\binom{n}{k}(1-\rho)^k\rho^{n-k}\,.\]
Let \((\widetilde{Z}_n)_{n\ge0}\) count only those individuals in \((Z_n)_{n\ge0}\), who conditioned on survival have an infinite line of descent. Show that \((\widetilde{Z}_n)_{n\ge0}\) is a branching process with offspring generating function [rescaled-generating-function] \[\widetilde\varphi(s)=\frac1{1-\rho}\Bigl(\varphi\bigl((1-\rho)s+\rho\bigr)-\rho\Bigr)\,.\]
Let \((Z_n)_{n\ge0}\) be a subcritical branching process whose generating function \(\varphi(s)={\mathsf{E}}(s^{Z_1})\) is finite for some \(s>1\), ie., the offspring distribution has finite exponential moments in a neighbourhood of the origin.
Using the result of Exercise [exse:branching-process-total-population-size-generating-function] or otherwise, show that the total population size \(\bar{Z}=\sum_{k\ge0}Z_k\) satisfies \({\mathsf{E}}\bigl(u^{\bar{Z}}\bigr)<\infty\) for some \(u>1\).
Suppose that for each \(1\le i\le\bar{Z}\), individual \(i\) produces wealth of size \(W_i\), where \(W_i\) are independent random variables with common distribution satisfying \({\mathsf{E}}\bigl(s^W\bigr)<\infty\) for some \(s>1\). Show that for some \(u>1\) we have \({\mathsf{E}}\bigl(u^{\overline{W}}\bigr)<\infty\), where \(\overline{W}=W_1+\dots+W_{\bar{Z}}\) is the total wealth generated by \((Z_n)_{n\ge0}\).
The following example is one of very few for which the computation in the critical case \(m={\mathsf{E}}(Z_1) =1\) can be done explicitly.
Consider the so-called linear-fractional case, where the offspring distribution is given by \(p_j=2^{-(j+1)}\), \(j\ge0\). Then the offspring generating function is \(\varphi(s)=\sum_{j\ge0}s^j/2^{j+1}=(2-s)^{-1}\) and a straightforward induction gives (check this!) \[\varphi_k(s)=\frac{k-(k-1)s}{(k+1)-ks} =\frac{k}{k+1}+\frac{1}{k(k+1)}\sum_{m\ge1}\Bigl(\frac{ks}{k+1}\Bigr)^m\,,\] so that \({\mathsf{P}}(Z_k=0)=\varphi_k(0)=k/(k+1)\), \({\mathsf{P}}(Z_k>0)=1/(k+1)\), and \[{\mathsf{P}}\bigl(Z_k=m\mid Z_k>0\bigr)=\frac{1}{k+1}\,\Bigl(\frac{k}{k+1}\Bigr)^{m-1}\,,\qquad m\ge1\,,\] ie., \((Z_k\mid Z_k>0\bigr)\) has geometric distribution with success probability \(1/(k+1)\).
For each \(k\ge 0\), by the partition theorem, \[1={\mathsf{E}}(Z_k)={\mathsf{E}}\bigl(Z_k\mid Z_k>0\bigr)\,{\mathsf{P}}(Z_k>0)+{\mathsf{E}}\bigl(Z_k\mid Z_k=0\bigr)\,{\mathsf{P}}(Z_k=0)\,,\] so that in the previous example we have \[{\mathsf{E}}\bigl(Z_k\mid Z_k>0\bigr)=\frac{1}{{\mathsf{P}}(Z_k>0)}=k+1\,,\] ie., conditional on survival, the average generation size grows linearly with time.
The following example is known as the general linear-fractional case:
For fixed \(b>0\) and \(p\in(0,1)\), consider a branching process with offspring distribution \(p_j=b\,p^{j-1}\), \(j\ge1\), and \(p_0=1-\sum_{j\ge1}p_j\).
Show that for \(b\in(0,1-p)\) the distribution above is well defined; find the corresponding \(p_0\), and show that \[\varphi(s)=\frac{1-b-p}{1-p}+\frac{bs}{1-ps}\,;\]
Find \(b\) for which the branching process is critical and show that then \[\varphi_k(s)={\mathsf{E}}\bigl(s^{Z_k}\bigr)=\frac{kp-(kp+p-1)s}{(1-p+kp)-kps}\,;\]
Deduce that \((Z_k\mid Z_k>0\bigr)\) is geometrically distributed with parameter \(\frac{1-p}{kp+1-p}\).
Straightforward computer experiments show that a similar linear growth of \({\mathsf{E}}\bigl(Z_k\mid Z_k>0\bigr)\) takes place for other critical offspring distributions, eg., the one with \(\varphi(s)=(1+s^2)/2\).
If the offspring distribution of the branching process \((Z_k)_{k\ge0}\) has mean \(m=1\) and finite variance \(\sigma^2>0\), then \(k\,{\mathsf{P}}(Z_k>0)\to\frac{2}{\sigma^2}\) as \(k\to\infty\); equivalently, \[\begin{equation} \label{eq:critical-branching-expectation} \frac1k\,{\mathsf{E}}(Z_k\mid Z_k>0\bigr)\to\frac{\sigma^2}2\quad\text{ as $k\to\infty$.} \end{equation}\]
This general result suggests that, conditional on survival, a general critical branching process exhibits linear intermittent behaviour; 6 namely, with small probability (of order \(2/(k\sigma^2)\)) the values of \(Z_k\) are of order \(k\).
Our argument is based on the following general fact: 7
Let \((y_n)_{n\ge0}\) be a real-valued sequence. If for some constant \(a\) we have \(y_{n+1}-y_n\to a\) as \(n\to\infty\), then \(n^{-1}y_n\to a\) as \(n\to\infty\).
By changing the variables \(y_n\mapsto y'_n=y_n-na\) if necessary, we can and shall assume that \(a=0\). Fix arbitrary \(\delta>0\) and find \(K>0\) such that for \(n\ge K\) we have \(|y_{n+1}-y_n|\le\delta\). Decomposing, for \(n>K\),
\(y_n-y_K=\sum\limits_{j=K}^{n-1}\bigl(y_{j+1}-y_j\bigr)\) we deduce that \(|y_n-y_K|\le\delta(n-K)\) so that the claim follows from the estimate \[\Bigl|\frac{y_n}{n}\Bigr|\le\Bigl|\frac{y_n-y_K}{n}\Bigr|+\Bigl|\frac{y_K}{n}\Bigr|\le\delta+\Bigl|\frac{y_K}{n}\Bigr|\le2\delta\,,\] provided \(n\) is chosen sufficiently large.
(of Theorem [thm:critical-branching]). We only derive the second claim of the theorem, ([eq:critical-branching-expectation]). By assumptions and Taylor’s theorem (here we are also using Theorem [thm:moments-from-generating-functions]) the offspring generating function \(\varphi\) satisfies \[1-\varphi(s)=(1-s)+\frac{\sigma^2}{2}(1-s)^2+R(s)(1-s)^2 \text{ where } R(s)\to 0 \text{ as } s\uparrow 1.\] Since \(\varphi_n(0)={\mathsf{P}}(Z_n=0)\to 1\) as \(n\to \infty\) this means in particular that \(1-\varphi_{n+1}(0)=1-\varphi(\varphi_n(0))=1-\varphi_n(0)+(1-\varphi_n(0))^2(\frac{\sigma^2}{2}+r_n))\) with \(r_n:=R(\varphi_n(0))\to 0\) as \(n\to \infty\). Setting \[y_n=\frac{1}{1-\varphi_n(0)} =\frac{{\mathsf{E}}(Z_n)}{{\mathsf{P}}(Z_n>0)}={\mathsf{E}}(Z_n|Z_n>0)\] we therefore have \[y_{n+1}-y_n = \frac{1}{1-\varphi_n(0)}\frac{1}{1-(1-\varphi_n(0))(\sigma^2/2+r_n)}-1\] which we can rewrite as \[\frac{(1-\varphi_n(0))(\sigma^2/2+r_n)}{1-\varphi_n(0)}\frac{1}{1-(1-\varphi_n(0))(\sigma^2/2+r_n)}\] for each \(n\). It therefore follows that \(y_{n+1}-y_n\to \sigma^2/2\) as \(n\to \infty\) and hence \[\frac{y_n}{n}=\frac{{\mathsf{E}}(Z_n|Z_n>0)}{n}\to \frac{\sigma^2}{2}\] as well (by the Lemma). This completes the proof.
With a bit of extra work 8 one can generalize the above proof to show that \[\lim\limits_{n\to\infty}n^{-1}\Bigl(\frac{1}{1-\varphi_n(s)}-\frac{1}{1-s}\Bigr)=\frac{\sigma^2}{2}\] for any \(s\in [0,1]\) and use this relation to derive the convergence in distribution:
If \({\mathsf{E}}Z_1=1\) and \({\mathsf{Var}}(Z_1)=\sigma^2\in(0,\infty)\), then for every \(z\ge0\) we have \[\lim_{k\to\infty}{\mathsf{P}}\Bigl(\frac{Z_k}{k}>z\mid Z_k>0\Bigr)=\exp\Bigl\{-\frac{2z}{\sigma^2}\Bigr\}\,,\] ie., the distribution of \(\bigl(k^{-1}Z_k\mid Z_k>0\bigr)\) is approximately exponential with parameter \(2/\sigma^2\).
In the setup of Example [exmle:linear-fractional-branching-process], we have \[{\mathsf{P}}\bigl(Z_k>m\mid Z_k>0\bigr)=\Bigl(\frac{k}{k+1}\Bigr)^m=\Bigl(1-\frac1{k+1}\Bigr)^m\,,\] so that \({\mathsf{P}}\bigl(Z_k>kz\mid Z_k>0\bigr)\to e^{-z}\) as \(k\to\infty\); in other words, for large \(k\) the distribution of \(\bigl(k^{-1}Z_k\mid Z_k>0\bigr)\) is approximately \({\mathsf{Exp}}(1)\).
Let \((Z_n)_{n\ge0}\) be the critical branching process from Exercise [exse:general-linear-fractional-branching-process], namely, the one whose offspring distribution is given by \((p_j)_{j\ge0}\), \[p_j=b\,p^{j-1}\,,\quad j\ge1\,,\qquad p_0=1-\sum_{j\ge1}p_j\,,\] where \(b>0\) and \(p\in(0,1)\) are fixed parameters. Show that the result of Theorem [thm:critical-branching-limit-distribution] holds: for every \(z\ge0\) \[\lim_{k\to\infty}{\mathsf{P}}\Bigl(\frac{Z_k}{k}>z\mid Z_k>0\Bigr)=\exp\Bigl\{-\frac{2z}{\sigma^2}\Bigr\}\,,\] where \({\mathsf{Var}}(Z_1)=\sigma^2\in(0,\infty)\).
If the offspring distribution changes with time, the previous approach must be modified. Let \(\psi_n(u)\) be the generating function of the offspring distribution of a single ancestor in the \((n-1)\)st generation, \[\psi_n(u)={\mathsf{E}}\bigl(u^{Z_n}\mid Z_{n-1}=1\bigr)\,\] (so in the cases considered up to now, \(\psi_n=\varphi\) for every \(n\)). Then the generating function \(\varphi_n(u)={\mathsf{E}}\bigl(u^{Z_n}\mid Z_0=1\bigr)\) of the population size at time \(n\) given a single ancestor at time \(0\), can be defined recursively as follows: \[\varphi_0(u)\equiv u\,,\qquad \varphi_n(u)=\varphi_{n-1}\bigl(\psi_n(u)\bigr)\,,\quad \forall n\ge1\,.\] If \(\mu_n={\mathsf{E}}(Z_n\mid Z_{n-1}=1)=\psi'_n(1)\) denotes the average offspring size in the \(n\)th generation given a single ancestor in the previous generation, then \[m_n\equiv{\mathsf{E}}\bigl(Z_n\mid Z_0=1\bigr)=\mu_1\mu_2\ldots\mu_{n-1}\mu_n\,.\] It is natural to call the process \((Z_n)_{n\ge0}\) supercritical if \(m_n\to\infty\) and subcritical if \(m_n\to0\) as \(n\to\infty\).
A strain of phototrophic bacteria uses light as the main source of energy. As a result individual organisms reproduce with probability mass function \(p_0=1/4\), \(p_1=1/4\) and \(p_2=1/2\) per unit of time in light environment, and with probability mass function \(p_0=1-p\), \(p_1=p\) (with some \(p>0\)) per unit of time in dark environment. A colony of such bacteria is grown in a laboratory, with alternating light and dark unit time intervals.
a) Model this experiment as a time non-homogeneous branching process \((Z_n)_{n\ge0}\) and describe the generating function of the population size at the end of the \(n\)th interval.
b) Characterise all values of \(p\) for which the branching process \(Z_n\) is subcritical and for which it is supercritical.
c) Let \((D_k)_{k\ge0}\) be the original process observed at the end of each even interval, \(D_k\stackrel{{\sf def}}{=}Z_{2k}\). Find the generating function of \((D_k)_{k\ge0}\) and derive the condition for sure extinction. Compare your result with that of part b).
current version by Ellen Powell (ellen.g.powell@durham.ac.uk); based on previous notes by Nicholas Georgiou and Ostap Hyrniv↩︎
sometimes called a Galton-Watson-Bienaymé process↩︎
If \(Z_0=k\), we shall explicitly write \({\mathsf{P}}_k(\,\cdot\,)\) and \({\mathsf{E}}_k(\,\cdot\,)\).↩︎
otherwise the model is degenerate: if \(p_0=0\), then \(Z_n\ge1\) for all \(n\ge0\) so that \(\rho=0\); if \(p_0=1\), then \({\mathsf{P}}(Z_1=0)=\rho=1\).↩︎
[rescaled-generating-function] Geometrically, the graph of this generating function is a rescaled version of that of \(\varphi(\cdot)\).↩︎
Intermittency follows from the criticality condition, \(1={\mathsf{E}}(Z_k\mid Z_k>0\bigr){\mathsf{P}}(Z_k>0)\); it is the linearity which is surprising here!↩︎
Compare the result to Cesàro limits of real sequences: if \((a_k)_{k\ge1}\) is a real-valued sequence, and \(s_n=a_1+\dots+a_n\) is its \(n\)th partial sum, then \(\frac1ns_n\) are called the Cesàro averages for the sequence \((a_k)_{k\ge1}\). Lemma [lem:cesaro-limit] claims that if \(a_k\to a\) as \(k\to\infty\), then the sequence of its Cesàro averages also converges to \(a\). The converse is, of course, false. (Find a counterexample!)↩︎
using the fact that every \(s\in(0,1)\) satisfies \(0<s<\varphi_k(0)<1\) for some \(k\ge1\);↩︎