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

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

提議分佈Q表示隨機遊走下一狀態的可能位置

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

算法

假設 為目標概率分佈。梅特羅波利斯-黑斯廷斯算法的過程為:

  1. 初始化
    1. 選定初始狀態 
    2.  
  2. 迭代過程
    1. 生成: 從某一容易抽樣的分佈 中隨機生成候選狀態 [註 1]
    2. 計算: 計算是否採納候選狀態的概率 
    3. 接受或拒絕
      1.  的均勻分佈中生成隨機數 
      2.  ,則接受該狀態,並令 
      3.  ,則拒絕該狀態,並令 (複製原狀態);
    4. 增量: 

註釋

  1. ^ 該分佈稱為提議分佈(proposal distribution),當其對稱時(即滿足 ),是梅特羅波利斯-黑斯廷斯算法的一類特例,稱為梅特羅波利斯算法(Metropolis algorithm)。

參考文獻

  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. 
  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. 
  • 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