马尔可夫链蒙特卡罗 MCMC 是什么？用随机游走从复杂分布中采样

马尔可夫链蒙特卡罗（Markov Chain Monte Carlo，MCMC）是一类从复杂概率分布中抽取样本的方法。当一个概率分布复杂到无法直接从中抽样，甚至连它的归一化常数都算不出来时，马尔可夫链蒙特卡罗方法通过构造一个特殊的随机游走过程，让它长时间运行，最终得到近似服从目标分布的样本。它是贝叶斯统计中最重要的计算工具之一。

两个组成部分

蒙特卡罗方法：用随机抽样来近似计算的方法。比如要计算一个复杂分布下某个量的平均值，如果能从这个分布中抽出大量的样本，就可以直接用样本的平均值来近似。这个名字来自摩纳哥著名的赌城，取其随机的含义。马尔可夫链：一种随机过程，下一个状态只取决于当前的状态。在一定的条件下，马尔可夫链运行足够长的时间之后，处于各个状态的概率会稳定下来，不再随时间变化，这个稳定的分布叫作平稳分布。马尔可夫链蒙特卡罗的核心思想是：巧妙地设计一个马尔可夫链，让它的平稳分布正好等于我们想要采样的目标分布。这样，只要让这个链运行足够长的时间，它访问各个状态的频率就符合目标分布，链上的状态就可以当作目标分布的样本。

为什么它特别有用

在贝叶斯推断中，我们需要计算参数的后验分布，它等于先验乘以似然再除以一个归一化常数，而这个常数往往需要计算一个极其复杂的积分，无法求出。马尔可夫链蒙特卡罗方法的巧妙之处在于：它只需要知道分布的相对大小，也就是两个状态的概率之比，而在计算比值时，那个未知的归一化常数恰好被约掉了。因此，即使不知道归一化常数，也能从后验分布中采样。

代表性的算法

Metropolis 算法：1953 年由 Nicholas Metropolis、Arianna Rosenbluth、Marshall Rosenbluth、Augusta Teller 和 Edward Teller 在研究物理系统时提出。每一步，从当前位置随机地提出一个新的候选位置；如果候选位置的概率更高，就移动过去；如果更低，就以一定的概率移动过去，这个概率等于两者的概率之比，否则留在原地。1970 年，W. K. Hastings 把它推广到了更一般的、提议不对称的情况，称为 Metropolis-Hastings 算法。吉布斯采样：由 Stuart Geman 和 Donald Geman 在 1984 年用于图像复原问题。对于多个变量，每次只更新一个变量，在其他变量固定的条件下，直接从这个变量的条件分布中抽样，轮流更新所有的变量。它在主题模型等概率图模型中被广泛使用。哈密顿蒙特卡罗：借鉴物理学中的哈密顿动力学，利用分布的梯度信息，让每一步可以移动得更远、更有方向性，在高维问题中效率高得多。在此基础上改进的 NUTS 算法被 Stan 等概率编程工具采用。

使用时的注意事项

预热期：马尔可夫链从一个任意的起点出发，需要运行一段时间才能达到平稳分布，这段时间的样本应该丢弃。收敛诊断：很难确切地知道链是否已经收敛，常用的方法是从不同的起点运行多条链，比较它们的结果是否一致，比如计算 Gelman-Rubin 统计量。样本相关性：链上相邻的样本是相关的，并不是独立的，有效的样本数量比实际的样本数量少，有时会每隔若干步取一个样本。多峰分布：如果目标分布有多个相距很远的峰，链可能长时间困在其中一个峰附近，难以探索其他的峰。马尔可夫链蒙特卡罗方法被广泛用于贝叶斯统计、统计物理、计算生物学、计量经济学等领域，PyMC、Stan 等工具让研究者只需描述模型，就能自动进行采样。