21 Branching Process

#ExtinctionProbability #PGF #BranchingProcess #MarkovInequality

Random Process

A random process is a family ${X_{t}, t \in T}$ of RVs indexed by some set $T$ , i.e. $X_{t} : Ω \to S$ .
$S$ is called state space.

$X_{t}$ "evolves" as time passes in a random but prescribed way.

1 GaHon-Watson Branching Process

This model has historical context in family name propagation (Galton, 1889) and free neutrons in nuclear fission reactions (1930's). Denote $T = N$ , $S = N_{0}$ , $X_{t}$ is number of particles at time $t$ .
Pasted image 20241127000405.png|300
Each particle gives birth to $k \in N_{0}$ children with probability $p_{k}$ , independently of other particles in the past and present.

Assumptions

There is no single $k \in N$ s.t. $p_{k} = 1$ .

$p_{k} > 0$ for some $k \geq 2$ .

$μ > 0, σ^{2} > 0$ , both finite.

Let $F = {p_{k} | k \in N_{0}}$ denote the offspring number distribution with mean $μ < \infty$ , and variance $σ^{2} < \infty$ .
Denote $B_{i}^{(t)}$ as the children generated by $i$ th node at time $t$ . So $B_{1}^{(t)}, \dots, B_{X_{t}}^{(t)} \overset{i . i . d}{\sim} F$ and are independent from $X_{t}$ . So $X_{t + 1} = B_{1}^{(t)} + \dots + B_{X_{t}}^{(t)}$ , $P (B_{i}^{(t)} = k) = p_{k}$ .

By Wald's Identity, $E (X_{t}) = μ E (X_{t - 1}) = μ (μ E (X_{t - 2})) = \dots = μ^{t} E (X_{0}) .$
Typically $X_{0} = 1$ . So $E (X_{t})$ increases geometrically if $μ > 1$ (supercritical); decreases geometrically if $μ < 1$ (subcritical); remains constant if $μ = 1$ (critical).
By Law of Total Variance, $\begin{aligned} Var (X_{t}) & = σ^{2} E (X_{t - 1}) + μ^{2} Var (X_{t - 1}) \\ = σ^{2} μ^{t - 1} + μ^{2} (σ^{2} μ^{t - 2} + μ^{2} Var (X_{t - 2})) \\ = σ^{2} (μ^{t - 1} + μ^{t} + \dots + μ^{2 t - 2}) \\ = {\begin{aligned} σ^{2} t, μ = 1, \\ σ^{2} μ^{t - 1} (\frac{1 - μ^{t}}{1 - μ}), μ \neq 1. \end{aligned} \end{aligned}$
The figure may look like:

Pasted image 20241127004828.png|300
For all GW processes, the state $0$ is the absorbing state. ( $X_{t} = 0 \Rightarrow X_{t + 1} = 0$ .)

2 Extinction Probability

Definition

Extinction Time $τ = min {t \in N | X_{t} = 0}$ ; $τ = \infty$ if there exists no such $t$ .
Extinction Probability $P (τ < \infty)$ .

Claim

$P (τ > t) \leq μ^{t} .$

Hence if $μ < 1$ , the extinction occurs with probability $1$ .

Proof

By Markov's inequality,

P (τ > t) = P (X_{t} \geq 1) \leq E [X_{t}] = μ^{t} .

Key tool for computing the extinction probability is the PGF.
Consider a Galton-Watson process ${X_{t}, t \in N_{0}}$ with offspring number distribution $F = {p_{k} | k \in N_{0}}$ . For $B \sim F$ , define $φ (s) = E [s^{B}] = \sum_{k = 0}^{\infty} s^{k} p_{k} .$

Then $φ$ is non-linear.

$φ (0) = p_{0}, φ (1) = 1$ .
$φ (s)$ is strictly increasing for $s \in (0, 1)$ .
$φ (s)$ is strictly convex.

Claim

Let $φ_{t} (s) = E (s^{X_{t}}) = \sum_{k = 0}^{\infty} s^{k} P (X_{t} = k)$ (PGF for $X_{t}$ .) Then $φ_{t + 1} (s) = φ (φ_{t} (s)) = φ_{t} (φ (s)), \forall t \in N_{0} .$
If $X_{0} = 1$ , then this implies that $φ_{t} (s)$ is the $t -$ fold composition of $φ$ , i.e. $φ_{t} (s) = \underset{t times}{\underset{⏟}{φ (φ (\dots (φ (s)) \dots))}} .$

Proof

First, note that $X_{t + 1} \overset{d}{=} X_{t}^{(1)} + \dots + X_{t}^{(X_{1})},$ then $φ_{t + 1} (s) = E [(φ_{t} (s))^{X_{1}}] = φ (φ_{t} (s)) .$
This is PGF for $X_{1}$ with variable $φ_{t} (s)$ .
Furthermore, $\begin{aligned} φ_{t + 1} (s) = E [s^{X_{t + 1}}] & = \sum_{k = 0}^{\infty} E [s^{X_{t + 1}} | X_{t} = k] P (X_{t} = k) \\ = \sum_{k = 0}^{\infty} [φ (s)]^{k} P (X_{t} = k) = φ_{t} (φ (s)) . \end{aligned}$
This is PGF for $X_{t}$ with variable $φ (s)$ .

Claim

Let $e_{t} = P (X_{t} = 0)$ be the probability of extinction by time $t$ . Then $e_{t} = φ (e_{t - 1}) .$

When $e_{0} = 0, e_{t} = φ_{t} (0)$ , extinction probability is $lim_{t \to \infty} φ_{t} (0)$ .

Proof

$\begin{aligned} e_{t} & = \sum_{k = 0}^{\infty} P (X_{t - 1}^{(1)} = 0, \dots, X_{t - 1}^{(X_{1})} = 0 | X_{1} = k) P (X_{1} = k) \\ = \sum_{k = 0}^{\infty} (e_{t - 1})^{k} p_{k} = φ (e_{t - 1}) . \end{aligned}$

Pasted image 20241127011300.png|400
Pasted image 20241127011404.png|400

Claim

The probability of extinction $ξ = P (τ < \infty)$ is the smallest non-negative solution of the fixed point equation $\begin{matrix} (1) & s = φ (s) . \end{matrix}$

Proof

$ξ$ is solution. Since $ξ = p_{0} + \sum_{k = 1}^{\infty} ξ^{k} p_{k} = φ (ξ),$ then $ξ$ satisfies (1).
$ξ$ is non-negative. Note that $P (X_{t} = 0) = φ_{t} (0) \leq 1$ , and $(X_{t} = 0) \subset (X_{t + 1} = 0)$ , then $φ_{t} (0) \leq φ_{t + 1} (0)$ , so $lim_{t \to \infty} φ_{t} (0)$ exists and is equal to $ξ$ .
$ξ$ is smallest. Suppose $s \geq 0$ satisfies (1). Then $φ_{t} (s) = s, \forall t \in N$ . By monotonicity of $φ_{t}$ , $φ_{t} (0) \leq φ_{t} (s) = s$ . Take the limit of each side as $t \to \infty$ , we have $ξ \leq s$ , so $ξ$ is the smallest non-negative solution.

Theorem

Unless $p_{k} = 1$ , the fixed-point equation (1) has either one or two solutions.

Supercritical ( $μ > 1$ ) case has a unique solution $ξ$ less than $1$ .
Critical ( $μ = 1$ ) and subcritical ( $μ < 1$ ) cases have only one solution $ξ = 1$ .

Theorem

Suppose ${X_{t} | t \in N_{0}}$ is a Galton-Watson process with offspring number distribution $F = {p_{k} | k \in N_{0}}$ .

(Geometrically decaying tail) If $μ < 1$ , then $P (τ > t) \sim c_{F} μ^{t}$ as $t \to \infty$ , where $c_{F} \in (0, \infty)$ is a constant that depends on $F$ .
(Fat tail) If $μ = 1$ , then $P (τ > t) \sim \frac{2}{σ^{2} t}$ as $t \to \infty$ . Then $E [τ]$ is finite.