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

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

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

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

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

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

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

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

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