梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

簡介

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

該算法的名稱源於美國物理學家尼古拉斯·梅特羅波利斯與加拿大統計學家W·K·黑斯廷斯。

算法

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

假設為目標機率分布。梅特羅波利斯－黑斯廷斯算法的過程為：

1.初始化：

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

選定初始狀態；令；

2.疊代過程:

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

生成：從某一容易抽樣的分布中隨機生成候選狀態；

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

計算：計算是否採納候選狀態的機率；

接受或拒絕：

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

從的均勻分布中生成隨機數；

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

如，則接受該狀態，並令；

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

如，則拒絕該狀態，並令（複製原狀態）；

梅特羅波利斯－黑斯廷斯算法[梅特羅波利斯－黑斯廷斯算法]

增量：令.

馬爾科夫蒙特卡洛

馬爾科夫蒙特卡洛（英語：Markov chain Monte Carlo，MCMC）方法（含 隨機遊走蒙特卡洛方法）是一組用馬氏鏈從隨機分布取樣的算法，之前步驟的作為底本。步數越多，結果越好。

創建一個具有期望屬性的馬氏鏈並非難事，難的是如何決定通過多少步可以達到在許可誤差內的穩定分布。一個好的馬氏鏈具有 快速混合——從開始階段迅速獲得的一個穩定狀態——請參考馬氏鏈最大時間。

因於初始樣本，最常見的MCMC取樣只能近似得到分布。複雜的MCMC改進算法如過往耦合，但是會消耗更多的計算資源和時間。

典型用法是模擬一個隨機行走的行人來進行路徑最佳化等。每一步都算作是一個狀態。而統計經過次數最多的地方將在下一步中更有可能為目的地。馬氏蒙特卡洛方法是一種結合了蒙特卡羅法的解決方案。但不同於以往的蒙特卡洛integration是統計獨立的，MCMC中的是 統計相關的。

本方法的相關套用包括：貝葉斯統計、計算物理、計算生物以及計算語言學，此外還有Gill先生的一些著作。

參見

•貝葉斯推理