梅特羅波利斯-黑斯廷斯演算法（Metropolis-Hastings algorithm）
/ meh-TROP-oh-lis HAY-stings /
你常常能把後驗寫到差一個正規化常數——你知道一個正比於密度的函數——但那個常數本身是個沒指望的積分，所以你無法直接抽樣。梅特羅波利斯-黑斯廷斯是那條巧妙的逃生路：它在可能值的空間裡建構一場隨機漫步，只要你讓它遊蕩得夠久，就會恰好按目標分布所說的頻率造訪每個區域。你從不需要那個正規化常數，因為出現的只有密度的「比值」，常數會被約掉。
它是一種馬可夫鏈蒙地卡羅（MCMC）方法，迴圈很短。從目前狀態 x，依某個提議分布 q(y given x) 提出一個候選 y。算接受比 alpha = min(1, [pi(y) q(x given y)] / [pi(x) q(y given x)])，其中 pi 是只知道差一個常數的目標密度——注意 pi 只以比值 pi(y)/pi(x) 出現，所以那個未知常數消失了。以機率 alpha 移到 y；否則留在 x 並再記錄一次 x。重複。精妙之處在接受規則：它被設計成讓鏈對 pi 滿足細緻平衡，這迫使 pi 成為鏈的平穩分布，於是長期待在任何區域的時間比例都與 pi 相符。
丟掉開頭一段「暖機」（鏈忘掉它任意起點所需的時間）之後，剩下的狀態就是目標的樣本，你把它們當成蒙地卡羅抽樣來用。這一個點子解鎖了現代貝氏統計：它讓你能對沒有共軛形式、沒有封閉積分的後驗抽樣。不過誠實的提醒是真的。這些樣本是相關的、不是獨立的，所以有效樣本數比原始計數小。鏈可能混合得慢，或卡在某一個峰，所以調校提議（別太怯懦、別太大膽）極其重要，而你必須永遠檢查收斂——一條鏈可能看起來安定了卻是錯的。
從一個長得像兩座小丘的目標抽樣。從任何地方開始；每一步提議一個小小的隨機跳躍。若提議的點目標密度較高，就一律移過去；若較低，只以等於密度比的機率移過去（所以你有時也會往下爬）。經過數千步，這個漫步者待在每座丘的時間與其質量成比例——把造訪過的點畫成直方圖，就重現出那兩座丘的形狀。
出現的只有密度比值，所以那個未知的正規化常數被約掉，永遠不必去算。
MCMC 的樣本是相關的，鏈需要暖機；一條看起來收斂的鏈仍可能卡在某一個峰，所以永遠要檢查混合與收斂，而非信任單次執行。