2010年11月6日星期六

序贯蒙特卡洛(一)




遗传学的例子

大三那年自从上了白老师的一个讨论班之后,就对生物学中的很多问题很感兴趣。这 本教材中也有不少生物方面的例子,让我时不时眼前一亮。

考虑一组等位基因的演化历史。我们能观察到的,只有今天这组等位基因在某种群的分 布。我们提出一个单倍体演化模型,只考虑繁殖和突变,一步概率转移矩阵由某个待定系数t唯一决定。用极大似然方法估计这个参数,也就是极大化历史演化成今 天这个样子的概率。

按照定义,要计算

P(H0)=sum{P(H)|H 的最后一代是H0}

其中H0是 今天的分布,H是历史演化过程。这在计算上是不可行的,因为H的空间太大了。自然想到蒙特卡洛。

任意给定参数t,根据贝叶斯公式,可以知 道P(H-1|H0),从而每一步,根据今天的分布,按条件概率采样尝试回到昨天的分布,也就是P(H-1|H0)的估计。反复为之,可以得到 P(H|H0)的估计,也就是在今天这样分布的条件下,某历史演化过程存在的概率。
从而得到P(H0)的估计:P(H)/P(H|H0)的多次实 现的均值。




聚合物的例子

考虑一个随机方案来构造一个长度为N的、在平面网格点上的、不能自交的 路径,使得任何两条满足条件的路径出现的概率相同。不失一般性,假设从原点出发第一步向右走。
方案A:
每一步从{左转、右转、直行}三个 中等概率选择一个,如果自交了,则拒绝当前路径从头再来。否则走到长度为N接受它。
方案B:
每一步如果没有能走的地方,则拒绝当前路径从 头再来,否则从能走的1或2或3个地方中等概率选择一个,所谓能走的地方,指的是{左转、右转、直行}的三个点中之前没有到达过的那些。

B 看起来更有效率,然而不幸的是它不是无偏的:它更倾向于走出一条压紧、褶皱的路径。例如,对于N=4,走出[右,右,右,右]的概率就要小于[右,上, 左,左]
为了使得B均匀分布,需要为它生成的每条路经赋一个修正权重,而这个修正权重的计算,正是蒙特卡洛方法的精髓。

没有评论: