给定一个简单的概率分布$p(x)$（比如均匀分布、正态分布），生成它的样本是比较容易的。但是当目标概率分布很复杂时，要生成它的样本就会变得十分困难。MCMC（蒙特卡洛马尔科夫方法）算法就是一种常用的生成复杂目标概率分布样本的算法。
MCMC的基础是非周期马氏链的平稳特性：从任意状态出发，最后都会到达平稳状态。当达到平稳状态后，每一次采样得到的样本$x$都服从平稳分布$\pi$。如果平稳分布$\pi$就是目标分布的话，那么我们就找到了一种生成目标概率分布样本的方法，MCMC就是使得$\pi$成为目标分布的方法。
具体算法推导参考：MCMC和Gibbs Sampling
MCMC需要已知目标概率分布$p(x)$和一个任意分布$q(x|y)$
算法如下：
初始化马氏链状态X=x0
对t=0,1,2…循环采样
采样$y\sim q(x|y)$
从均匀分布采样$u\sim U(0,1)$
如果$u<\alpha(x_y,y)=min\{\frac{p(y)q(x_t|y)}{p(x_t)q(y|x_t)},1\}$，接受新样本y，X=y，否则$X=x_t$
选取分布$q(x|y)$时，往往需要满足对称性，$q(x|y)=q(y|x)$，也就是x->y与y->x的概率相同，这样$\alpha(x_y,y)=min\{\frac{p(y)}{p(x_t)},1\}$
$q(x|y)$常选择以y为中心的高斯分布，这样越靠近y的值越可能在下一次被访问，这样的样本序列就是一个随机行走过程。
可以看到如果新的样本y处在$p$的高密度区域（$p(y)>p(x)$），则y总是被接受的，否则y可能被拒绝。直观上讲，被接受的样本总是以较大的概率落在$p(x)$的高密度区域，而以小概率落在$p(x)$的低密度区域（被拒绝），因此接受的样本序列大致服从$p(x)$的概率分布。
MCMC虽然能够有效的生成复杂概率分布的样本，但也有几个显著的缺点：
- 样本是相干的，由于采用马氏链生成，相邻的样本并不独立，解决该问题可以通过增加jumping size，即再次从采样序列抽样。
- 初始分布并不服从平稳分布，有一个burn-in的过程，导致算法可能需要迭代n次后，采样的分布才服从目标分布。