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

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

該算法的名稱源於美國物理學家尼古拉斯·梅特羅波利斯^[1]與加拿大統計學家W·K·黑斯廷斯（英語：W. K. Hastings）。^[2]

算法

假設 $P(x)$ 為目標概率分布。梅特羅波利斯－黑斯廷斯算法的過程為：

初始化
1. 選定初始狀態 $x_{0}$ ；
2. 令 $t=0$ ；
迭代過程
1. 生成： 從某一容易抽樣的分布 $Q(x'|x_{t})$ 中隨機生成候選狀態 $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. 從 $[0,1]$ 的均勻分布中生成隨機數 $u$ ；
  2. 如 $u\leq A(x'|x)$ ，則接受該狀態，並令 $x_{t+1}=x'$ ；
  3. 如 $u>A(x'|x)$ ，則拒絕該狀態，並令 $x_{t+1}=x_{t}$ （複製原狀態）；
4. 增量：令 ${\textstyle t=t+1}$ ；

注釋

^ 該分布稱為提議分布（proposal distribution），當其對稱時（即滿足 $Q(x'|x)=Q(x|x')$ ），是梅特羅波利斯－黑斯廷斯算法的一類特例，稱為梅特羅波利斯算法（Metropolis algorithm）。

參考文獻

^ Metropolis, N.; Rosenbluth, A.W.; Rosenbluth, M.N.; Teller, A.H.; Teller, E. Equations of State Calculations by Fast Computing Machines. Journal of Chemical Physics. 1953, 21 (6): 1087–1092. Bibcode:1953JChPh..21.1087M. doi:10.1063/1.1699114.
^ Hastings, W.K. Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika. 1970, 57 (1): 97–109. JSTOR 2334940. Zbl 0219.65008. doi:10.1093/biomet/57.1.97.

Bernd A. Berg. Markov Chain Monte Carlo Simulations and Their Statistical Analysis. Singapore, World Scientific, 2004.
Siddhartha Chib and Edward Greenberg: "Understanding the Metropolis–Hastings Algorithm". American Statistician, 49(4), 327–335, 1995
David D. L. Minh and Do Le Minh. "Understanding the Hastings Algorithm." Communications in Statistics - Simulation and Computation, 44:2 332-349, 2015
Bolstad, William M. (2010) Understanding Computational Bayesian Statistics, John Wiley & Sons ISBN 0-470-04609-0

[3] 該分布稱為提議分布（proposal distribution），當其對稱時（即滿足 $Q(x'|x)=Q(x|x')$ ），是梅特羅波利斯－黑斯廷斯算法的一類特例，稱為梅特羅波利斯算法（Metropolis algorithm）。

[metropolis-1] Metropolis, N.; Rosenbluth, A.W.; Rosenbluth, M.N.; Teller, A.H.; Teller, E. Equations of State Calculations by Fast Computing Machines. Journal of Chemical Physics. 1953, 21 (6): 1087–1092. Bibcode:1953JChPh..21.1087M. doi:10.1063/1.1699114.

[Hastings-2] Hastings, W.K. Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika. 1970, 57 (1): 97–109. JSTOR 2334940. Zbl 0219.65008. doi:10.1093/biomet/57.1.97.

[1]

[2]

[註 1]