0%

梅特罗波利斯算法

蒙特卡洛方法中抽样方法的一种。

马尔科夫链

设一个系统状态序列为$x_0,x_1,x_2,…$,每个状态可以以一定概率转化到另一状态,假设从其中任意一个起始状态开始行走,每个时刻发生一次状态转移,对于任意时刻$n$系统状态转移的条件概率为:
$$
P(X_{n+1}=x|X_0=x_0,X_1=x_1,…,X_{n}=x_{n})=P(X_{n+1}=x|X_n=x_n)
$$
则此转移过程形成的状态序列$X_0,X_1,…,X_{n+1}$称为马尔科夫链。$P(X_{n+1}=x|X_n=x_n)$称为转移概率,若转移概率与时间$n$无关,称这样的马尔科夫链是时齐的。通常研究的都是时齐的马尔科夫链。

利用马尔科夫链对目标概率分布进行抽样的过程,实际上就是设一个状态系统服从目标概率分布,然后给定一个任意初始值,经过一段时间系统平衡后,产生的马尔科夫链就是服从目标概率分布的,由此得到抽样值。

马尔科夫链属性

不可约性

非周期性

回返性

遍历性

平衡分布

细致平衡

//TODO

梅特罗波利斯算法

设$f(x)$为正比于目标概率分布$p(x)$的近似分布,梅特罗波利斯算法的基本步骤为:

  1. 初始化阶段:选取一个任意点$x_0$作为起始抽样点,并选择一个任意概率密度函数$g(x|y)$用来根据当前抽样随机数$y$产生下一个候选随机数$x$,$g(x)$必须是对称的,即满足$g(x|y)=g(y|x)$。常用的$g(x)$是高斯分布。
  2. 迭代阶段,对于每一次迭代$n$:
    • 首先从建议密度函数$g(x’|x_n)$产生一个候选抽样点$x’$
    • 计算接受率$\alpha=\frac{f(x’)}{f(x_n)}$,这个接受率用于决定新的候选抽样点被接受或拒绝
    • 如果$\alpha\ge1$,新的候选点直接被接受:$x_{n+1}=x’$;否则,按照概率$\alpha$来接受候选点;若新的候选点被拒绝,则设置:$x_{n+1}=x_n$