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

梅特羅波利斯－黑斯廷斯算法（英語：Metropolis–Hastings algorithm）是統計學與統計物理中的一種馬爾科夫蒙特卡洛（MCMC）方法，用於在難以直接採樣時從某一機率分布中抽取隨機樣本序列。

簡介

得到的序列可用於估計該機率分布或計算積分（如期望值）等。梅特羅波利斯－黑斯廷斯或其他MCMC算法一般用於從多變數（尤其是高維）分布中採樣。對於單變數分布而言，常會使用自適應判別採樣（adaptive rejection sampling）等其他能抽取獨立樣本的方法，而不會出現MCMC中樣本自相關的問題。

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

尼古拉斯·康斯坦丁·梅特羅波利斯介紹

尼古拉斯·康斯坦丁·梅特羅波利斯（英語：Nicholas Constantine Metropolis），美籍希臘裔物理學家。出生於美國芝加哥市。1936年、1941年分別獲芝加哥大學實驗物理學學士、博士學位。1943年由羅伯特·奧本海默招募，進入洛斯阿拉莫斯國家實驗室工作。他是曼哈頓計畫最早的科學家之一，協助恩里科·費米和愛德華·泰勒進行了世界上第一個核反應堆的研究。二戰結束後，他前往芝加哥大學，擔任助理教授。1948年返回洛斯阿拉莫斯國家實驗室，領導了有關電子計算機的理論部門的研究。該組於1952年設計並建造了計算機MANIAC I，並於1957年建造了MANIAC II。1957至1965年在芝加哥大學擔任物理教授。1965年再次回到洛斯阿拉莫斯國家實驗室，1980年獲得實驗室資深研究員稱號。

梅特羅波利斯最知名的貢獻，是他對蒙特卡洛方法和積分微分方程的研究。他於1953年首次提出的梅特羅波利斯–黑斯廷斯算法（Metropolis–Hastings algorithm）是蒙特卡洛方法中最重要的抽樣方法之一。

算法

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

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

初始化

1.

初始化

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

a.選定初始狀態；

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

b.令；

疊代過程

1.

疊代過程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f.接受或拒絕

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

g.增量 ：令；

馬爾可夫鏈蒙特卡洛

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

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

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

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