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

梅特羅波利斯－黑斯廷斯算法（英語：Metropolis–Hastings algorithm）是統計學與統計物理中的一種馬爾科夫蒙特卡洛（MCMC）方法，用於在難以直接採樣時從某一概率分布中抽取隨機樣本序列。得到的序列可用於估計該概率分布或計算積分（如期望值）等。梅特羅波利斯－黑斯廷斯或其他MCMC算法一般用於從多變量（尤其是高維）分布中採樣。對於單變量分布而言，常會使用自適應判別採樣（adaptive rejection sampling）等其他能抽取獨立樣本的方法，而不會出現MCMC中樣本自相關的問題。

提議分布Q表示隨機漫步下一狀態的可能位置

該算法的名稱源於美國物理學家尼古拉斯·梅特羅波利斯^[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}$；