馬可夫鏈蒙地卡羅

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

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

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

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

本方法的相關應用包括：貝葉斯統計、計算物理、計算生物學以及計算語言學。^{[1] [2]}

隨機遊走算法

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

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

基本原理

梅特羅波利斯-黑斯廷斯算法（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 }$的採樣。^[3]

基本步驟

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 次，則可得後驗樣本。根據後驗樣本可計算後驗分布的各階矩，進行相應的統計推斷。

參見

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