Galton–Watson 分枝过程

形式陈述

设每个个体产生的下一代数量为非负整数随机变量 $\xi$ ，满足

\Pr(\xi=k)=p_k,\qquad k=0,1,\ldots,\qquad \sum_{k\ge0}p_k=1.

这允许无界的繁殖数，但每个繁殖数有限几乎必然。准备一族相互独立、同分布于 $\xi$ 的随机变量 $\xi_{n,i}$ ，其中 $n\ge0,i\ge1$ 。固定初始祖先数 $Z_0=r\in\mathbb N_0$ ，递推

Z_{n+1}=\sum_{i=1}^{Z_n}\xi_{n,i}, \tag{1}

空和为零。这个随机过程称为单类型 Galton–Watson 分枝过程。 $n$ 是代数； $Z_n$ 只数第 $n$ 代，不累计已经过去的各代，也不描述个体在连续时间里活多久。

零态吸收： $Z_n=0$ 后所有未来代均为零。令 $\mathcal E=\{\exists n:Z_n=0\}$ 为最终灭绝事件，先从一个祖先出发，记 $q=\Pr_1(\mathcal E)$ 。定义繁殖分布的概率生成函数

f(s)=\mathbb E s^\xi=\sum_{k\ge0}p_ks^k,\qquad 0\le s\le1, \tag{2}

其中 $0^0=1$ 。这是系数非负且总和为一的普通生成函数；在这里还可合法数值代入 $[0,1]$ ，不是只作形式运算。

写 $f^{\circ n}$ 为 $n$ 次复合， $f^{\circ0}(s)=s$ 。则

\mathbb E_r s^{Z_n}=[f^{\circ n}(s)]^r, \qquad q=\lim_{n\to\infty}f^{\circ n}(0) =\min\{s\in[0,1]:f(s)=s\}. \tag{3}

$r=0$ 时过程已经灭绝，生成函数与灭绝概率都为一；式(3)的零次幂按此解释。一般 $r$ 的最终灭绝概率为 $q^r$ 。

繁殖均值 $m=\mathbb E\xi\in[0,\infty]$ 决定阈值，但有一个必须保留的退化情形：

若 $p_1=1$ ，每条家系永远只有一个个体， $q=0$ ，尽管 $m=1$ 。
若 $p_1\ne1$ ，则 $m\le1$ 时 $q=1$ ； $m>1$ （允许 $m=\infty$ ）时 $q<1$ 。
若 $p_0=0$ ，没有个体会断后，所以 $q=0$ ；若 $p_0>0$ 且 $m>1$ ，则 $0<q<1$ 。

这些结论要求式(1)中的全部个体繁殖独立，且繁殖分布不随代数或当前人数改变。

直觉

一个祖先的孩子们开启彼此独立、规律相同的子家系。若它恰有 $k$ 个孩子，最终灭绝要求这 $k$ 个子家系全部灭绝，概率为 $q^k$ 。平均后得到 $q=f(q)$ 。不过 $f(1)=1$ 永远成立，单写不动点方程还不知道应选哪一个根；从“零代时尚未灭绝”的概率零反复更新，才选出最小根。

同一想法还能读出整代分布。给定第 $n$ 代有 $i$ 个个体，下一代是 $i$ 份独立繁殖数之和；概率生成函数相乘，得到 $f(s)^i$ 。再平均当前人数，生成函数的乘法便变成复合。

均值 $m^n$ 是跨重复家系实验的平均。它可以持续增加，同时有一部分家系很早灭绝；平均增长不是每条样本路径的确定增长率。进一步识别存活路径的增长，需要归一化鞅的矩条件。

例子与边界

一份可以逐代复算的二叉家系

取 $p_0=1/4,p_2=3/4$ ，其余为零。则

f(s)=\frac14+\frac34s^2,\qquad m=\frac32, \qquad f(s)-s=\frac14(3s-1)(s-1).

最小根为 $q=1/3$ 。从一个祖先出发，第一代灭绝概率为 $1/4$ ；到第二代已灭绝的概率为

f(f(0))=\frac14+\frac34\left(\frac14\right)^2=\frac{19}{64}.

第二代分布可以直接列出：

$Z_2$	$0$	$2$	$4$
概率	$19/64$	$18/64$	$27/64$

例如 $Z_2=2$ 要求第一代确有两个孩子，随后恰有一个孩子繁殖为二，概率为 $(3/4)\,2(1/4)(3/4)=18/64$ 。表中均值为 $9/4=m^2$ 。两个初始祖先的家系独立，第二代均值为 $9/2$ ，最终共同灭绝概率为 $1/9$ ，不是 $1/3$ 。

同样的个体边缘分布，换成共同环境

现在每代只抽一次 $A_n$ ，其取值零、二的概率仍为 $1/4,3/4$ ，不同代的 $A_n$ 独立；令该代所有个体都产生 $A_n$ 个孩子。于是

\widehat Z_{n+1}=A_n\widehat Z_n, \qquad \Pr(\widehat Z_n>0)=\left(\frac34\right)^n \longrightarrow0.

从一个祖先出发，存活到第 $n$ 代时人数恰为 $2^n$ ，故均值仍为 $(3/2)^n$ ，但最终灭绝概率为一。这里同代个体的繁殖完全相关，不能使用 $f(s)^{Z_n}$ 。这不是式(3)的例外，而是模型输入已经改变。

两个祖先下蓝色独立家系与红色共同环境的有限代灭绝概率，以及归一化人数二阶矩；右图为对数纵轴，显示的是二阶矩而非方差 — 独立性改变灭绝概率与平方预算

临界情形不能省掉退化检查

若 $p_0=p_2=1/2$ ，则 $m=1$ ，不动点方程只有 $s=1$ ，家系几乎必然灭绝。若改成 $p_1=1$ ，同样有 $m=1$ ，但 $Z_n=r$ 恒定。繁殖均值相同，并不足以把这两个模型归为同一存活结论。

本模型也不同于连续时间生灭过程：生灭过程在实时间里逐次加一或减一，本页在一代结束时让全部个体同时被其后代替换。若有外部个体不断进入，应写明移入项；此时零态一般不再吸收，不能把“曾到零”当成永久灭绝。

推论与应用

从独立子家系到最小不动点

给定当前人数 $i$ ，下一代分布为 $p$ 的 $i$ 重卷积；当 $i=0$ 时为零点质量。未来繁殖数组独立于已经观察的历史，所以这个转移核只依赖当前人数，且不依赖代数。这证明本模型确实是可数状态、时间齐次的Markov 链。

从一祖先出发，令 $F_n(s)=\mathbb E s^{Z_n}$ 。条件计算给出

F_{n+1}(s)=\mathbb E[f(s)^{Z_n}]=F_n(f(s)),\qquad F_0(s)=s,

因此 $F_n=f^{\circ n}$ 。初始 $r$ 个祖先使用互不相交的繁殖数组，家系相互独立，所以总人数的生成函数是 $F_n^r$ 。

令 $a_n=F_n(0)=\Pr_1(Z_n=0)$ 。零态吸收说明事件 $\{Z_n=0\}$ 递增，故 $a_n\uparrow q$ 。级数(2)在 $[0,1]$ 连续：尾部对所有 $s$ 都不超过相应的概率尾和。于是 $a_{n+1}=f(a_n)$ 传极限给出 $f(q)=q$ 。任何其他不动点 $b\in[0,1]$ 都满足 $a_0=0\le b$ ；由 $f$ 单调，归纳得 $a_n\le b$ ，从而 $q\le b$ 。

为什么阈值是均值一

先处理 $p_0=0$ ：每个个体至少产生一个孩子，直接得到 $q=0$ 。若再有 $m\le1$ ，必有 $\xi=1$ 几乎必然，正是前述退化情形。

以下设 $p_0>0$ 。若没有大于一的繁殖数， $f(s)=p_0+p_1s$ 且 $p_1<1$ ，唯一不动点就是一。否则至少某个 $p_k>0,k\ge2$ ， $f$ 严格凸；在 $0\le s<1$ 上，

f'(s)=\sum_{k\ge1}k p_ks^{k-1},\qquad f'(1-)=m.

当 $m\le1$ ，对 $s<1$ 有 $f'(s)<1$ ，故 $f(s)-s$ 从正值严格递减到零，不能提前穿零。当 $m>1$ ，存在 $s_0<1$ 使 $f'(s_0)>1$ ，即使 $m=\infty$ 也成立。对 $s\in(s_0,1)$ ，积分得 $f(s)-s<0$ 。但 $f(0)>0$ ，故在 $(0,1)$ 有一个根；严格凸性不允许连同一再出现第三个根。因此该根唯一，且是 $q$ 。割线从 $q$ 到一的斜率为一，严格凸性还给出 $f'(q)<1$ 。

均值、方差与所需成本

当 $m<\infty$ ，对历史条件化后调用全期望公式，

\mathbb E[Z_{n+1}\mid\mathcal F_n]=mZ_n, \qquad \mathbb E_rZ_n=r m^n.

若繁殖方差 $\sigma^2<\infty$ ，同一工具的全方差公式给出

\operatorname{Var}_rZ_{n+1} =\sigma^2\mathbb E_rZ_n+m^2\operatorname{Var}_rZ_n. \tag{4}

其首项为零。对 $m>0,n\ge1$ ，解递推得

\operatorname{Var}_rZ_n= \begin{cases} r\sigma^2m^{n-1}(m^n-1)/(m-1),&m\ne1,\\ r n\sigma^2,&m=1. \end{cases}

$m=0$ 时繁殖恒零，第一代起人数和方差均为零，不需代入负幂式。

若繁殖支持为 $\{0,\ldots,d\}$ ，用Horner法算一次 $f(a)$ 需要 $O(d+1)$ 次算术操作；求到第 $N$ 代灭绝概率需要 $O(N(d+1))$ 时间，除输入系数外只需常数个状态。系数为有理数时可以精确迭代，但上述是算术操作计数，不是忽略分子分母增长后的位复杂度。

直接迭代得到的是 $q$ 的下界，不能把相邻两次差自动当作误差上界。若另外找到 $b<1$ 满足 $f(b)\le b$ ，且已认证 $\rho=f'(b)<1$ ，则 $q\le b$ ，在 $[0,b]$ 上的导数不超过 $\rho$ 。由中值估计，

0\le q-a_n\le \frac{f(a_n)-a_n}{1-\rho}. \tag{5}

二叉例子可取 $b=1/2,\rho=3/4$ 。相反，临界 $f(s)=(1+s^2)/2$ 满足 $f(a)-a=(1-a)^2/2$ ，真实误差 $1-a$ 是相邻差的平方根量级；只看迭代增量很小，会过早宣称精确。

如果按式(1)逐个模拟到第 $N$ 代，繁殖抽样次数恰为 $\sum_{n=0}^{N-1}Z_n$ ，不是固定 $N$ 次。假设单次繁殖抽样常数成本，期望次数为 $r\sum_{n=0}^{N-1}m^n$ 。累计整个家系的工作量则由总后代数控制；终点会把有限代概率、最终灭绝概率和累计规模分别复算。

参考资料

Hao Wu，MIT 18.445, Lecture 19: Galton–Watson tree，2015-04-27，幻灯片3–7，独立繁殖、灭绝不动点和归一化过程。
The simple Galton–Watson process: Classical approach, Chapter 1，Münster大学2010–2011课程材料，§§1.1–1.4，印页3–10，转移卷积、矩与最小不动点。

形式陈述 ​

一份可以逐代复算的二叉家系 ​

同样的个体边缘分布，换成共同环境 ​

临界情形不能省掉退化检查 ​

从独立子家系到最小不动点 ​

为什么阈值是均值一 ​

均值、方差与所需成本 ​

反向链接