採樣方法

一，採樣方法
1，接受-拒絕抽樣
2，重要性抽樣
3，MCMC（馬爾可夫鏈蒙特卡洛方法）：metropolis-hasting算法和它的特例Gibbs採樣算法

一，隨機模擬的基本思想
1，求不規則面積:
a,分割計算
b，我們抓一把黃豆，把它們均勻地鋪在矩形區域，如果我們知道黃豆的總個數S，那麼只要我們數數位於不規則區域M中的黃豆個數S1，那麼我們就可以求出M的面積： M=S1∗R/S 。

2，求解定積分
∫baf(x)dx
採用蒙特卡洛積分，即把上述式子改寫爲：
∫baf(x)∗g(x)/g(x)dx=∫ba(1/g(x))∗f(x)∗g(x)dx
把 f(x)g(x) 當成一個函數，g(x)看出[a,b]上的一個概率分佈
抽取n個樣本後，可知 ∑n1[f(xi)/g(xi)]/n

二，常見的抽樣方法
2.0，直接抽樣法
2.1，接受-拒絕抽樣
這個算法的基本思想是：我們需要對一個分佈f(x)進行採樣，但是卻很難直接進行採樣，所以我們想通過另外一個容易採樣的分佈g(x)的樣本，用某種機制去除掉一些樣本，從而使得剩下的樣本就是來自與所求分佈f(x)的樣本。
條件：
1）對於任何一個x，有 f(x)≤Mg(x) ;
2) g(x)容易採樣；
3) g(x)最好在形狀上比較接近f(x)。
採樣過程：
1. 對於g(x)進行採樣得到一個樣本 xi,xi∼g(x) ;
2. 對於均勻分佈採樣 ui∼U(a,b) ;
3. 如果 ui≤f(x)Mg(x) , 那麼認爲 xi 是有效的樣本；否則捨棄該樣本； （# 這個步驟充分體現了這個方法的名字：接受-拒絕）

1. 反覆重複步驟1~3，直到所需樣本達到要求爲止。
   

2.2重要性採樣
∫f(x)dx=∫f(x)g(x)g(x)dx
根據上述等式：
抽樣步驟如下：
1. 選擇一個容易抽樣的分佈g(x), 從g(x)中抽取N個樣本；
2. 計算 1N∑Nif(x)g(x) ,從而得到近似解。

2.3,MCMC抽樣方法
MCMC方法的基本思想是：如果我們能構造一個轉移矩陣爲P的馬氏鏈，使得該馬氏鏈的平穩分佈恰好是p(x), 那麼我們從任何一個初始狀態 x0 出發沿着馬氏鏈轉移, 得到一個轉移序列 x0,x1,x...xn,xn+1... ,， 如果馬氏鏈在第n步已經收斂了，於是我們就得到了 π(x) 的樣本 xn,xn+1⋯ 。

背景知識：
馬氏鏈定理
細緻平穩條件；如果非週期馬氏鏈的轉移矩陣P和分佈 π(x) 滿足：

構造滿足條件

假設我們已經有一個轉移矩陣爲Q馬氏鏈(q(i,j)表示從狀態i轉移到狀態j的概率，也可以寫爲q(j|i)或者q(i→j)), 顯然，通常情況下 p(i)q(i,j)≠p(j)q(j,i)(∗)

構造一個a(i,j),根據對稱性
a(i,j)=p(j)q(j,i) a(j,i)=p(i)q(i,j)

使得 p(i)q(i,j)a(i,j)=p(j)q(j,i)a(j,i)
此時p(i)爲平穩分佈， α(i,j)稱爲接受率
理解思路：物理意義可以理解爲在原來的馬氏鏈上，從狀態i 以q(i,j)的概率轉跳轉到狀態j 的時候，我們以α(i,j) 的概率接受這個轉移，於是得到新的馬氏鏈Q′的轉移概率爲q(i,j)α(i,j)。

MCMC採樣算法
採樣概率p(x)的算法，假設我們已經又一個轉移矩陣Q(對應元素q(i,j))

採樣思路藉助了重要性採樣的思路
2.3.2，Metropolis-Hastings算法
MCMC採樣的缺陷：
馬氏鏈Q在轉移的過程中的接受率α(i,j) 可能偏小，這樣採樣過程中馬氏鏈容易原地踏步，拒絕大量的跳轉，這使得馬氏鏈遍歷所有的狀態空間要花費太長的時間，收斂到平穩分佈p(x) 的速度太慢。
優化：
思路很簡單，將a(i,j),a(j,i)同時擴大一定的倍數，使得
maxa(i,j),a(j,i)=1
所以得出 a(i,j)=min{p(j)q(j,i)p(i)q(i,j),1}

2.3.3,Gibbs sampling算法
二維：
gibbs採樣只對z是高維（2維以上）情況有效。通過固定某個維度 xi ,然後通過其他維度 x⃗ −i 的值來抽樣該維度的值

由於x座標相同的點 A(x1,y1),B(x1,y2) ,我們可以發現

同理，可知道，兩個點無論是平行於x,y軸，兩個點之間的轉移概率，那麼兩個點之間的轉移滿足細緻平穩條件。
從而根據下圖，構造轉移概率矩陣：

構造平面上任意兩點之間的轉移概率矩陣Q：

可得到二維的細緻平穩條件：
對平面上的任意兩點X,Y,滿足細緻平穩條件：
P(X)Q(X→Y)=P(Y)Q(Y→X)

從轉移概率矩陣我們可得轉移過程如下：

2.1步是從 (x0,y0)轉移到(x0,y1)，滿足Q(A→B)=p(yB|x1)的細緻平穩條件，所以會收斂到平穩分佈；
2.2步是從(x0,y1)轉移到(x1,y1)，也會收斂到平穩分佈。
也就是整個第2步是從(x0,y0)轉移到(x1,y1)，滿足細緻平穩條件，在循環多次後會收斂於平穩分佈，
採樣得到的 (xn,yn),(xn+1,yn+1)…就是平穩分佈的樣本
高維：
高維的原理和二維基本一致：


Gibbs 採樣的相關性和獨立性
1.馬爾科夫鏈中的連續的樣本是高度相關的
2.吉布斯採樣可以看做是M-H算法的一個特例，即接受率α=1的情況
3.吉布斯採樣收斂的判斷
（1）圖形方法
（2）蒙特卡洛誤差
（3）Gelman-Rubin方法

時間序列基礎