为什么要用MCMC?

前面转载过一篇文章MCMC和Gibbs Sampling,文中详细介绍了MCMC算法及其证明.本文用几个简单的例子再来理解一下MCMC.

假设有一个抽样任务,变量X取值的样本空间为，且取1,2,3三个值的概率分别为。那么这时候你要如何从这个分布中进行采样？

我想大多数人自己都写过这样简单的程序，首先根据各离散取值的概率大小把区间划分为,,这三个区间，再通过计算机产生之间的伪随机数，根据伪随机数的落点即可完成一次采样。

现在把问题改为二维的,每个维度上的取值和概率同上,我们可以把二维平面按比例切分,然后产生两个之间的伪随机数，根据这两个伪随机数的落点进行采样:

你可能已经看出来了,随着维度的增加抽样的复杂度是程指数增加的.假设我们有100维的数据,每个维度有10个取值,那么概率空间的大小为,作为对比，已知宇宙的基本粒子大约有个。

上面例子取值是离散的,但如果分布是连续的,我们无法直接对概率进行"分段",聪明的你可能会想到,我们可以已固定长度进行"分段",的积分就是这段出现的概率.不幸的是,并不是所有的函数都可以计算积分,而且已固定长度进行"分段",同样有"维数灾难"的问题.

如果仔细观察"等距计算"的结果，就会发现绝大多数点算出的概率都很小，而少部分点的概率非常大。而如果我们忽略大多数概率小的点，只计算概率大的那小部分点，对最后数学期望的结果影响非常小。这是MCMC思路的直观部分。

参考:
https://www.zhihu.com/question/60437632