References：

马尔可夫蒙特卡罗 MCMC 原理及经典实现

马尔可夫链蒙特卡罗算法（MCMC）

【概述】

对于对某概率分布进行随机抽样，或求函数关于该概率分布的数学期望等问题，使用蒙特卡罗法即可解决

而基于拒绝采样法的蒙特卡罗法的使用要求有两点：

概率密度函数可积
累积分布函数有反函数

也就是说，当面临无法得到具体形式的非共轭后验分布、随机变量是多元的、随机变量各分量不独立等情况时，就无法使用蒙特卡罗法了

例如：假设参数 $\theta$ 的先验分布为某定义域 $\theta\in[0,1]$，均值 $\mu=\frac{1}{2}$，正则化系数为 $\alpha$ 的截尾正态分布，后验分布 $P(\theta|X)$ 具备如下形式：

$p(\theta|x) = \frac{\theta^{x}(1-\theta)^{1-x}\cdot \frac{\alpha}{\sqrt{2\pi}}e^{-\frac{(\theta-\frac{1}{2})^2}{2\sigma^2}}}{\int_{0}^{1} \theta^{x} (1-\theta)^{1-x} \cdot \frac{\alpha}{\sqrt{2\pi}}e^{-\frac{(\theta-\frac{1}{2})^2}{2\sigma^2}} d\theta}$

显然，虽然知道这个后验分布 $P(\theta|X)$ 的形式，但无法解出分母

为解决该类问题，出现了马尔可夫链蒙特卡罗法（Markov Chain Monte Carlo，MCMC），其是从概率分布中抽样以构建最大可能分布的一类方法，核心思想是：设计一个具有给定平稳概率分布的马尔可夫链模型，然后根据遍历理论，用采样器的随机状态的经验测度来近似平稳分布

简单来说，这类方法生成的序列都是马尔可夫链，每个值都只与自己前后的几个值有关，同时，用随机化的方法来解决确定性问题，从已知概率分布中采样出一系列符合目标分布的样本

MCMC 的出现使得许多贝叶斯统计问题的求解成为可能，在机器学习、深度学习等领域有广泛的应用，是诸多复杂算法求解的基础

MCMC 有两种基本算法：

【基本思想】

假设多元随机变量 $x\in \mathcal{X}$，其概率密度函数为 $p(x)$，$f(x)$ 是定义在 $x\in\mathcal{X}$ 上的函数，目标是获得概率分布 $p(x)$ 的样本集合，以及求函数 $f(x)$ 的数学期望 $E_{p(x)}[f(x)]$

MCMC 的基本思想是：

1）在随机变量 $x\in \mathcal{X}$ 的状态空间 $S$ 上构造一个满足遍历定理的马尔可夫链 $\{X_t,t\geq0\}$，使其平稳分布就是抽样的目标分布 $p(x)$

2）从状态空间的某一点 $x_0$ 出发，用构造的马尔可夫链进行随机游走，产生样本序列 $x_0,x_1,\cdots,x_t,\cdots$

3）根据马尔可夫链的遍历定理，当时间趋于无穷时，样本的分布趋于平稳分布，样本的函数均值趋于函数的数学期望

确定正整数 $m,n(m<n)$，得到样本集合 $\{x_{m+1},x_{m+2},\cdots,x_n\}$，并求函数 $f(x)$ 的遍历均值

$\hat{E}f = \frac{1}{n-m} \sum_{i=m+1}^n f(x_i)$

此时，得到的样本集合 $\{x_{m+1},x_{m+2},\cdots,x_{n}\}$ 就是目标概率分布的抽样结果，得到的函数均值就是要计算的数学期望，从时刻 $0$ 到时刻 $m$ 为止的时间段，被称为燃烧期

关于遍历定理，详见：马尔可夫链的状态

由于马尔可夫链 $\{X_t,t\geq0\}$ 满足遍历定理，因此随机游走的起始点并不影响得到的结果，即从不同的起始点出发，都会收敛到同一平稳分布

同时，对于马尔可夫链蒙特卡罗法中的得到的样本序列，相邻的样本点是相关的，而非独立的，因此在需要独立样本时，可以在该样本序列中再次进行随机抽样，将得到的子样本集合作为独立样本集合

马尔可夫链蒙特卡罗法比基于接受-拒绝法的蒙特卡罗法更容易实现、效率更高，因为 MCMC 仅需定义马尔可夫链而不需定义提议分布，虽然燃烧期的样本需要抛弃，但不需要大量拒绝样本