本文会介绍MCMC（markov chain monte carlo）的工作原理，MH（Metropolis-Hasting）采样和Gibbs采样。

MCMC

MCMC是markov chain和monte carlo两个方法名称的结合。这两个名词的介绍可以见Monte Carlo Integration，MCMC。

给定一个状态转移概率 $P$，马尔可夫过程告诉我们，在进行多次状态转移之后，最后每个状态的分布会遵循一个分布 $\pi(y)$，而这个分布只和状态转移概率 $P$ 有关。给定一个 $P$ 我们就可以找到一个稳态的分布 $\pi$。

现在我们的问题是给定分布 $\pi$ 如何找到对应的状态转移分布 $P$，使得我们能够进行对复杂的分布 $\pi$ 采样。

根据细致平稳条件，对于任意点$x$ 和 $y$，

$$\pi(x)Q(y|x) = \pi(y)Q(x|y)$$

通常，给定的$Q$是不满足上述条件的（$Q$ 称作提议分布，一般选择均匀分布或者高斯分布），我们在两边同时放入$\alpha_{ij}$ 和 $\alpha_{ji}$，

$$\begin{aligned} \alpha_{ij} &= \pi(y) Q(x|y)\\ \alpha_{ji} &= \pi(x) Q(y|x)\\ \end{aligned}$$

这里的 $\alpha$ 和拒绝采样中起同样的作用。

工作流程如下：

1. 从均匀分布 $\rm U(0, 1)$ 中采样得到 $p$；
2. 从条件概率分布 $Q(x\vert x_t)$ 中采样得到新的点 $x$；
3. 计算 $\alpha = \pi(x)Q(x\vert x_t)$；如果$\alpha\geq p$，则即为 $x_{t+1}$，否则重复上述过程。

MH

上述MCMC方法有个问题就是，两个概率相乘可能会得到很小的$\alpha$。

MH的做法是，将细致平稳的两边放大$\alpha = \min\{\frac{\pi(x)Q(x\vert x_t)}{\pi(x_t)Q(x_t\vert x)}, 1\}$

其余的流程和MCMC一致。

Gibbs

Gibbs为了提高在高纬度的采样效率，使用了类似于block的想法。

Reference

• Boyang Zhao：MCMC
• Eureka：MCMC
• Darren Wilkinson: Gibbs