在介紹《Fast and Provably Good Seedings for K-means》時，作者使用MCMC採樣來近似 D2−sampling 的過程，下面我們來介紹一下MCMC算法。

Monte Carlo Approach

在介紹MCMC算法之前，我們先來看蒙特卡洛隨機模擬算法。

假設我們需要求解下面這個積分問題：

而這個 f(x) 的積分形式比較難求，我們可以通過數值模擬解法近似求解。常用的方法是蒙特卡洛算法：

式中的 q(x) 可以看作 x 在區間上的分佈，當我們使用 q(x) 採集足夠的樣本後，便可以使用均值來近似積分：

以上便是蒙特卡洛算法的核心思想，具體操作時就是需要考慮如何從給定的概率分佈 (x) 中採集足夠的樣本。下面我們來介紹兩種簡單的採樣算法。

採樣算法

CDF

假設我們想以 p(x) 的概率採集一些數據，

1. 我們可以先求出它的累積概率函數:
   
   F(x)=∫bap(x)d(x)   s.t.a<x<b
   
   2.然後使用均勻分佈產生一個樣本點 u
   
   u∼u(a,b)
   
   3.最後我們求解出反函數 F−1(u)
   
   x=F−1(u)
   
   4. x 便可以看作是按照 p(x) 採樣得到的樣本點

我們可以看一個正態分佈的例子：

左圖是概率密度函數PDF- p(x) ，右圖是對應的累計概率密度函數CDF- F(x) .
我們先隨機生成一個樣本點 u=0.8413 ， F−1(u)=1 ，所以1就是相應的樣本點。
直覺上看，我們隨機選擇 (0,1) 之間的點，大部分點都i會落在區間 (0.2,0.8) 之間，而與之對應的 F−1(x) 則大部分落在 (−1,1) 之間，這也對應了正態分佈在 (−1,1) 之間概率密度較大的事實。

這種方法只適用於簡單的分佈。

Markov Chain

對於某一些馬爾科夫鏈，它能夠收斂到一個平穩分佈 π(x) ，即：

當馬爾可夫鏈在第 n 個狀態收斂之後，從 n+1 往後的狀態都可以看作是平穩分佈 π 的採樣點。
所以爲了構造一個以 π 爲平穩分佈的馬爾科夫鏈，我們需要滿足細緻平衡條件:

Metropolis Sampler

M算法要求提案概率 q(x) 是對稱的。

Metropolis-Hastings Sampler

MH算法加入了 α ，不要求提案概率是對稱的，也能滿足細緻平衡條件。

這兩個算法的區別在於提案概率是否是對稱的。