# 背景
貝葉斯統(tǒng)計推斷是一個非常*藝術(shù)*的東西，他的先驗結(jié)果（prior knowledge）是一種專家的經(jīng)驗，而**貝葉斯公式**給出的后驗分布是貝葉斯推斷的基本工具。每個大學生都應該學過數(shù)理統(tǒng)計，其中提及的貝葉斯統(tǒng)計推斷都是一些基于簡單先驗和簡單后驗的結(jié)果。
但當我們一旦碰到復雜的先驗（比如高維參數(shù)又沾、復雜先驗分布），我們用貝葉斯公式得出的后驗分布將變得非常復雜熙卡，在計算上會非常困難杖刷。為此，先人提出了**MCMC算法**方便我們可以對任何后驗分布進行計算或推斷驳癌。其思想就是其名字：兩個MC滑燃。
第一個MC: Monte Carlo(蒙特卡洛)。這個簡單來說是讓我們使用隨機數(shù)（隨機抽樣）來解決計算問題颓鲜。在MCMC中意味著：后驗分布作為一個隨機樣本生成器不瓶，我們利用它來生成樣本(simulation)，然后通過這些樣本對一些感興趣的計算問題（特征數(shù)灾杰，預測）進行估計蚊丐。
第二個MC：Markov Chain(馬爾科夫鏈)。第二個MC是這個方法的關(guān)鍵艳吠，因為我們在第一個MC中看到麦备，我們需要利用**后驗分布**生成隨機樣本，但后驗分布太復雜昭娩，一些package中根本沒有相應的隨機數(shù)生成函數(shù)（如`rnorm(),rbinom()`）怎么辦凛篙？答案是我們可以利用Markov Chain的**平穩(wěn)分布**這個概念實現(xiàn)對復雜后驗分布的抽樣。
# Markov Chain
為了能順利闡述MCMC算法栏渺，這里就簡單地講一下所涉及到的馬爾科夫鏈概念呛梆。因為都是我個人的理解，這里所講不敢說都是正確的磕诊，希望各位童鞋能夠獨立思考填物。
## 1.什么是Markov Chain
隨機過程$\{X_n\},X_n$的狀態(tài)空間為有限集或可列集纹腌，比如當$X_n=i$,就稱過程在n處于狀態(tài)i。
定義：如果對任何一列狀態(tài)$i_0,i_1,...,i_{n-1},i,j$滞磺，及對任何n≥0升薯，隨機過程$\{X_n\}$滿足Markov性質(zhì)：
$$P\{X_{n+1}=j|X_0=i_0,...X_{n-1}=i_{n-1},X_n=i\}\\=P\{X_{n+1}=j|X_n=i\}$$
**轉(zhuǎn)移概率**
$P\{x_{n+1}=j|X_n=i\}$成為Markov鏈的一步轉(zhuǎn)移概率$P_{ij}^{n,n+1}$,當這個概率與n無關(guān),則記之為$P_{ij}$
**轉(zhuǎn)移概率矩陣P**
這個矩陣的元素就是一步轉(zhuǎn)移概率$P_{ij}$
**結(jié)論**
一個Markov鏈可以由它的初始狀態(tài)以及轉(zhuǎn)移概率矩陣P完全確定。（證明略击困，自行百度或翻書）
## 2.n步轉(zhuǎn)移概率
所謂n步轉(zhuǎn)移概率就是從狀態(tài)i走n步正好到狀態(tài)j的概率涎劈，我們記為$P_{ij}^{(n)}$。
利用概率分割的思想阅茶，由基礎(chǔ)概率論中**全概率公式**可以得到$$P_{ij}^{(n)}=\Sigma_{k=0}^{\infty}P_{ik}P_{kj}^{(n-1)}$$ 寫成矩陣形式就是$$P^{(n)}=P\times P^{(n-1)}$$
進一步推廣蛛枚，我們就推出了著名的Chapman-Kolmogorov方程：$$P_{ij}^{(n+m)}=\Sigma_{k=0}^{\infty}P_{ik}^{(n)}P_{kj}^{(m)}$$寫成矩陣形式就是$$P^{(m+n)}=P^{(m)}\times P^{(n)}$$
## 3.Markov鏈的極限定理和平穩(wěn)分布
現(xiàn)在我們已經(jīng)有了n步轉(zhuǎn)移概率的概念，一個很簡單的想法就是如果n趨向無窮會怎么樣脸哀？這個問題也是后面**極限分布**以及**平穩(wěn)分布**的來源蹦浦，更是MCMC算法中第二個MC的關(guān)鍵。
要回答這個問題首先要掌握幾個關(guān)鍵概念企蹭，我先列出來白筹，如果不熟悉的可以自行百度或翻書：
1. 互達性($i \leftrightarrow j$)
2. 周期性(d(i))
3. 常返與瞬過($f_{ii}=1$)
4. 常返時($\T_i$)
### 3.1互達性智末、周期性
幾個重要結(jié)論（證明略谅摄，自行百度，或者call me）
1. $i \leftrightarrow j,\Rightarrow d(i)=d(j)$
2. $若存在d(i)<\infty,則存在N系馆，對所有n>N,有P_{ii}^{(nd(i))}>0$
3. $P_{ji}^{(m)}>0,\Rightarrow 存在N送漠，對所有n>N,有P_{ii}^{(m+nd(i))}>0$
4. 對于非周期不可約Markov鏈的轉(zhuǎn)移概率矩陣P，存在N由蘑，當n≥N時闽寡，$P^{(n)}>0$
### 3.2常返、瞬過尼酿、常返時
1. 引入重要概率$f_{ij}^{(n)}$表示從i出發(fā)在n步**首次**到達j的概率爷狈，我們約定$f_{ii}^{(0)}=0$
2. $定義f_{ij}=\Sigma_{n=1}^{\infty}f_{ij}^{(n)}$表示從i出發(fā)**最終**到j(luò)的概率。
3. $定義：如果f_{ii}=1,則狀態(tài)i是常返的裳擎，否則是瞬過的$
4. $我們記T_i為首次返回i的步長,且\mu_i=ET_i$
5. $若\mu_i=\infty,則稱狀態(tài)i是零常返涎永，否則正常返$
### 3.3 極限定理
是時候回答上面那個問題了！（摘自網(wǎng)絡(luò)共享PPT）
另外對于一個正常返鹿响、非周期的狀態(tài)(也稱為遍歷ergodic)羡微，我們有結(jié)論:$$對所有i\leftrightarrow j,有l(wèi)imP_{ji}^{(n)}=limP_{ii}^{(n)}=\frac{1}{\mu_i}$$
>到這里，我們可以想象了惶我，n步轉(zhuǎn)移概率矩陣最終的極限形式應該是由相同的行向量組成的Ｂ杈蟆！绸贡！我們把那個行向量稱為極限概率分布盯蝴。? 但是毅哗，問題還沒完，要計算極限概率结洼，就要根據(jù)極限定理黎做，求出很多東西（如$f_{ii}^{(n)}$），實際中并不方便松忍。所以蒸殿，我們要引入*平穩(wěn)分布*這個概念。最關(guān)鍵的部分來了Ｃ汀：晁！摊溶！
### 3.3 平穩(wěn)分布
什么是平穩(wěn)分布爬骤？它和求極限概率分布有什么關(guān)系呢？
定義：Markov鏈有轉(zhuǎn)移概率矩陣P莫换，如果有一個概率分布$\{\pi_i \}滿足\pi_j =\Sigma_{i=0}^{\infty}\pi_i P_{ij}$,則稱為這個Markov鏈的平穩(wěn)分布霞玄。這個定義用矩陣形式寫出來就是π*P=π.
>這個定義內(nèi)容很豐富：如果一個過程的初始狀態(tài)$X_0$有平穩(wěn)分布π,我們可以知道對所有n，$X_n$有相同的分布π拉岁。再根據(jù)Markov性質(zhì)可以得到坷剧，對任何k，有$X_n,X_{n+1},...,X_{n+k}$的聯(lián)合分布不依賴于n喊暖，顯然這個過程是嚴格平穩(wěn)的惫企，平穩(wěn)分布也由此得名！陵叽！
**重要定理**
若一個markov鏈中所有的狀態(tài)都是遍歷的狞尔，則對所有i,j有$limP_{ij}^{(n)}=\pi_j存在，且\pi=\{\pi_j,j≥0\}就是平穩(wěn)分布$巩掺。反之偏序，拖一個不可約Markov鏈只存在一個平穩(wěn)分布，且這個Markov鏈的所有狀態(tài)都是遍歷的胖替，則這個平穩(wěn)分布就是該Markov鏈的極限概率分布研儒。$$limP_{ij}^{(n)}=\pi_j$$
>上面這條定理就給出了通過求平穩(wěn)分布來求Markov鏈極限概率分布的簡單方法。到這里我對第二個MC的解讀也就結(jié)束了刊殉。下一期我們就要開始具體講講怎么應用MCMC算法對后驗分布進行抽樣和推斷殉摔。
