梅特羅波利斯-黑斯廷斯演算法（Metropolis-Hastings algorithm）
/ meh-TROP-oh-lis HAY-stings /
有時你需要從一個只能算到相差一個未知縮放常數的分布取樣——貝氏後驗、物理裡的波茲曼分布——而在高維中直接取樣（反轉、拒絕）毫無希望。Metropolis-Hastings 用一個巧妙的裝置解決：它不直接對分布取樣，而是建一條「隨機漫步」，在空間裡遊蕩，長遠來看會「恰好按各區域的機率比例」造訪它們。把漫步的停留點收集起來，就是你的樣本。
迴圈如下，美在簡單。你在當前狀態 x。(1) 用某個隨機移動提議一個候選 y（例如從 x 做一小步高斯跳躍）。(2) 算接受比 alpha = min(1, [p(y) q(x|y)] / [p(x) q(y|x)])，其中 p 是目標（只需算到相差一個常數，因為未知常數在比值中抵消），q 是提議密度。(3) 抽一個均勻數 u；若 u < alpha 則「接受」、移到 y，否則「留在」x 並再記錄一次 x。重複。精妙之處在於 p 只以比值 p(y)/p(x) 出現，所以那個算不出來的正規化常數抵消了——你永遠不需要它。這條鏈被設計（透過「細緻平衡」）成其長遠分布恰好是目標 p；吉布斯取樣是其特例，一次從一個座標的精確條件分布更新它。
Metropolis-Hastings 於 1953 年為物理發明、再由 Hastings 推廣，徹底改變了貝氏統計與統計物理——它使「對複雜的高維分布取樣」這件事首度成為可能。但誠實不可或缺。樣本是「相關」的，不是獨立：連續狀態彼此靠近，所以有效的獨立樣本數遠少於鏈的長度，而 s/sqrt(N) 誤差棒太樂觀，除非你把自相關算進去。鏈需要一段「暖機」（burn-in）來忘掉任意的起點，之後樣本才有效，而調整提議步長很微妙——太小則爬行（接受率高但移動極小），太大則幾乎全被拒絕（卡住）。診斷鏈是否真正收斂確實困難，且永遠不能完全確定。
對雙峰目標 p(x) 正比於 e^(-(x^2-4)^2) 取樣。從 x = 0 起，提議 y = x + Normal(0, 1)。設 y = 1.8：算 p(1.8)/p(0)；若該比值超過一個均勻抽樣，就接受並移到 1.8，否則留在 0。重複數百萬次，產生的直方圖會吻合 p——即使 p 的正規化常數從未被計算。
一條被引導的隨機漫步，其長遠造訪比例吻合目標——不需正規化常數。
MCMC 樣本是「相關」的，所以天真的 s/sqrt(N) 誤差棒會高估你的精度——你必須把自相關算進去。鏈還需要暖機與謹慎的提議調整，而「它收斂了嗎？」這個問題確實難以確定地回答。