分支过程

在概率论中，分支过程（英語：Branching Process）属于随机过程的一类，由一系列随机变量组成。分支过程的最初目的是建立一个数学模型，研究第n代个体产生随机个后代时的个体数模型。最简单的情况是每个个体产生的后代数目遵循相同的随机分布。^[1]

分支过程最常见的表述是高爾頓－沃森過程（英语：Galton–Watson process）。记Z_n为第n代的状态，随机变量X_n,i表示第n代中第i个个体产生的直系后代数。对一切n ∈{ 0, 1, 2, ...}，X_n,i是独立同分布的。于是可得递推关系式

${\displaystyle Z_{n+1}=\sum _{i=1}^{Z_{n}}X_{n,i}}$

其中Z₀ = 1。

另外，分支过程也可表述为随机游走。记S_i为第i代的状态，随机变量X_i对一切i都是独立同分布的，则递推关系式为

${\displaystyle S_{i+1}=S_{i}+X_{i+1}-1=\sum _{j=1}^{i+1}X_{j}-i}$

其中S₀ = 1。要想从直观上理解上式，可以设想一次随机游走的目的是访问到所有节点。令S_i为第i期已发现但未访问的节点数，X_i为第i个节点得到访问时已发现的节点数。于是在每一期中，已发现但未访问的节点数等于上一期已发现但未访问的节点数加上访问新节点时发现的节点数，再减掉刚访问的节点。当所有节点都访问过时，整个过程停止。

• 隨機樹
• 鞅 (概率论)