馬可夫鏈蒙地卡羅

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目可能需要清理，以符合維基百科品質標準。 (2023年5月30日) 請儘量協助改善這篇條目，詳情請參見討論頁。 此條目翻譯品質不佳。 (2023年5月30日) 翻譯者可能不熟悉中文或原文語言，也可能使用了機器翻譯。請協助翻譯本條目或重新編寫，並注意避免翻譯腔的問題。明顯拙劣的翻譯請改掛{{d|G13}}提交刪除。

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

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

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

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

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

Jeff Gill. Bayesian methods: a social and behavioral sciences approach Second Edition. London: Chapman and Hall/CRC. 2008 [2012-02-07]. ISBN 1-58488-562-9. （原始內容存檔於2009-05-23）.  引文格式1維護：冗餘文字 (link) </ref> and Robert & Casella.^[1]

馬氏鏈性質決定了下一個方位取決於當前狀態和隨機變數。這樣的性質決定了最終所有的空間將被覆蓋但是卻需要花費較長時間。下面給出MCMC方法：

• Metropolis–Hastings演算法：給出預見密度和回絕按照給出方向前進的方法。
• 吉布斯採樣：取目標區域所有的條件分布樣本。
• 平滑取樣
• 多重實驗Metropolis：Metropolis–Hastings演算法的改良版本。

設非週期正常返的馬可夫鏈的平穩分布為${\displaystyle \pi }$，${\displaystyle S}$為馬可夫鏈的狀態，對於任意${\displaystyle S}$上有界函數${\displaystyle h}$有： ${\displaystyle P(\lim _{n\rightarrow \inf }{\frac {1}{n}}\sum _{k=0}^{n}h(X_{k})=\sum _{x\in S}\pi (x)h(x))=1}$，也就是說，該馬可夫鏈在取的變數${\displaystyle X_{k}}$在${\displaystyle n}$比較大時會趨向於服從機率分布${\displaystyle \pi }$。

在設計一個馬可夫鏈滿足細緻平衡的條件下，對馬爾科夫鏈的類比就可以看作對機率分布${\displaystyle \pi }$的採樣。^[2]

MCMC方法是使用馬爾科夫鏈的蒙地卡羅積分，其基本思想是：構造一條Markov鏈使其平穩分布為待估參數的事後分布${\displaystyle \pi (x)}$，通過這條馬爾科夫鏈產生事後分布的樣本，並基於馬爾科夫鏈達到平穩分布時的樣本（有效樣本）進行蒙特卡羅積分。設${\displaystyle n}$為產生的總樣本數，${\displaystyle m}$為Markov鏈達到平穩時的樣本數則MCMC方法的基本思路可概括為：

• 構造Markov鏈。構造一條Markov鏈，給定馬爾科夫鏈狀態轉移矩陣${\displaystyle Q}$，使其收斂到平穩分布${\displaystyle \pi (x)}$；
• 產生樣本：從初始狀態${\displaystyle x_{0}\sim p_{0}}$出發，利用從條件機率分布${\displaystyle Q(x|x_{t})}$生成樣本，並通過轉移條件判斷是否轉移，通過${\displaystyle m}$次更新達到平穩，此後生成的即為${\displaystyle \pi (x)}$的樣本，我們記為${\displaystyle x^{(1)},\cdots ,x^{(n)}}$；
• 蒙特卡羅積分。任一函數${\displaystyle f(x)}$的期望值估計為：${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}f(x^{(i)})}$

在採用MCMC方法時馬爾科夫鏈轉移核的構造至關重要，不同的轉移核構造方法將產生不同的MCMC方法，目前常用的MCMC方法主要有兩種Gibbs抽樣和Metropolis-Hastings演算法。

l Gibbs '抽樣'

Gibbs抽樣是現實中最簡單應用最廣泛的MCMC方法，由Geman最初命名提出其基礎思路如下：

給定任意的初始向量；

從中抽取樣本

從中抽取樣本

…

從中抽取樣本

…

從中抽取樣本

至此，完成的轉移。經過n次迭代，可得後驗樣本。根據後驗樣本可計算事後分布的各階矩，進行相應的統計推論。

• Metropolis-Hastings '演算法'

Metropolis-Hastings演算法是較早出現且比較一般化的MCMC方法，最初由Metropolis等人在1953年提出之後由Hastings對其加以推廣形成了，Metropolis-Hastings方法。該方法的基本思路是：選擇一轉移函數和初始值，若第次迭代開始時的參數值為

，則第次迭代過程為：

• 從中抽取一個備選值

• 計算接受機率

• 以機率，置，以機率，置；
• 重複i –iii 次，則可得後驗樣本。根據後驗樣本可計算事後分布的各階矩，進行相應的統計推論。

• 貝葉斯推理
• 圖模式
• 馬可夫鏈
• 馬可夫邏輯網路

• MCMC sampling and other methods in a basic overview, by Alexander Mantzaris
• Visual demonstration of MCMC sampling methods (Java applet) （頁面存檔備份，存於網際網路檔案館）, by Laird Breyer
• A Toy Example of MCMC sampling, by Zhiyuan Weng
• MCL - a cluster algorithm for graphs （頁面存檔備份，存於網際網路檔案館）, by Stijn van Dongen