跳转到内容

分支过程

维基百科,自由的百科全书

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

数学表述

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

其中Z0 = 1。

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

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

参见

参考文献

  1. ^ Athreya, K. B. Branching Process. Encyclopedia of Environmetrics. 2006. ISBN 0471899976. doi:10.1002/9780470057339.vab032.