Branching Process 分支过程

本文为研究生课程《计算机科学与技术理论基础》课程的作业内容。在网上没有检索到相关的中文资料，于是为了加深自己的理解(同时造福后人)，写成此文。

为了不破坏连贯性，文中提到的定理仅描述内容，证明部分置于附录。

前言

一切故事起源于19世纪中期，众多贵族意识到他们的家族将会面临灭绝的风险，因此一位叫Galton的贵族兼学者提出这样的一个问题：

Galton

How many male children (on average) must each generation of a family have in order for the family name to continue in perpetuity?

1874年，Reverend Henry William Watson和Galton共同发表了一篇名为《One the probability of extinction of families》，自此这个问题得到了解决。

本文便是以这个问题为背景，探讨分支过程和分支过程的灭绝概率。

首先我们需要对分支过程进行定义。这很容易理解，类比兔子生小兔子的问题，每只兔子随机生若干个小兔子，并且死去，分支过程研究的是每一代兔子的总数符合什么样的特征。用数学模型来表达，我们可以将分支过程抽象为下面的描述：

一个种群在第零代

时开始，此时种群的总数

。

经过一段单位时间(即一代)，在

时，这个唯一的个体产生了

个子个体，并且死去。此处，

是一个非负整数域的随机变量。

按照

的取值，我们面临下面几种情形：

，则种群灭绝，在

时，任何事情都不会发生。

，我们用

代表第一个个体，

代表第二个个体，以此类推，

代表最后一个个体。为了简化问题，我们假设这些个体产生下一代的数量的概率分布相同，且相互独立。同时，这些概率分布又与

相互独立，即与他们的个数相互独立。在

时，我们可以得到总体数量为：

后面的代类推下去，我们可以得到

上面这个过程定义为简单的分支过程(Simple Branching Process)。我们接下来的研究都是基于这种分支过程，即一个重要假设：

每个节点产生下一代节点的个数的概率分布相同，相互独立，且与其他代也相互独立(即与本代节点总数相互独立)。此概率分布函数称为Offspring distribution。

为了模拟分支过程，我们可以利用许多工具。随机游走就是其中之一，但是随机游走并不是十分适用，因为本问题中每一代的增长量

是与

相关的。

我们也可以用生成函数(Generating Function)来做这件事，而事实上，生成函数更加适合。下一个章节会对我们用到的生成函数这一数学工具作出解释。

概率生成函数

概率质量函数(Probability Mass Function, PMF)：定义为一个离散函数，

。

PMF可以理解为离散型随机变量的概率密度函数。

生成函数

对于一个非负整数值的随机变量

来说，它可以被一个序列

完全确定。其中，

取值范围为

，定义为

的概率，即：

因此，

可以被用来构造一个幂级数，即：

由于

，因此

的收敛半径至少为1。

回顾：幂级数的收敛半径

为使得

绝对收敛的最大正数。

定义：

可以定义为PMF：

的生成函数。简单表示，可以定义为非负整数值随机变量

的生成函数。

几个常见分布的生成函数

伯努利分布

：此处

，

对任意

成立。因此：

二项分布

：

。因此：

几何分布

：

。因此：

泊松分布

：

。因此：

生成函数的基本分析性质

定理1：对

一个非负整数值随机变量，其PMF为

，其生成函数为

，则如下成立：

下凸，单调递增，且

在区间

无穷阶可导，且：

推论：

，因此

唯一确定了一个序列

。

证明见附录。

后面我们会用到的定理

定义：

和

为两个PMF，则他们的卷积

定义为序列

，其中：

性质：

和

为两个PMF，则他们的卷积

也是PMF，即满足：

定理2：

为两个独立的非负整数值随机变量，他们的PMF分别为：

和

，则他们的和

也是非负整数值随机变量，其PMF为

和

的卷积。

证明见附录。

定理3：

和

为两个PMF，

和

为他们的生成函数，则卷积

定义的生成函数

满足下式：

推论：

为两个独立的非负整数值随机变量，

为其生成函数，则有：

证明见附录。

定理4：

是一列相互独立的非负整数值随机变量，他们的PMF均为

，生成函数为

。

为一个与

独立的随机变量，代表随机次数。则随机变量的随机和

的生成函数

有：

证明见附录。

此处不表述上面定理的用途，在后文的建模和证明过程中会用到。

基于生成函数的分支过程数学模型

我们如何表示第

代的群体总数

(

)的分布？这是分支过程模型的一个核心问题。

给定一个Offspring Distribution，我们可以定义一个分支过程

。下面我们考虑他的概率模型。

首先，

的含义是个体数，因此必然为非负整数值随机变量。所以此分布可以完全由其PMF决定。根据上面对概率生成函数的定义，也就是完全由其生成函数决定。虽然直接定义他的PMF很困难，但我们可以利用生成函数的工具进行计算。

定理5：

为一个分支过程，其Offspring Distribution由PMF：

定义，此PMF的生成函数记做

。则随机变量

的生成函数可以表达为：

证明见附录。

几个常见的Offspring Distribution定义的分支过程的特性分析

为一个分支过程，其Offspring Distribution由PMF：

定义，则：

：

此时

，故

。此时，

。这个分支过程在第一代即灭绝。

Offspring Distribution of example 1

感性认识：Offspring Distribution的PMF如上图，可以看出每一代的后代个数的分布情况是：个数为0的概率为1。因此在第零代的时候，节点就不会产生新的节点了，从而在第一代没有新节点，而第零代的节点死亡，分支过程结束，种群灭绝。

：

此时

，故

。此时，

。这个分支过程表现为：从一个节点开始，每一代会生成一个新节点，同时在下一代时死亡。因此种群会在任何代都保持

的总体数量。

Offspring Distribution of example 2

感性认识：Offspring Distribution的PMF如上图，每个节点的后代个数为1的概率均为1，也就是每个节点的后代必然有且仅有一个。所以从第零代开始，每个节点都会产生仅一个新节点，同时自身死亡。每代的种群总数均为1。

：

此时，

。因此

，即第

代的种群总数

。

：

此时，

。这是因为s在这个重叠乘法中只有一个。有因为乘法都是

在做，所以

。又因为

是概率质量函数的生成函数，所以

，因此

。到这里，我们就可以知道

。因此，第

代种群总数

的概率为

，

的概率为

。

统计特性

虽然我们通过上面的生成函数可以对分支过程

的每一代个体数有了初步的认识，并且某些情况下可以计算总体数量分布的显式解。但是上面举的例子都是十分简单的，当我们遇到复杂的分支过程时，依然难以计算分布的显式解。例如：给定Offspring Distribution：

，此时

的显示解是难以计算的。(可以自己尝试一下)

虽然这样，我们依然可以对分支过程每一代的总体数量的分布的统计特性进行研究了。引出下面这个定理。

定理6：

为一个分支过程，定义在PMF：

上。如果此PMF存在均值，即：

，则有：

类似地，如果PMF存在方差，即

，则：

证明见附录。

灭绝概率

基于上面的模型，我们可以回答刚开始提出的问题了，即什么时候一个家族才会灭绝。

灭绝

首先我们要先给“灭绝”下一个数学上的定义。

定义：事件

称为灭绝。

直观上理解，就是找到一个代数

，我可以断言，在第

代，种群总数为零。这也就意味着，从第n代开始，这个种群不会再有变化了(因为从第

代就已经没有个体了)，所以称为“灭绝”。

定义：用记号

表示一个上升集合列，即：

。

这个定义中的上升是因为：当第

代总数

时，任意给定一个正整数

，也一定有

。因此，事件

灭绝概率

因为上面的定义，我们可以断言，如果构造一个概率序列

，则这个序列是单调非减的。再根据单调有界原理，

为概率值，因此一定属于区间

，满足有界性，因此序列一定收敛。

定义：灭绝概率定义为上述概率序列的极限，即：

又由

定义，有

。

再根据生成函数的定义：

，此处

为

的概率，也就是

在此处是非负整数值随机变量

的PMF。因此，有

。

因此，本定义可以改写为：

灭绝概率的计算

定理7：灭绝概率

是方程

的最小非负解。此方程称为灭绝方程。

证明见附录。

根据这个定理，大多数分支过程的灭绝概率我们都可以计算了(虽然

的显式表达式不一定求得出来)。

下面我们可以通过两个参数，即

和

观察灭绝概率的特征。其中

，这是因为

，则

。所以

。

灭绝函数的图像表示

由于

为下凸单调递增函数，

，故

的图像可以分为上面三类。

，则

对

成立。

，则

对

成立。

，则

，此时树的形状为一根无限单链。

，则

在

内有唯一解。

根据上述定理，我们知道，情况4中的

在

中的根即为灭绝概率

。

灭绝家族期望规模

对一个家族而言，其灭绝时的规模一定是有限的，但是这个规模的期望值却不一定有限。例如：

假设家族灭绝时的规模为一个随机变量，以

概率为3，

概率为9，

概率为27，以此类推。则这个分布为

，

。则

的期望

。

如果给定条件

，其中

，则家族灭绝时的规模一定是有限的，即上述情况是不会发生的。

定理8：给定

，则灭绝家族的规模期望值是有限的。若

并且

，则家族树为一条单链，不会灭绝。若

并且

，则灭绝家族的规模期望值是无穷大。

证明见附录。

附录：证明

定理1 证明

由均值的性质，

，因此

因为

对任意

成立，

对任意

成立，因此

在区间

上单调递增且下凸。

由单调性知，

。

定理2 证明

，由于：

根据序列卷积的定义，我们明显得出

定理3 证明

，则：

。根据定理2，

，即

。

设

的生成函数为

，则：

定理4 证明

此处我们不加证明地利用了Fubini’s Theorem。关于此定理可以参考本文。

，则：

定理5 证明

设第

代有

个个体，每个个体的后代个数为一个独立同分布的随机变量，其生成函数为

。

首先，从第零代开始，由于第零代只有唯一一个个体，第一代的个体数

的分布即为Offspring Distribution。从而

用记号

表示第

个个体的后代个数，这是一个非负整数值随机变量。那么，第

代个体数

。假设

的生成函数为

，

的生成函数为

，则有：

从第1代开始，逐代进行此步骤，我们可得：

定理6 证明

先证明一个子命题

命题：

为一个非负整数值随机变量，则

。

证明：很简单，

，所以

，所以

下面证明定理

由定理5，

，因此

。所以

。

因为

，所以

。

所以

。

从第1代开始，逐代进行此步骤，我们可得：

所以

。

定理7 证明

先证明：

是方程

的解。

定义一个数列

，其中

。

由

的定义，有

，可知序列

必收敛到

。

再根据

的定义，有

。

因此，有：

根据海涅定理，

连续，所以

。

因此：

因此，

是方程

的一个解。

再证明：

是方程

在区间

上的最小解。

假设方程

存在另一个解

，则

。由定理1知，P(x)单调递增，因此

。因为

是一个解，所以

。

再由定理1，有

。因此我们可以对

再应用上述过程，得到

。

一直迭代下去到第

次，我们可得：

两边取极限，有：

因此，任取另一个解

，我们得到

。即

为方程

的最小非负解。

定理8 证明

从全概公式出发，

等式两端对

求和，得，

继续化简得，

由

的含义，可知：

，并且

因此，上式可化为，

整理得，

注意到，

，因此

。

因此，我们可以得到，

由定理5，又有，

因此，

又因为灭绝概率

为方程

的解，因此，

带入上式可得，

所以，灭绝家族的期望规模为：

因此，考虑参数

,

当

时，

，此时

，从而可得期望规模

；

当

时，

，此时

，与上述情况类似；

当

时，若

，则家族树为一条单链，如常见Offspring Distribution中的一个案例所示，此时家族不会灭绝；若

，则

，级数发散，即期望规模为无穷大。