Metropolis-Hastings采样

MH采样，是一种MCMC采样方法。所谓MCMC，就是构造一个Markov链，使它的平稳分布$\pi(x)$就是我们想要采样的分布，这样一来，我们只要随机选取Markov链的一个状态$x_0$，然后根据状态转移矩阵反复更新这个状态，最终的状态就是我们想要的样本，因为这个Markov链平稳分布就是我们想要的分布，因为最终状态$x_t \sim \pi(x_t)$。

做法

MH采样主要有两个要素：

1. 提议分布$q(x'|x)$，也就是Markov链的状态转移概率。这个分布的选取基本上是任意的，只要方便采样就行。
2. 接受概率$A(x', x)$，决定是否要接受状态$x'$，如果不接受，就保留原状态，用来保证这个链是平稳的。

$$A(x'|x_t) = \min \left( 1, \frac{\pi(x') q(x_t|x')}{\pi(x_t)q(x'|x_t)} \right)$$

正确性的证明

主要就是要证明平稳分布确实是$\pi(x)$。

首先，我们写出对应Markov链的状态转移概率，如果$x' \ne x$

$$P(x'|x) = q(x'|x)A(x'|x)$$

如果 $x' = x$，也就是状态事实上没有改变，那么除了原本的转移概率，还要加上转移到其他状态被拒绝的概率

$$P(x|x) = q(x|x)A(x|x) + (1 - \sum A(u|x)q(u|x)du )$$

这个时候我们要介绍一下细致平衡条件。Markov链只要满足下面这个细致平衡条件，就存在平稳分布，平稳分布就是$\pi(x)$

$$\pi(x) P(x'|x) = \pi(x')P(x|x')$$

我们可以简单阐述一下这个条件的意义。假设Markov链已经平稳，那么不管再怎么转移状态，都还是平稳分布。我们可以想象有一大堆粒子，按照平稳分布处于各个状态中，那么任选一个状态，出去和进来的粒子数肯定一样多，否则处于这个状态的粒子数会发生变化，就不叫“平稳分布”了。细致平衡条件是这种想法的一个特例，它的要求更严格：假如处于Markov链现在处于某个分布，从a到b的粒子数，等于从b到a的粒子数，那么这个分布在下一时刻也不会发生任何改变，因此是平稳分布。

$x = x'$时，显然是满足细致平衡条件的，不信可以代进去看看（笑）。

因此只要考虑考虑$x \ne x'$的情况，又分两种情况

若 $\displaystyle \frac{\pi(x') q(x_t|x')}{\pi(x_t)q(x'|x_t)} \le 1$，那么

$$P(x'|x_t) = q(x'|x_t)A(x'|x_t) = q(x'|x_t)\frac{\pi(x') q(x_t|x')}{\pi(x_t)q(x'|x_t)} = \pi(x')q(x_t|x') / \pi(x_t)$$

并且一定有 $\displaystyle \frac{\pi(x_t) q(x'|x_t)}{\pi(x')q(x_t|x')} \ge 1$

所以

$$P(x_t|x') = q(x_t|x') A(x_t|x') = q(x_t|x')$$

两个式子联立，直接就是细致平衡条件。

若 $\displaystyle \frac{\pi(x') q(x_t|x')}{\pi(x_t)q(x'|x_t)} \gt 1$，和上面完全同理。

那么是不是只有一个平稳分布呢？如果马尔可夫链是不可约的，只会有唯一的平稳分布。而且因为存在拒绝下一个样本的可能性，这个链是非周期的。非周期的不可约马氏链，有且只有一个平稳分布。

MH采样的问题

MH采样难以应付高维分布。在维数很高的时候，拒绝概率很大，导致采样效率实际上很低。