抽样算法的主要任务是找到符合给定分布 $p(x)$ 的一系列样本。对于简单的分布，可以通过基本的抽样算法进行抽样。大多数分布都是不容易直接抽样的，马尔可夫链蒙特卡罗算法解决了不能通过简单抽样算法进行抽样的问题，是一种重要的实用性很强的抽样算法。

马尔可夫链蒙特卡罗算法（简写为MCMC）的核心思想是找到某个状态空间的马尔可夫链，使得该马尔可夫链的稳定分布就是我们的目标分布 $p(x)$ 。这样我们在该状态空间进行随机游走的时候，每个状态x的停留时间正比于目标概率 $p(x)$ 。在用MCMC进行抽样的时候，我们首先引进一个容易抽样的参考分布q(x)，在每步抽样的过程中从q(x)里面得到一个候选样本y, 然后按照一定的原则决定是否接受该样本，该原则的确定就是要保证我们得到的原本恰好服从p(x)分布。

MCMC由梅特罗波利斯(Metropolis)于1949年基于马尔可夫链的基本性质提出，下面介绍一下与马尔可夫链相关的性质。

一、稳定分布

稳定分布是指当我们给定状态空间的一个初始分布 $\pi_0$ 以后，按照转移矩阵进行跳转最终达到的稳定状态。

设转移矩阵为A，其中 $A_{ij} = p(x_t= j|x_{t-1} =i)$ , $\pi_t$ 为第t步的状态分布，那么第t+1步的状态分布可以写为 $\pi_{t+1}^T=\pi^T_tA$ ,经过一系列跳转以后，最终 $\pi$ 达到一个稳定分布，即 $\pi^T = \pi^T A$ 。

可以写为以下形式，

$\pi_i\sum_{j\neq i}A_{ij} = \sum_{j\neq i}\pi_j A_{ji}$

即每个状态的流出概率等于该状态注入的概率，该方程称为全局平衡方程。满足该方程的分布称为转移矩阵A的稳定分布。

二、细致平衡

对于一个稳定分布，我们可以给其一个更强的条件限制，使得任意一个状态 $i$ 满足如下条件，

$\pi_iA_{ij} = \pi_j A_{ji}$

表示对于任意一对节点 $(i,j)$ ，i到j的概率等于j到i的概率，该等式称为细致平衡方程。我们有如下定理，如果一个分布满足细致平衡方程，那么它也满足全局平衡方程。

证明如下：

考虑 $\pi^T A$ 的任意元素i,我们有以下等式，

$(\pi^TA)_i= \sum_j \pi_j A_{ji} = \sum_j \pi_i A_{ij} = \pi_i \sum_j A_{ij} = \pi_i$

对于任意元素i，上面等式成立，因此我们有 $\pi^T = \pi^T A$ 。

下面我们介绍基本的梅特罗波利斯算法(Metropolis algorithm)。假设 $p(x)$ 是我们的目标分布函数，我们想得到一系列服从该分布的样本。我们考虑样本的产生过程构成一个马尔可夫链，并且让p(x)是该马尔可夫链的稳定分布，那么该样本序列就服从p(x)。现在p(x)是已知的，问题的关键在于如何构造这个产生过程，也即如何构造马尔可夫链。

首先我们引进一个参考分布 $q(x)$ ，该参考分布是一个容易抽样的简单分布，例如高斯分布。用 $z$ 表示状态变量， $z_t$ 表示第t步时的状态，每一步状态转移按如下过程进行：

(1) 从 $q(x)$ 产生一个候选样本 $y$ 产生概率为 $q(y|z_t)$ ;

(2) 计算接受概率

$A(y, z_t) = min(1,\frac{p^*(y)}{p^*(x_t_)})$

(3) 如果候选变量被接受，那么状态转移成功， $z_{t+1} = y$ , 否则，状态转移失败，下一步的状态仍然保留在上一个状态， $z_{t+1} = z_t$ ;

重复以上步骤可以得到一个样本序列，该序列每个中的每一个状态都依赖于上一个状态，因此它构成一个马尔可夫链。

下面我们证明p(x)在上面的产生过程中满足细致平衡方程，因此得到的样本序列服从分布 $p(x)$ 。

证明如下：

假设 $x_1, x_2$ 是马尔可夫中的任意两个状态， 假设

                                                            $q(x_2|x_1) = q(x_1|x_2)$          （1）

并且不失一般性假设

$p^*(x_1) > p^*(x_2)$                                   （2）

那么我们有

$p(x_2|x_1) = q(x_2|x_1)A(x_2, x_1) = q(x_2|x_1)\frac{p^*(x_2)}{p^*(x_1)}$                  （3）

$p(x_1|x_2) = q(x_1|x_2)A(x_1, x_2) = q(x_2|x_1)$                               （4）

由公式（1），（3），（4）得，

$p(x_1|x_2)p^*(x_2) = p(x_2|x_1)p^*(x_1)$

因此

$p(x_1|x_2)p(x_2) = p(x_2|x_1)p(x_1)$

即目标概率p(x)满足细致平衡方程，即由状态 $x_2$ 跳转到 $x_1$ 的概率与由 $x_1$ 跳转到 $x_2$ 的概率相等，因此p(x)是转移概率的稳定分布。

最后，回顾一下梅特罗波利斯抽样的主要思想。首先构造一个马尔可夫链，接着证明p(x)满足其细致平衡方程，进而说明p(x)是该马尔可夫链的稳定分布。然后将抽样的过程看成是在马尔可夫链状态空间进行跳转的过程，跳转的候选状态由参考分布q(x)产生。最后 得到一个的跳转序列，该序列在每个状态x的停留时间与p(x)成比，即服从p(x)分布。

参考文献

1. pattern recognition and machine learning              Christopher M.Bishop   p537-542

2. machine learning a probabilistic perspective          Kevin P.Murphy    p596-600

3. bayesian reasoning and machine learning    David Barber   p531-533