Monte Carlo Method Introduction
0 likes270 views
文档介绍了蒙地卡罗法的起源、原理及其在模拟实验和财务规划等领域的应用。它通过随机数来模拟复杂问题，最早应用于圆周率的估算。文档还说明了两种主要应用模式，以及蒙地卡罗法衍生的工具和在统计检验中的作用。
Monte Carlo Method Introduction
- 2. 起源 ? 蒙地卡羅是摩納哥親王國最著名的一區，以豪華的賭場 聞名於世。 ? 20世紀40年代，在科學家馮·紐曼、斯塔尼斯拉夫·烏拉 姆、尼古拉斯·梅特羅波利斯三位科學家在洛斯阿拉莫斯 國家實驗室為核武器計劃工作時，發明了蒙地卡羅方法。 ? 會取這個名稱，是因為烏拉姆的叔叔在摩納哥的蒙地卡 羅賭場輸了很多錢。
- 4. 蒙地卡羅法的原理 ? 利用電腦模擬一個理想環境，然後利用亂數產生大 量隨機狀況，藉以探討許多難以進行實際試驗的理 論。這種利用蒙地卡羅法進行的電腦模擬研究，又 稱為蒙地卡羅模擬法(Monte Carlo Simulation method)。
- 6. 一、Buffon 投針實驗 針 n = 2212 相交數 m= 704 ? = ? ? ≈ 3.14 此法由法國科學家Buffon在1777年提出，針的數目為 2212，請賓客投在畫有平行線的紙上，然後計算針與 平行線相交的數計有704，然後兩者相除，可以得到π 的近似值。
- 7. 一、Buffon 投針實驗 ? 此法由法國科學家Buffon在1777年提出，方法是在桌面畫 距離為2a的平行橫線，再將長度為 2? 的針反覆丟在桌面上 如圖上，然後計算所投針的總次數(N)及針與橫線相交的次 數(n)，如此Buffon便宣稱： 圓周率π ≈ 2?? ??
- 8. Buffon’s needle 2 φ 線的間距和棒子的長度都等於2 Φ的可以角度從0到π 1 π/2 π sinφ 壓到線的比率就是sinΦ， 所以要積分sin Φ 沒有壓到線的比率就是1-sinΦ 長方形面積=1 x π = π 半圓形面積= ??? 0 π 1 2 l sinΦ?? = l 所以壓到線的機率就是 2 ? φ 相交的條件 x ≤ 1 2 l sinΦ l x 1 2 l sinΦ 1 2 l
- 9. 一、Buffon投針實驗 其原理被證明如下： ? 假設M為針的中點，又y為M至其最近平行線的 距離，針與水平面的夾角為φ，則其垂直面的 投影為?sinφ，因此當y ≦ ? sinφ 時，即表示針 與平行線相交。由於0 ≦ y ≦ a、0 ≦ φ ≦ π，故 針與平行線相交的機率即為圖下的陰影面積所 佔比例： 因此，只要不斷重複作投針的動作，再以 觀測所得的針線相交機率P值配合已知的l 與 a 值，就可以反推求得我們想要的圓周 率 π。
- 10. Buffon’s needle ? 這個方法採用隨機的原理來解決一項看似毫不相干的問題， 可以說是歷史上最早的蒙地卡羅法應用，又稱之為Buffon之 針(Buffon’s needle) 。 ? 今天我們可以利用電腦模擬的方式重作這個實驗，而不用 真的拿一堆針去丟。只要反覆取各種y和φ的隨機亂數值來 模擬針落下的位置和角度，即可求得針和其中一條橫線相 交的機率P，進而反推求得我們想要的π值。
- 11. 二、由圓面積估算反推π值 ? 以圖的圓形面積估算為例，已知半徑為 r 的圓在二維座標空間的表 示法為 x2 + y2 ≦ r2，因此要估算此圓的面積，只要利用電腦在 –r ≦ x, y ≦ r的二維座標平面(方框部分)隨機產生亂數點，當 x2 + y2 ≦ r2 時 (灰色部分)，即表示此點落在該圓面積中。再計算分布在不同地 方的亂數點落在圓內的次數(n)占全部點數(N)的比例( ? ? )，由於已知 正方形面積為 4r2，便可以求得圓形的面積為 4r2( ? ? ) = πr2。 ? 因此，圓周率π估值可由落在圓內的亂數點比例 4? ? 加以估算，由 於這個估值本身不包含圓半徑 r，也可證明用這個方法估算圓周率 π 跟所使用的圓半徑大小無關。
- 12. 兩種方法的比較 ? 這兩種方法應用的原理差別在於所取得的隨機亂數的用途，這也是蒙 地卡羅法的兩種主要應用模式： ? 第一個例子是以隨機方法模擬真實的投針實驗過程，然後再觀察模擬 實驗的結果，以取代真正的實驗～也就是以機率的方法來解決非機率 的問題。 ? 第二個例子則是以隨機亂數點落在正方形和內接圓上面的比例來估算 π值，這是直接把隨機亂數拿來當作實驗觀測值使用。
- 13. 蒙地卡羅法的應用 ? 一、模擬真實實驗過程 ? 二、當作計算輔助工具 ? 三、作為多自由度系統的另類解法 ? 四、作為最佳化問題的另類解法
- 21. 四、另類解法 ? 最早且最有名的最佳化問題，當屬所謂的「旅行推銷員問題」 (Traveling Salesman Problem) ，也就是要找出一個距離最短的 路徑。 ? 這是一個非常複雜的數學問題，因為兩兩城市間走法的組合會隨城 市數目增加而快速暴增。4個城市間的走法只有4! / 2 = 3種，但10 個城市間的走法就快速增加到9! / 2 = 181,440種；加上城市間的距 離各有不同，也必須同時考慮，而使問題更加複雜。
- 22. 四、另類解法 ? 這類問題在演算法(Algorithm) 領域被稱之為難解 (Nondetermnistic Polynomial-time Complete, NPC) 問題，它的複雜度會隨系統的單位 數目N呈 eN 或 N! 等所謂超多項式函數的規模增加，而非以一般多項式 函數的規模增加，使得計算十分花費時間，甚至根本算不完。 ? 這類最佳化問題往往只要求實用解，即使不是最佳解也沒關係。這時 候，蒙地卡羅法就可以派上用場了。
- 23. 從蒙地卡羅法衍生的工具 一、拔靴法(Bootstrap)： 二、模擬退火法(Simulated Annealing, SA)： 三、遺傳演算法(Genetic Algorithm, GA)：
- 24. 統計檢定上的應用 ? Carmer與Swanson(1971) 利用蒙地卡羅法產生逢機觀測值，來比較 五種當時常用的處理平均值多重比較法的檢定效果，包括： 1.LSD：普通的最小差異顯著LSD法(Least Significant Difference) 2.FLSD：先經過F檢定後，再進行LSD法 3.TSD：Turkey的差異顯著檢定法(Turkey’s Significant Difference) 4.DMRT：Duncan的多重範圍檢定(Duncan’s Multiple Range Test) 5.BLSD：採用貝氏定理為基礎修正後的LSD法(Bayesian LSD)