马尔可夫链蒙特卡洛

马尔可夫链蒙特卡洛（MCMC）是一类计算方法，通过构造以目标概率分布为平稳分布的马尔可夫链，从目标分布中采样。沿着链生成的样本用于近似期望值及其他与分布有关的量。与基于统计独立性的普通蒙特卡洛采样不同，MCMC 通常产生相互依赖的观测值。当直接采样较为困难，但能够计算目标密度与某个未知归一化常数的乘积时，这种方法尤其有用。(stat.umn.edu)

数学基础

马尔可夫链满足马尔可夫性质：给定当前状态后，下一状态的分布不依赖于更早的状态。MCMC 算法规定一个转移核 $K(x,A)$ ，表示从状态 $x$ 转移到集合 $A$ 中的概率。目标分布 $\pi$ 的不变性意味着

\pi(A)=\int K(x,A)\,\pi(dx).

因此，如果某个状态已经服从分布 $\pi$ ，应用该转移后，其分布仍然保持不变。这并不意味着从任意点初始化的链会立即产生服从目标分布的样本。(stat.umn.edu)

一种常见的构造方式是使链满足细致平衡，在离散状态空间中表示为

\pi(x)K(x,y)=\pi(y)K(y,x).

细致平衡蕴含不变性，但并非必要条件：不可逆的链也可以保持目标分布不变。要获得一致估计，需要适当的可达性和常返性条件；要使状态分布收敛，还需要排除持续周期性的条件。仅仅具有正确的不变分布，并不能保证链在有限次运行中表现良好。(stat.umn.edu)

对于可积函数 $f$ ，MCMC 使用下式估计其期望值：

\widehat{\mu}_N=\frac{1}{N}\sum_{t=1}^{N}f(X_t), \qquad \mu=\int f(x)\,\pi(dx).

在适当的遍历性条件下，马尔可夫链版本的大数定律保证这一平均值收敛到 $\mu$ 。因此，该方法将一个可能难以求解的积分问题转化为模拟问题。(stat.umn.edu)

主要算法

**梅特罗波利斯–黑斯廷斯算法**从提议密度 $q(y\mid x)$ 中生成候选状态 $y$ ，并以如下概率接受它：

\alpha(x,y)= \min\!\left( 1,\frac{\pi(y)q(x\mid y)} {\pi(x)q(y\mid x)} \right).

如果候选状态被拒绝，下一状态仍为 $x$ ；重复出现的状态也是样本的一部分，并不是应当删除的失败观测。比值中的 $\pi$ 的未知归一化常数会被约去。对于对称提议，提议密度项也会约去，从而得到梅特罗波利斯接受规则。随机游走提议在当前状态上添加随机扰动，扰动尺度对效率有很大影响。(arxiv.org)

**吉布斯采样**通过从给定其余坐标时的条件分布中采样，更新单个坐标或坐标块。每次更新都会保持联合目标分布不变。当这些条件分布易于处理时，吉布斯采样十分方便，不过坐标之间的强依赖关系可能会妨碍对状态空间的探索。(arxiv.org)

**哈密顿蒙特卡洛（HMC）**为连续参数引入辅助动量变量，并利用哈密顿力学提出状态转移。对数密度的梯度引导轨迹，而梅特罗波利斯校正则用于修正数值积分误差。HMC 可以进行长距离移动，而不会表现出随机游走提议所特有的扩散行为。无掉头采样器会自适应地确定轨迹长度。这些方法要求满足适当的可微性条件，且不能直接更新离散参数。(mc-stan.org)

统计应用

在贝叶斯推断中，后验分布满足

p(\theta\mid y)\propto p(y\mid\theta)\,p(\theta),

其中 $p(y\mid\theta)$ 是似然函数， $p(\theta)$ 是先验分布。MCMC 无须显式计算归一化积分，就能从这一后验分布中采样。即使无法进行解析积分，后验样本也可用于估计均值、概率及其他概括性统计量。模拟样本量与观测数据点的数量是不同的：增加迭代次数提高的是计算精度，而不是观测所提供的信息量。(stat.umn.edu)

在统计力学中，相关方法用于对相互作用粒子的构型进行采样，并估计平衡性质。链的更新只是计算手段，不必代表系统实际的物理运动。(osti.gov)

精度、诊断与局限性

样本之间的依赖关系会改变估计的不确定性。当适用的中心极限定理成立时，均值估计的不确定性既取决于所估计量在目标分布下的方差，也取决于不同迭代之间的相关性。对于自相关系数 $\rho_k$ 可求和的平稳标量序列，其有效样本量通常表示为

N_{\mathrm{eff}} =\frac{N}{1+2\sum_{k=1}^{\infty}\rho_k}.

正自相关通常会降低有效样本量；负自相关则可能使其超过实际抽样次数。有效样本量针对的是具体的待估计量，而不是一次运行所具有的普遍属性。蒙特卡洛标准误衡量的是模拟的不确定性，而不是统计模型下参数的不确定性。(mc-stan.org)

可以丢弃初始的一段样本，将其作为烧入期或预热期。自适应采样器也会利用预热期调整转移参数。丢弃初始样本本身并不能证明已经收敛。多链比较（包括 $\widehat{R}$ 诊断）以及有效样本量可以提供有关采样表现的证据，但无法保证所有重要区域都已得到探索。(stat.umn.edu)

提议尺度不合适、坐标之间依赖过强，或不同模态相互分离，都可能导致探索缓慢。因此，即使一条链在数学上有效，在实际可用的计算预算内也可能产生误导性估计。仅凭高接受率并不能证明效率高：极小的移动可能频繁被接受，却几乎没有探索目标分布。(arxiv.org)

历史发展

1953 年，尼古拉斯·梅特罗波利斯、阿里安娜·罗森布卢斯、马歇尔·罗森布卢斯、奥古斯塔·泰勒和爱德华·泰勒发表了一项影响深远的工作，提出了一种用于相互作用粒子相关计算的采样程序。1970 年，W. K. 黑斯廷斯发表了这一方法的推广形式，使其能够适用于更广泛的提议机制，并给出了相关理论及对蒙特卡洛误差评估的讨论。这些发展奠定了如今称为梅特罗波利斯–黑斯廷斯算法的方法的基础。(osti.gov)