Markov 链 Monte Carlo

阐述

给定 $\mu$ 是一个有限状态 $\mathcal X$ 上的分布，我们可以找到一个不可约的、非周期的 Markov 链 $P$ 使得它的稳态分布是 $\mu$ ，则我们可以运行一段时间，等它接近 $\mu$ 之后开始采样。

给定 $P$ 是一个 Markov 链， $\mu(x)>0$ 是一个 $\mathcal X$ 上的分布，则构造相应的 Markov 链

\hat P(x,y)=P(x,y)\min\left(1,\frac{\mu(y)P(y,x)}{\mu(x)P(x,y)}\right)

且 $\hat P(x,x)$ 的定义使得每行之和为 1。这样定义的 $\hat P$ 对 $\mu$ 是可逆的，因此 $\mu$ 是此 Markov 链的一个稳态分布。

此外，如果 $P$ 是不可约的，且 $P(x,y)>0\Leftrightarrow\hat P(y,x)>0$ ，这说明 $\hat P$ 也是不可约的。非周期性可以通过以一定概率暂停 $P$ 来实现。

设 $\mathcal X=S^n$ ， $S$ 是某个集合， $n>0$ 。 $\mu$ 是一个 $\mathcal X$ 上的分布。则从 $(x_1,\cdots,x_n)$ 出发，选定一个指标 $x_i$ 进行如下随机移动：

\mathbb P(X=x)=\frac{\mu(x_1,\cdots,x,\cdots,x_n)}{\sum_y\mu(x_1,\cdots,y,\cdots,x_n)}

这个 Markov 链显然对 $\mu$ 也是可约的。

\frac{\exp\left(\beta\sum_w\sigma(w)\right)}{\exp(-\beta\sum_w\sigma(w))+\exp(\beta\sum_w\sigma(w))}

其中对 $w$ 的求和可以仅对与 $v$ 相连的节点完成。