马尔可夫链蒙特卡洛法（MCMC）知识点总结

MCMC方法最初来源于上世纪的物理学物理学研究，它解决了一类采样问题，且对于高维分布数据同样适用。在说明MCMC之前应该先了解一下蒙特卡洛求积分的方法，这点请参考文献[3]。

马尔可夫链的极限概率

对于马尔可夫转移矩阵 A， 我们知道它的每一行的和都为1，且元素的都在区间[0,1]之间。它有两个性质：

1. A有特征值  2. A的所有其它特征值的绝对值都小于1  （证略）

有了这两个性质，我们得出一个非常有趣的结论。对于马尔可夫链的初始状态概率分布 ，其经过 k 次状态转移之后，其概率分布为：。我们知道  可以表示为 A 的特征向量的线性组合，我们设 A 的特征值为，对应特征向量为 。我们有，由于且，所以当k趋近于无穷时，我们有，所以是收敛的，设其收敛于，且，即和初始状态分布无关。

这为MCMC建立了理论基础，如果我们想在某个分布下采样，只需要模拟以其为平稳分布的马尔可夫过程，经过足够多次转移后，我们的样本分布就会充分的接*稳分布。

想要模拟平稳分布的马尔可夫过程，转移概率矩阵需要满足一定的条件，即细致平稳条件（detailed balance）：。当条件满足时，可以证明状态分布  在转移概率 P 的条件下保持不变：

MH采样

我们可以看出，按照上述方法，状态 i 转移到 j 的概率为

易证，其满足细致平稳条件。

故状态分布最终会收敛于 。算法描述如下：

可以看出，MH算法不需要像拒绝采样那样可能会舍弃采样点，而是重复之前的采样点。当然q的选择不同mh的表现好坏会受到影响，比如如果同样的x出现次数太多次，则采样效果便不好。

Gibbs采样

我们知道MH采样需要拒绝采样，如果q选不好，拒绝率会非常高从而影响采样效率；其次，MH采样对于高维数据接受率计算量仍然比较大。Gibbs采样作为一种改进方法，解决了该问题。该算法如下（细致平稳条件证略）：

我们可以看到，该算法并不需要去拒绝, 且每单个维度的采样是以其他维度为条件的，也就是说我们可以单个维度进行采样！

参考文献：

[1] MIT线性代数视频（Gilbert Strang）

[2] https://www.cnblogs.com/pinard/p/6645766.html

[3] https://blog.csdn.net/itplus/article/details/19168937

[4] 徐亦达机器学习