梅特罗波利斯-黑斯廷斯算法

梅特罗波利斯－黑斯廷斯算法（英語：Metropolis–Hastings algorithm）是统计学与统计物理中的一种马尔科夫蒙特卡洛（MCMC）方法，用于在难以直接采样时从某一概率分布中抽取随机样本序列。得到的序列可用于估计该概率分布或计算积分（如期望值）等。梅特罗波利斯－黑斯廷斯或其他MCMC算法一般用于从多变量（尤其是高维）分布中采样。对于单变量分布而言，常会使用自适应判别采样（adaptive rejection sampling）等其他能抽取独立样本的方法，而不会出现MCMC中样本自相关的问题。

该算法的名称源于美国物理学家尼古拉斯·梅特罗波利斯^[1]与加拿大统计学家W·K·黑斯廷斯（英语：W. K. Hastings）。^[2]

假设${\displaystyle P(x)}$为目标概率分布。梅特罗波利斯－黑斯廷斯算法的过程为：

1. 初始化
   1. 选定初始状态${\displaystyle x_{0}}$；
   2. 令${\displaystyle t=0}$；
2. 迭代过程
   1. 生成： 从某一容易抽样的分布${\displaystyle Q(x'|x_{t})}$中随机生成候选状态${\displaystyle x'}$；^{[註 1]}
   2. 计算： 计算是否采纳候选状态的概率${\textstyle A(x'|x)=\min \left(1,{\frac {P(x')}{P(x)}}{\frac {Q(x|x')}{Q(x'|x)}}\right)}$；
   3. 接受或拒绝
      1. 从${\displaystyle [0,1]}$的均匀分布中生成随机数${\displaystyle u}$；
      2. 如${\displaystyle u\leq A(x'|x)}$，则接受该状态，并令${\displaystyle x_{t+1}=x'}$；
      3. 如${\displaystyle u>A(x'|x)}$，则拒绝该状态，并令${\displaystyle x_{t+1}=x_{t}}$（复制原状态）；
   4. 增量：令${\textstyle t=t+1}$；

• Bernd A. Berg. Markov Chain Monte Carlo Simulations and Their Statistical Analysis. Singapore, World Scientific, 2004.
• Siddhartha Chib and Edward Greenberg: "Understanding the Metropolis–Hastings Algorithm". American Statistician, 49(4), 327–335, 1995
• David D. L. Minh and Do Le Minh. "Understanding the Hastings Algorithm." Communications in Statistics - Simulation and Computation, 44:2 332-349, 2015
• Bolstad, William M. (2010) Understanding Computational Bayesian Statistics, John Wiley & Sons ISBN 0-470-04609-0