蒙特卡羅方法又稱統計模拟法、随機抽樣技術,是一種随機模拟方法,以機率和統計理論方法為基礎的一種計算方法,是使用随機數(或更常見的僞随機數)來解決很多計算問題的方法。将所求解的問題同一定的機率模型相聯系,用電子計算機實作統計模拟或抽樣,以獲得問題的近似解。為象征性地表明這一方法的機率統計特征,數學家馮·諾依曼用聞名世界的賭城——蒙特卡羅命名(就是那個馮·諾依曼)。
1、蒙特卡洛方法
蒙特卡羅方法又稱統計模拟法、随機抽樣技術,是一種随機模拟方法,以機率和統計理論方法為基礎的一種計算方法,是使用随機數(或更常見的僞随機數)來解決很多計算問題的方法。将所求解的問題同一定的機率模型相聯系,用電子計算機實作統計模拟或抽樣,以獲得問題的近似解。為象征性地表明這一方法的機率統計特征,數學家馮·諾依曼用聞名世界的賭城——蒙特卡羅命名(就是那個馮·諾依曼)。
蒙特卡羅方法解題過程的主要步驟:
a.針對實際問題建立一個簡單且便于實作的機率統計模型,使所求的量恰好是該模型的機率分布或數字特征。
b.對模型的随機變量建立抽樣方法,在計算機上進行模拟測試,抽取足夠多的随機數。
c.對模拟實驗結果進行統計分析,給出所求解的“估計”。
d.必要時,改進模型以提高估計精度和減少實驗費用,提高模拟效率。
2、馮·諾依曼
馮·諾依曼(John von Neumann,1903~1957),20世紀最重要的數學家之一,在現代計算機、博弈論和核武器等諸多領域内有傑出建樹的最偉大的科學全才之一,被稱為“計算機之父”和“博弈論之父”。主要貢獻是:2進制思想與程式記憶體思想,當然還有蒙特卡洛方法。通過第一部分,可知,蒙特卡洛方法更多的是一種思想的展現(這點遠不同于快排等“嚴格”類算法),下面介紹最常見的一種應用——随機數生成。
3、U(0,1)随機數的産生
對随機系統進行模拟,便需要産生服從某種分布的一系列随機數。最常用、最基礎的随機數是在(0,1)區間内均勻分布的随機數,最常用的兩類數值計算方法是:乘同餘法和混合同餘法。
乘同餘法:

其中,
被稱為種子,
是模,
是(0,1)區間的随機數。
混合同餘法:
其中,
是非負整數。
這些随機數是具有周期性的,模拟參數的選擇不同,産生的随機數品質也有所差異。更複雜的生成方法還有:
4、從U(0,1)到其它機率分布的随機數
離散型随機數的模拟
設随機變量X的機率分布為:
,分布函數有
設随機變量U~U(0,1)的均勻分布,則
,表明
的機率與随機變量u落在
與
之間的機率相同。
例如:離散随機變量X有分布律
X | 1 | 2 | |
P(x) | 0.3 | 0.3 | 0.4 |
U是(0,1)的均勻分布,則有
,這樣得到的x便具有X的分布律。
連續型随機變量的模拟
常用的有兩種方法:逆變換法和舍選法。逆變換法
定理:設随機變量Y的分布函數為F(y)是連續函數,而U是(0,1)上均勻分布的随機變量。另
,則X和Y具有相同的分布。
證明:由定義知,X的分布函數
是以X和Y具有相同的分布。
這樣計算得
,帶入均勻分布的U,即可得到服從
的随機數Y。
例如:設X~U(a,b),則其分布函數為
則
。是以生成U(0,1)的随機數U,則
便是來自U(a,b)的随機數。
有些随機變量的累計分布函數不存在或者難以求出,即使存在,但計算困難,于是提出了舍選法
要産生服從
的随機數,設x的值域為[a,b],抽樣過程如下:
1.已知随機分布
且x的取值區間也為[a,b],并要求
,如圖:
2.從
中随機抽樣得
,然後由
的均勻分布抽樣得
。
3.接受或舍棄取樣值
,如果
舍棄該值;傳回上一步,否則接受。幾何解釋如下:
常數c的選取:c應該盡可能地小,因為抽樣效率與c成反比;一般取
。這裡的
可以取均勻分布,這樣由第二步中兩個均勻分布便能得到其他任意分布的模拟抽樣。
5、正态随機數的生成
除了上面的反函數法和舍選法,正态随機數還可以根據中心極限定理和Box Muller(坐标變換法)得到。
中心極限定理:如果随機變量序列
獨立同分布,并且具有有限的數學期望和方差
,則對于一切
有
也就是說,當n個獨立同分布的變量和,服從
的正态分布(n足夠大時)。
設n個獨立同分布的随機變量
,它們服從U(0,1)的均勻分布,那麼
漸近服從正态分布
。
Box Muller方法,設(X,Y)是一對互相獨立的服從正态分布
的随機變量,則有機率密度函數:
令
,其中
,則
有分布函數:
令
,則分布函數的反函數得:
。
如果
服從均勻分布U(0,1),則
可由
模拟生成(
也為均勻分布,可被
代替)。令
為
,
服從均勻分布U(0,1)。得:
X和Y均服從正态分布。用Box Muller方法來生成服從正态分布的随機數是十分快捷友善的。