19-高尔顿-沃森树

有根树

树是一个没有环的连通图。

有根树有一个特别指定的顶点 ，称为根。

顶点 的深度是它到根的图距离。

叶子是度数为 的顶点。

考虑一棵正则有根树：每个顶点都有固定数目的后代，设这个数目为 。

令

有根二叉树的层级关系可示意为

          根
       ／    ＼
   第1代      第1代
   ／  ＼      ／  ＼
第2代 第2代  第2代 第2代

对正则树，

在实际问题中，我们经常遇到另一类树：每个顶点的后代数是随机的。

高尔顿—沃森树

高尔顿—沃森树按如下方式生成：

1. 从一个初始祖先开始；
2. 该祖先按照某个分布 产生一定数目的后代；
3. 这些新个体构成第一代；
4. 每个新个体都按照同一个分布 产生后代，并且各个个体彼此独立；
5. 这一繁衍机制逐代重复。

令

观察： 如果对某个 ，

那么对所有 ，

这意味着该家族已经灭绝。

问题： 灭绝概率是多少？定义

灭绝概率

记号

令

于是

记平均子代数为

假设

采用约定

灭绝概率为

繁殖分布的生成函数定义为

它满足

定理. 灭绝概率 是方程

在区间 上的最小根。

特别地，

而

灭绝概率

定理. 灭绝概率 是方程

在区间 上的最小根。特别地，当 时 ，当 时 。

• 在亚临界情形 中，高尔顿—沃森树以概率 灭绝。
• 在临界情形 中，高尔顿—沃森树以概率 灭绝。
• 在超临界情形 中，高尔顿—沃森树以严格正概率

存活。

问题： 在超临界情形 中，这棵树增长得有多快？

我们知道

是否也有

增长速度

假设：

定义

则 是非负鞅，并且

由 Fatou 引理，

观察：

• 如果 ，则

• 如果 ，则

定理（Kesten–Stigum）. 下列三个条件等价：

其中

增长速度

假设：

定义

则 是非负鞅，并且

由 Fatou 引理，

观察：

• 如果 ，则

• 如果 ，则

定理. 如果

则

并且

引理.

只能取 或 。

麻省理工学院开放式课程