分支过程

分支过程最常见的表述是高尔顿－沃森过程（英语：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个节点得到访问时已发现的节点数。于是在每一期中，已发现但未访问的节点数等于上一期已发现但未访问的节点数加上访问新节点时发现的节点数，再减掉刚访问的节点。当所有节点都访问过时，整个过程停止。

• 随机树
• 鞅 (概率论)