我之前有發過一篇創作關於如何計算圓周率的創作文，不過事實上還有其他方法能計算出圓周率，其中之一就是蒙地卡羅模擬，用投擲飛鏢來計算面積求圓周率的方法還滿有趣的，我記得過去修課的時候有一次作業就是平行化蒙地卡羅模擬來計算圓周率。
另一方面，蒙地卡羅模擬要能成功實做，如何隨機地模擬投擲飛鏢是很重要的。換句話說，如果沒有提供一個能提供亂數的機制，蒙地卡羅模擬就很難做出來，甚至是其他功能都沒有辦法做出來。
首先，我們對於亂數的產生有以下的需求，我們盡可能希望亂數產生器所產生的數字與數字間的關係越"獨立"(independent)越好，換句話說，我們不希望數字與數字之間產生相依關係，不然的話，亂數的隨機性質就會消失。
Linear Congruential Generator (LCG)
其中a為multiplier，b為offset，m為modulus，x是random seed，u是產生的亂數（範圍為：0.0 ~ 1.0）
這邊先假設a = 3，b = 0，m=5，x=3，我們來看看它產生的亂數序列
他的X序列為：4、2、1、3、4、4、2、1、3、4、2、1、3，每經過 " 4、2、1、3 " 四個數字後就會重新開始一個序列週期（period），事實上這裡很明顯由m來控制period。這是一個應用性很差的亂數產生器，我們會希望找到合理的參數對（a,b,m）來盡可能讓它的週期越大越好
Minimal standard random number generator
由Park and Miller提出，參數對為（a = 7^5 = 16807，b = 0， m = 2^31 - 1 = 2147483647）
而它產生的亂數序列：
週期為2^31 - 2，這個週期對於一般的使用上而言是已經是足夠的，是一個常見的亂數產生器
Lagged Fibonacci Generators （LFG）
運算原理類似費波那契數列，中間不一定是要相加，某些binary operator也可以使用，基本是為了改善standard random number generator，但是能夠提供更長的週期，例如：
LFG(l = 17, k = 5, M = 31)的週期約為2^47
LFG(l = 55, k = 24, M = 31)的週期約為2^85
Matlab宣稱它的LFG亂數產生器週期超過2^1400
![]()
C++library使用的亂數產生器就是LFG，所以C++會建議使用C++版本的亂數產生器而不是C語言版本的
一個亂數間存在相依關係的LCG亂數產生器，它的參數對為（a = 2^16+3 = 65539, b = 0, m = 2^31）
相依關係為：
我們來看看如果使用Minimal standard random number generator以及randu generator在三維空間上的分佈情況：
Minimal standard random number generator：
randu generator ：
在某些使用情境下，randu generator的分佈會造成問題
回到蒙地卡羅模擬，理解亂數產生器對蒙地卡羅模擬的實作有任何影響嗎？
絕對有，假設我們要使用蒙地卡羅模擬來計算圓周率，那麼我挑選的亂數產生器必須具備高週期性的性質，不然當投擲次數超過亂數產生器的週期時，計算出來的圓周率精度會比較差
我們來做個實驗：
假設總共投擲1000000次，執行20次模擬算平均
- 使用LCG（a = 13，b = 0，m = 31）亂數產生器，pi為3.3733332000，err為0.2317405464
- 使用standard LCG亂數產生器，pi為3.1417626000，err為0.0001699464
有的，有一個叫做quasi-random numbers的東西可以取代亂數產生器，並且效果可以比亂數產生器還要好，不過quasi-random numbers本身不具有隨機性且具有self-avoiding的性質，所以蒙地卡羅模擬只會產生同一種結果。
quasi-random numbers的產生方式如下，給定兩參數，p代表幾進位（基本上用質數），n代表數列長度，首先產生一個從1開始的遞增數列，比如說：p為2，n為8，那麼會先產生1,2,3...8的數列，把每個數列的數轉換為p-base表示法後做reverse，然後再轉換回10進制
e.g.
1 -> 001 -> .100 -> 0.5
2 -> 010 -> .010 -> 0.25
3 -> 011 -> .110 -> 0.75
4 -> 100 -> .001 -> 0.125
以此類推
我們來比較一般的 pseudo random number generator 以及 quasi-random numbers在二維平面上分佈的差異
pseudo random number generator VS quasi-random numbers （20000 pairs points） ：
quasi-random numbers的分佈狀況會比pseudo random number generator還要好
在蒙地卡羅模擬上也有比較好的效果
- 使用quasi-random numbers，pi為3.1415720000，err為0.0000206536
創作內容
學習筆記 - 從亂數產生器到蒙地卡羅模擬
其他 (14)