天天看點

随機數生成算法

蒙特卡羅方法又稱統計模拟法、随機抽樣技術,是一種随機模拟方法,以機率和統計理論方法為基礎的一種計算方法,是使用随機數(或更常見的僞随機數)來解決很多計算問題的方法。将所求解的問題同一定的機率模型相聯系,用電子計算機實作統計模拟或抽樣,以獲得問題的近似解。為象征性地表明這一方法的機率統計特征,數學家馮·諾依曼用聞名世界的賭城——蒙特卡羅命名(就是那個馮·諾依曼)。

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方法來生成服從正态分布的随機數是十分快捷友善的。