蒙特卡羅算法+經(jīng)典算法

1、Monte Carlo Simulation Methods(蒙特卡羅模擬方法)主要內(nèi)容: 1.各種隨機數(shù)的生成方法. 2.MCMC方法.1從Buffon 投針問題談起2Buffon 投針問題3試驗者時間(年)針長投針次數(shù)相交次數(shù)的估計值Wolf18500.80500025323.15956Smith18550.60320412183.15665Fox18840.7510304893.15951Lazzarini19250.83340818083.141592924數(shù)值積分問題5Monte Carlo數(shù)值積分的優(yōu)點與一般的數(shù)值積分方法比較，Monte Carlo方法具有以下優(yōu)點：6隨機模擬計算

2、的基本思路1.針對實際問題建立一個簡單且便于實現(xiàn)的概率統(tǒng)計模型，使所求的量（或解）恰好是該模型某個指標的概率分布或者數(shù)字特征。2.對模型中的隨機變量建立抽樣方法，在計算機上進行模擬測試，抽取足夠多的隨機數(shù)，對有關(guān)事件進行統(tǒng)計3.對模擬試驗結(jié)果加以分析，給出所求解的估計及其精度(方差)的估計4.必要時，還應改進模型以降低估計方差和減少試驗費用，提高模擬計算的效率7隨機數(shù)的生成1.蒙特卡羅模擬的關(guān)鍵是生成優(yōu)良的隨機數(shù)。2.在計算機實現(xiàn)中,我們是通過確定性的算法生成 隨機數(shù),所以這樣生成的序列在本質(zhì)上不是隨機 的,只是很好的模仿了隨機數(shù)的性質(zhì)(如可以通過 統(tǒng)計檢驗)。我們通常稱之為偽隨機數(shù)(pseu

3、do-random numbers)。3.在模擬中，我們需要產(chǎn)生各種概率分布的隨機數(shù)，而大多數(shù)概率分布的隨機數(shù)產(chǎn)生均基于均勻分布U(0,1)的隨機數(shù)。8U(0,1)隨機數(shù)的生成一個簡單的隨機數(shù)生成器：9一個簡單的例子10一個簡單的例子(續(xù))上面的例子中，第一個隨機數(shù)生成器的周期長度是 10，而后兩個生成器的周期長度只有它的一半。我們自然希望生成器的周期越長越好，這樣我們得到的分布就更接近于真實的均勻分布。11線性同余生成器(Linear Congruential Generator )12常用的線性同余生成器13復雜一些的生成器（一）1.Combining Generators:14復雜一些的

4、生成器（二）2.Multiple recursive generator15算法實現(xiàn)許多程序語言中都自帶生成隨機數(shù)的方法，如 c 中的 random() 函數(shù)，Matlab中的rand()函數(shù)等。但這些生成器生成的隨機數(shù)效果很不一樣，比如 c 中的函數(shù)生成的隨機數(shù)性質(zhì)就比較差，如果用 c ，最好自己再編一個程序。Matlab 中的 rand() 函數(shù)，經(jīng)過了很多優(yōu)化?？梢援a(chǎn)生性質(zhì)很好的隨機數(shù)，可以直接利用。16由rand()函數(shù)生成的U0,1隨機數(shù)17由rand函數(shù)生成的2維隨機點18從U(0,1)到其它概率分布的隨機數(shù)U(0,1)的均勻分布的隨機數(shù)，是生成其他概率分布隨機數(shù)的基礎(chǔ)，下面我們主

5、要介紹兩種將U(0,1)隨機數(shù)轉(zhuǎn)換為其他分布的隨機數(shù)的方法。1.逆變換方法 (Inverse Transform Method)2.舍取方法 (Acceptance-Rejection Method)19Inverse Transform Method20Inverse Transform Method21幾個具體例子（一）22幾個具體例子（二）23幾個具體例子（三）24標準正態(tài)分布隨機數(shù)的生成正態(tài)分布是概率統(tǒng)計中最重要的分布，在此我們著重討論如何生成標準正態(tài)分布隨機數(shù)。引理：25Box-Muller 算法26逆變換方法（一）我們無法通過具體的數(shù)學表達式計算正態(tài)分布函數(shù)的逆函數(shù)，我們必須通過數(shù)

6、值的方法逼近正態(tài)函數(shù)下面我們介紹 Beasley-Springer-Moro 方法。27逆變換方法（二）28逆變換方法（三）在 matlab 中可以直接通過 norminv() 函數(shù)直接計算標準正態(tài)分布函數(shù)的逆。29Matlab生成的正態(tài)隨機數(shù)30Acceptance-Rejection Method（一）Acceptance-Rejection 方法最早由 Von Neumann提出，現(xiàn)在已經(jīng)廣泛應用于各種隨機數(shù)的生成?；舅悸罚和ㄟ^一個容易生成的概率分布 g 和一個取舍準則生成另一個與 g 相近的概率分布 f 。31Acceptance-Rejection Method（二）具體步驟：32

7、Acceptance-Rejection Method（三）下面我們驗證由上述步驟生成的隨機數(shù) Y 確實具有密度函數(shù) f(x) 33Acceptance-Rejection Method（四）所以為了提高舍取法的效率，我們應該使 c 的取值盡可能的小，也就是使 f 和 g 的分布更為相近。34幾個具體例子（一）35幾個具體例子（一）36幾個具體例子（二）37幾個具體例子（二）38隨機向量的抽樣方法（一）39隨機向量的抽樣方法（二）40生成多維正態(tài)隨機數(shù)的方法（一）41生成多維正態(tài)隨機數(shù)的方法（二）生成多維正態(tài)隨機數(shù)的具體步驟：42用Monte Carlo方法求解Laplace方程參見書上5.8

8、節(jié) P213P21543馬氏鏈在Monte Carlo隨機模擬中的應用定義 為要模擬服從給定分布的隨機變量,用生成一個易于實現(xiàn)的不可約遍歷鏈 作為隨機樣本,使其平穩(wěn)分布為 的方法，稱為馬氏鏈蒙特卡羅方法.蒙特卡羅方法的一個首要步驟是產(chǎn)生服從給定的概率分布函數(shù) 的隨機變量(或稱為隨機樣本),由概率論知識,熟知下面的結(jié)論.44引理 生成隨機變量U,使其分布滿足U0,1,記為UU0,1, F(x)是給定的一個分布函數(shù),記 為F(x)的反函數(shù),則X=F-1(U)分布函數(shù)為F(x).454647米特羅波利斯(Metropolis)等人在1953年最早給出了通過生成一馬氏鏈實現(xiàn)從分布 中采樣(生成相關(guān)的樣本)這一重要基本思想.隨后,哈斯汀(Hastings)將其推廣到更一般的形式.下面僅敘述狀態(tài)空間S為至多可數(shù)的情形:484950Markov chain Monte Carlo (MCMC)問題提出：51MCMC方法的基本思路MCMC 是一種簡單有效的計算方法，在統(tǒng)計物理，Bayes 統(tǒng)計計算，顯著性檢驗，極大似然估計等領(lǐng)域都有著廣泛的應用?；舅悸罚?2概率轉(zhuǎn)移核的構(gòu)造（一）MCMC的方法有很多，在此我們只介紹Metropolis-Hastings方法?；舅悸罚?3概率轉(zhuǎn)移核的