分枝过程的总后代分布

形式陈述

设 $(Z_n)$ 为Galton–Watson分枝过程，繁殖概率为 $p_k$ ，生成函数为 $f(s)=\sum p_ks^k$ ，单祖先灭绝概率为 $q$ 。从固定 $r\ge1$ 个祖先出发，定义总后代数

T=\sum_{n=0}^{\infty}Z_n\in\{r,r+1,\ldots\}\cup\{\infty\}. \tag{1}

本页的“总后代”包含最初的 $r$ 个祖先。若只想计祖先之后的个体，应使用 $T-r$ ，不能不改下标便套下面的公式。

每代人数有限，而且没有移入，所以 $T<\infty$ 当且仅当家系最终灭绝。记

H(s)=\mathbb E_1[s^T\mathbf1_{\{T<\infty\}}] =\sum_{n\ge1}\Pr_1(T=n)s^n,\qquad 0\le s\le1.

这里直接按有限总数的概率求和，不对 $1^\infty$ 作约定。 $H$ 满足

H(s)=s f(H(s)),\qquad H(0)=0,\qquad H(1)=q. \tag{2}

从 $r$ 个祖先出发，有限总数的生成函数为 $H(s)^r$ 。对每个整数 $n\ge r$ ，有 Lagrange–Dwass 公式

\boxed{ \Pr_r(T=n)=\frac rn[u^{n-r}]f(u)^n =\frac rn\Pr(\xi_1+\cdots+\xi_n=n-r), } \tag{3}

其中 $\xi_i$ 独立同分布于繁殖数。 $n<r$ 时概率为零。有限质量的总和为 $q^r$ ，超临界时不能把它当成已归一化的条件分布。

若 $m=\mathbb E\xi<1$ ，则

\mathbb E_rT=\frac r{1-m}. \tag{4}

若还满足 $\sigma^2=\operatorname{Var}\xi<\infty$ ，则

\operatorname{Var}_rT=\frac{r\sigma^2}{(1-m)^3}. \tag{5}

另一个有用的合同是条件灭绝：若 $q>0$ ，给定整个家系最终灭绝后，过程仍是同一初始祖先数的分枝过程，但繁殖概率变为

\widetilde p_k=p_k q^{k-1},\qquad \widetilde f(s)=\frac{f(qs)}q. \tag{6}

当 $0<q<1$ ，新均值为 $f'(q)<1$ ，于是条件下的累计规模可用式(4)–(5)计算。 $q=0$ 时条件事件概率为零，式(6)没有这里所说的条件概率含义。

直觉

总数满足一个递归分解：先数祖先自己的一，再加上每个孩子的整个子家系。生成函数中的前因子 $s$ 正是祖先占用的一个计数单位；漏掉它会把每个规模都错移。

在式(3)右侧， $n$ 个已经处理的个体一共要产生 $n-r$ 个孩子，才与由 $r$ 个根组成、总顶点数为 $n$ 的森林相容。不过这个总量条件还未说明按探索顺序能否构成森林，因而概率前面还要乘 $r/n$ 。下面用已有的形式反演完整推导这个系数，不把它解释成没有证明的独立概率。

条件灭绝会重新加权每一种繁殖数。孩子越多，要求全部子家系都灭绝越困难，所以原概率 $p_k$ 被乘上 $q^k$ ，再除以祖先家系灭绝的概率 $q$ 。这改变的是整个家系的条件分布，不是把某次观察到的小家系随意当成原繁殖总体。

例子与边界

二叉家系的奇偶支持

令 $p_0=a,p_2=b=1-a$ ，且 $a,b>0$ 。一祖先的有限总数只能为奇数 $2j+1$ 。由式(3)，

\Pr_1(T=2j+1) =\frac1{2j+1}\binom{2j+1}{j}a^{j+1}b^j =\frac1{j+1}\binom{2j}{j}a^{j+1}b^j.

最后的整数系数正是二叉有序树的Catalan计数；每棵树有 $j$ 个产生两个孩子的内部点和 $j+1$ 个不繁殖的叶子。

取 $a=1/4,b=3/4$ ，最初三个有限质量为

\Pr(T=1)=\frac14, \qquad \Pr(T=3)=\frac3{64}, \qquad \Pr(T=5)=\frac9{512}.

全部有限质量只和到 $q=1/3$ ，余下 $2/3$ 在 $T=\infty$ 。条件于最终灭绝，新的繁殖概率是

\widetilde p_0=\frac34,\qquad \widetilde p_2=\frac14, \qquad \widetilde m=\frac12,\qquad \widetilde\sigma^2=\frac34.

故一祖先的条件总规模均值为二、方差为六。原过程的无条件总数均值为无穷，因为有正概率无限；不能把条件均值二报告成原家系的平均总数。

Poisson繁殖与全体总数

若繁殖数服从参数 $\lambda>0$ 的Poisson分布，则 $f(u)=\exp(\lambda(u-1))$ 。展开指数系数，式(3)给出

\Pr_r(T=n)=\frac rn e^{-\lambda n} \frac{(\lambda n)^{n-r}}{(n-r)!},\qquad n\ge r.

$r=1$ 时常称Borel分布公式。 $\lambda\le1$ 时全部有限质量为一； $\lambda>1$ 时它是有限部分的缺陷质量。临界 $\lambda=1$ 虽然 $T<\infty$ 几乎必然，仍有 $\mathbb ET=\infty$ 。有限随机变量的期望不一定有限。

没有叶子时不能强行反演

若 $p_0=0$ ，每个个体至少有一个孩子， $r\ge1$ 的森林永不终止，所以全部有限质量为零。式(3)右侧也为零： $\sum_{i=1}^n\xi_i\ge n>n-r$ 。但下面反演证明需要 $f(0)=p_0>0$ ，不能在 $p_0=0$ 时执行同一可逆换元；结论在这个边界应直接证明。

初始 $r=0$ 时 $T=0$ 恒定；它应作为单独的零森林处理，而不是向式(3)代入 $n=r=0$ 得到 $0/0$ 。

推论与应用

递归家系与形式反演

从一祖先出发，在扩展非负整数意义下有

T=1+\sum_{i=1}^{\xi}T_i,

其中子家系 $T_i$ 独立同分布于 $T$ ，且与 $\xi$ 独立。对 $0\le s<1$ ，把任何无限总数的贡献记为零，独立性给出 $H(s)=s f(H(s))$ ； $s\uparrow1$ 时按非负系数求和，同样得到端点等式。

也可逐个有限规模理解这个方程：总数为 $n$ 时，祖先至多有 $n-1$ 个孩子，且每个子家系都有限，所以每个系数只涉及有限多项。由此 $H$ 同时是形式方程 $H=s f(H)$ 的零常数项解。

当 $p_0>0$ ，实数域中的 $f(0)$ 非零可逆，满足Lagrange反演的条件。对外层函数 $u^r$ 使用系数公式，

[s^n]H(s)^r =\frac1n[u^{n-1}]r u^{r-1}f(u)^n =\frac rn[u^{n-r}]f(u)^n.

$f(u)^n$ 的系数正是 $n$ 份独立繁殖数之和的质量，得到式(3)。证明使用的是普通概率质量系数，没有指数生成函数中的 $n!$ 归一化。

先用有限截断证明矩有限

记一祖先到第 $N$ 代的累计人数为 $T_N=\sum_{j=0}^N Z_j$ 。它递增到 $T$ 。由于每代均值为 $m^j$ ，单调收敛定理给出

\mathbb ET=\sum_{j\ge0}\mathbb EZ_j=\sum_{j\ge0}m^j.

$m<1$ 时得到式(4)。 $m=1$ 时级数发散，这包括几乎必然灭绝的非退化临界过程，不能因其最终停止而把期望改成有限值。

为证明方差，先假设 $m<1,\sigma^2<\infty$ ，对每个有限 $N$ 计算。令 $a_N=\mathbb ET_N$ 、 $v_N=\operatorname{Var}T_N$ 。从根分解 $T_{N+1}=1+\sum_{i=1}^{\xi}T_N^{(i)}$ ，利用全期望和全方差公式，

a_{N+1}=1+m a_N, \qquad v_{N+1}=m v_N+\sigma^2a_N^2, \qquad a_0=1,\ v_0=0.

有限阶段的二阶矩可由这个递推归纳证明有限。再用 $a_N\le1/(1-m)$ ，得到

v_N\le\frac{\sigma^2}{(1-m)^2}\sum_{j=0}^{N-1}m^j \le\frac{\sigma^2}{(1-m)^3}.

于是 $\sup_N\mathbb ET_N^2<\infty$ 。对 $T_N^2\uparrow T^2$ 使用单调收敛，先确认 $T$ 二阶矩有限，才可让 $a_N,v_N$ 传极限；解 $v=mv+\sigma^2/(1-m)^2$ 得式(5)。初始有 $r$ 个独立家系时，均值和方差均相加。

条件灭绝保持哪一种独立性

假设 $q>0$ 。从一祖先出发，

\Pr(\xi=k\mid\mathcal E) =\frac{\Pr(\xi=k)\Pr(\text{全部}k\text{个子家系灭绝}\mid\xi=k)}q =p_kq^{k-1}.

这些数非负，且总和为 $f(q)/q=1$ 。给定 $k$ 后，对独立子家系同时施加各自的灭绝事件，条件分布仍分解成 $k$ 份相同的“已条件灭绝”的家系。因此整个过程递归地保留分枝结构。

同一事实也能在任意有限历史上核验。若初始有 $r$ 个祖先，观察到第 $N$ 代有 $Z_N=j$ ，未来全部灭绝的条件概率为 $q^j$ 。所以每个有限历史的条件概率，是原历史概率乘 $q^{j-r}$ 。各繁殖节点的权重 $q^{\xi-1}$ 相乘也恰为 $q^{j-r}$ ：非末代人数逐层抵消。这验证式(6)不仅给出首代边缘，还给出整个有限历史的联合规律。

当 $0<q<1$ ，严格凸性给出 $\widetilde m=\widetilde f'(1)=f'(q)<1$ 。此外 $\widetilde p_k=p_kq^{k-1}$ 带指数衰减，所有有限阶矩都有限，即使原繁殖分布的均值或方差无穷。若 $q=1$ ，变换不改变原分布；原临界过程也不会因此自动变成次临界。

用卷积表计算指定规模

给定有限支持 $p_0,\ldots,p_d$ ，若需要所有 $n\le N$ 的质量，可递推 $A_j(k)=[u^k]f(u)^j$ ：

A_0(0)=1,\qquad A_j(k)=\sum_{\ell=0}^{\min(d,k)}p_\ell A_{j-1}(k-\ell).

每完成一行 $j=n$ ，输出 $(r/n)A_n(n-r)$ ； $n<r$ 直接输出零。只需保留次数至 $N$ 的相邻两行，时间为 $O(N^2(1+\min(d,N)))$ 次算术操作，工作空间为 $O(N+1)$ 个系数，输入存储另计。无限支持时，计算这些有限系数只会读取 $p_0,\ldots,p_N$ ；不能把未读概率尾随意重新归一化，否则会改变原问题。

这个有限表给的是各个总数的精确质量，未列出的有限大规模和 $T=\infty$ 必须分别交代。终点的双祖先任务会同时检查卷积表、条件分布和缺失质量。

参考资料

Meyer Dwass，The total progeny in a branching process and a related random walk，Journal of Applied Probability6(3)，1969，682–686，原始公式书目；本页以形式反演给出自足证明。
Ira M. Gessel，Lagrange inversion，2016，§2.1，复合系数公式；这里将外层函数取为 $u^r$ ，概率解释和无叶边界另行证明。
Igor Kortchemski，Zurich master course, Lecture 5，手写讲义PDF第3、5页，随机游走编码下的单根公式与多根森林扩展；本页使用Lagrange反演作为另一条自足证明。

形式陈述 ​

二叉家系的奇偶支持 ​

Poisson繁殖与全体总数 ​

没有叶子时不能强行反演 ​

递归家系与形式反演 ​

先用有限截断证明矩有限 ​

条件灭绝保持哪一种独立性 ​

用卷积表计算指定规模 ​

反向链接