背景知識
隨機模擬也可以叫做蒙特卡羅模擬(Monte Carlo Simulation)。這個方法的發(fā)展始于20世紀40年代，和原子彈制造的曼哈頓計劃密切相關(guān)，當時的幾個大牛，包括烏拉姆、馮.諾依曼、費米、費曼、Nicholas Metropolis， 在美國洛斯阿拉莫斯國家實驗室研究裂變物質(zhì)的中子連鎖反應(yīng)的時候，開始使用統(tǒng)計模擬的方法,并在最早的計算機上進行編程實現(xiàn)。
蒙特卡洛數(shù)值積分
如果我們要求??(??)的積分，可化成記
，
為x的概率密度函數(shù)，在[a,b]區(qū)間內(nèi)取n個樣本[x1,x2,x3....xn]，則
蒙特卡洛數(shù)值積分將積分的計算轉(zhuǎn)化為期望的計算，進而可以用統(tǒng)計量來得到。
然而有一個重要的問題——怎么在給定的區(qū)間內(nèi)采樣？
采樣就是給定一個概率分布，根據(jù)該分布從樣本空間中生成樣本。
比如你可以通過拋硬幣近似完成對的0-1分布的采樣。再舉個最簡單的通過計算機程序?qū)Φ途S離散樣本空間進行采樣的例子，比如一維變量X取值的樣本空間為{1,2,3}，且取1,2,3三個值的概率分別為
。那么這時候你要如何從這個分布中進行采樣？我想大多數(shù)人自己都寫過這樣簡單的程序，首先根據(jù)各離散取值的概率大小對[0,1]區(qū)間進行等比例劃分，如劃分為[0,0.5],[0,5,0.75],[0.75,1]這三個區(qū)間，再通過計算機產(chǎn)生[0,1]之間的偽隨機數(shù)，根據(jù)偽隨機數(shù)的落點即可完成一次采樣。
那么問題來了，如果我們要對一個連續(xù)分布（即給定一個已知的概率密度函數(shù)）進行采樣，那么上述對[0,1]區(qū)間劃分的方式顯然就失效了（當然，最簡單的方法，可能會有人考慮將概率密度函數(shù)均勻分段積分，然后繼續(xù)采用之前的做法，不過這樣永遠只能得到近似的采樣結(jié)果，永遠不可能得到原始分布的采樣結(jié)果，并且高維情況下積分的計算代價以及是否可積本身也是個問題）。所以，在給定概率密度函數(shù)的連續(xù)分布下要如何采樣呢？
對于概率密度函數(shù)的采樣，相信一些人可以很直觀的想到可以利用累積分布函數(shù)（P(x<t)，即，即在[0,1]間隨機生成一個數(shù)a，然后求使得P(x<t)=a成立的t，t即可以視作從該分部中得到的一個采樣結(jié)果。
采樣方法
（0）Box-Muller方法
用平均分布的一對隨機變量生成高斯分布的隨機變量,如果隨機變量 U1,U2 獨立且U1,U2～Uniform[0,1]
滿足高斯分布。
但是這是基于累積分布函數(shù)可積，且P(x<t)=a可解，即累積分布函數(shù)具有反函數(shù)的條件下的。假如累積分布函數(shù)沒有反函數(shù)呢？
（1）拒絕采樣
很多實際問題中，既然 p(x) 太復雜在程序中沒法直接采樣，那么我們可以設(shè)定一個程序可抽樣的分布 q(x) 比如高斯分布，然后按照一定的方法拒絕某些樣本，達到接近 p(x) 分布的目的，其中q(x)叫做 proposal distribution 。
具體操作如下，設(shè)定一個方便抽樣的函數(shù) q(x)，以及一個常量 k，使得 p(x) 總在 kq(x) 的下方。
- x 軸方向：從 q(x) 分布抽樣得到 a。
- y 軸方向：從均勻分布（0, kq(a)) 中抽樣得到 u。
- 如果剛好落到灰色區(qū)域： u > p(a), 拒絕， 否則接受這次抽樣。
- 重復以上過程
問題：在高維的情況下，Rejection Sampling 會出現(xiàn)兩個問題，第一是合適的 q 分布比較難以找到，第二是很難確定一個合理的 k 值。這兩個問題會導致拒絕率很高，無用計算增加。
