隨機(jī)數(shù)的定義及產(chǎn)生方法

1、l 隨機(jī)數(shù)的定義及產(chǎn)生方法隨機(jī)數(shù)的定義及產(chǎn)生方法 l 偽隨機(jī)數(shù)偽隨機(jī)數(shù)l 產(chǎn)生偽隨機(jī)數(shù)的乘同余方法產(chǎn)生偽隨機(jī)數(shù)的乘同余方法l 產(chǎn)生偽隨機(jī)數(shù)的乘加同余方法產(chǎn)生偽隨機(jī)數(shù)的乘加同余方法l 產(chǎn)生偽隨機(jī)數(shù)的其他方法產(chǎn)生偽隨機(jī)數(shù)的其他方法l 偽隨機(jī)數(shù)序列的均勻性和獨(dú)立性偽隨機(jī)數(shù)序列的均勻性和獨(dú)立性作作 業(yè)業(yè) 由具有已知分布的總體中抽取簡(jiǎn)單子樣，在蒙特卡羅方法中占有非常重要的地位。總體和子樣的關(guān)系，屬于一般和個(gè)別的關(guān)系，或者說屬于共性和個(gè)性的關(guān)系。由具有已知分布的總體中產(chǎn)生簡(jiǎn)單子樣，就是由簡(jiǎn)單子樣中若干個(gè)性近似地反映總體的共性。 隨機(jī)數(shù)是實(shí)現(xiàn)由已知分布抽樣的基本量，在由已知分布的抽樣過程中，將隨機(jī)數(shù)作為已知

2、量，用適當(dāng)?shù)臄?shù)學(xué)方法可以由它產(chǎn)生具有任意已知分布的簡(jiǎn)單子樣。 l 隨機(jī)數(shù)的定義及性質(zhì)l 隨機(jī)數(shù)表l 物理方法 在連續(xù)型隨機(jī)變量的分布中，最簡(jiǎn)單而且最基本的分布是單位均勻分布。由該分布抽取的簡(jiǎn)單子樣稱，隨機(jī)數(shù)序列，其中每一個(gè)體稱為隨機(jī)數(shù)。 單位均勻分布也稱為0，1上的均勻分布，其分布密度函數(shù)為： 分布函數(shù)為 ：其他, 010, 1)(xxf1, 110,0, 0)(xxxxxF 由于隨機(jī)數(shù)在蒙特卡羅方法中占有極其重要的位置，我們用專門的符號(hào)表示。由隨機(jī)數(shù)序列的定義可知，1，2，是相互獨(dú)立且具有相同單位均勻分布的隨機(jī)數(shù)序列。也就是說，獨(dú)立性獨(dú)立性、均勻性均勻性是隨機(jī)數(shù)必備的兩個(gè)特點(diǎn)。 隨機(jī)數(shù)具有非

3、常重要的性質(zhì)：對(duì)于任意自然數(shù)s，由s個(gè)隨機(jī)數(shù)組成的s維空間上的點(diǎn)（n+1，n+2，n+s）在s維空間的單位立方體Gs上均勻分布，即對(duì)任意的ai， 如下等式成立：siai, 2 , 110，siiiinasiaP1), 1,( 其中P()表示事件發(fā)生的概率。反之，如果隨機(jī)變量序列1, 2對(duì)于任意自然數(shù)s，由s個(gè)元素所組成的s維空間上的點(diǎn)（n+1，n+s）在Gs上均勻分布，則它們是隨機(jī)數(shù)序列。 由于隨機(jī)數(shù)在蒙特卡羅方法中所處的特殊地位，它們雖然也屬于由具有已知分布的總體中產(chǎn)生簡(jiǎn)單子樣的問題，但就產(chǎn)生方法而言，卻有著本質(zhì)上的差別。 為了產(chǎn)生隨機(jī)數(shù)，可以使用隨機(jī)數(shù)表。隨機(jī)數(shù)表是由0，1，9十個(gè)數(shù)字組成

4、，每個(gè)數(shù)字以0.1的等概率出現(xiàn)，數(shù)字之間相互獨(dú)立。這些數(shù)字序列叫作隨機(jī)數(shù)字序列。如果要得到n位有效數(shù)字的隨機(jī)數(shù)，只需將表中每n個(gè)相鄰的隨機(jī)數(shù)字合并在一起，且在最高位的前邊加上小數(shù)點(diǎn)即可。例如，某隨機(jī)數(shù)表的第一行數(shù)字為7634258910，要想得到三位有效數(shù)字的隨機(jī)數(shù)依次為0.763，0.425，0.891。 因?yàn)殡S機(jī)數(shù)表需在計(jì)算機(jī)中占有很大內(nèi)存，而且也難以滿足蒙特卡羅方法對(duì)隨機(jī)數(shù)需要量非常大的要求，因此，該方法不適于在計(jì)算機(jī)上使用。 用物理方法產(chǎn)生隨機(jī)數(shù)的基本原理是：利用某些物理現(xiàn)象，在計(jì)算機(jī)上增加些特殊設(shè)備，可以在計(jì)算機(jī)上直接產(chǎn)生隨機(jī)數(shù)。這些特殊設(shè)備稱為隨機(jī)數(shù)發(fā)生器。用來作為隨機(jī)數(shù)發(fā)生器的物

5、理源主要有兩種：一種是根據(jù)放射性物質(zhì)的放射性，另一種是利用計(jì)算機(jī)的固有噪聲。 一般情況下，任意一個(gè)隨機(jī)數(shù)在計(jì)算機(jī)內(nèi)總是用二進(jìn)制的數(shù)表示的： 其中i（i=1，2，m）或者為0，或者為1。 mm2222211 因此，利用物理方法在計(jì)算機(jī)上產(chǎn)生隨機(jī)數(shù)，就是要產(chǎn)生只取0或1的隨機(jī)數(shù)字序列，數(shù)字之間相互獨(dú)立，每個(gè)數(shù)字取0或1的概率均為0.5。 用物理方法產(chǎn)生的隨機(jī)數(shù)序列無法重復(fù)實(shí)現(xiàn)，不能進(jìn)行程序復(fù)算，給驗(yàn)證結(jié)果帶來很大困難。而且，需要增加隨機(jī)數(shù)發(fā)生器和電路聯(lián)系等附加設(shè)備，費(fèi)用昂貴。因此，該方法也不適合在計(jì)算機(jī)上使用。l 偽隨機(jī)數(shù)l 偽隨機(jī)數(shù)存在的兩個(gè)問題l 偽隨機(jī)數(shù)的周期和最大容量 在計(jì)算機(jī)上產(chǎn)生隨機(jī)數(shù)

6、最實(shí)用、最常見的方法是數(shù)學(xué)方法，即用如下遞推公式： 產(chǎn)生隨機(jī)數(shù)序列。對(duì)于給定的初始值1,2，k，確定n+k，=1，2，。經(jīng)常使用的是k=1的情況，其遞推公式為： 對(duì)于給定的初始值1，確定n+1，=, )(nknT, 2 , 1),(11nTknnnkn 用數(shù)學(xué)方法產(chǎn)生的隨機(jī)數(shù)，存在兩個(gè)問題：l遞推公式和初始值1,2，k確定后，整個(gè)隨機(jī)數(shù)序列便被唯一確定。不滿足隨機(jī)數(shù)相互獨(dú)立的要求。l由于隨機(jī)數(shù)序列是由遞推公式確定的，而在計(jì)算機(jī)上所能表示的0，1上的數(shù)又是有限的，因此，這種方法產(chǎn)生的隨機(jī)數(shù)序列就不可能不出現(xiàn)無限重復(fù)。一旦出現(xiàn)這樣的n，n (n n )，使得下面等式成立：a) 隨機(jī)數(shù)序列便出現(xiàn)了周

7、期性的循環(huán)現(xiàn)象。對(duì)于k=1的情況，只要有一個(gè)隨機(jī)數(shù)重復(fù)，其后面的隨機(jī)數(shù)全部重復(fù)，這與隨機(jī)數(shù)的要求是不相符的。 kiinin, 2 , 1 由于這兩個(gè)問題的存在，常稱用數(shù)學(xué)方法產(chǎn)生的隨機(jī)數(shù)為偽隨機(jī)數(shù)。對(duì)于以上存在的兩個(gè)問題，作如下具體分析。 關(guān)于第一個(gè)問題，不能從本質(zhì)上加以改變，但只要遞推公式選得比較好，隨機(jī)數(shù)間的相互獨(dú)立性是可以近似滿足的。至于第二個(gè)問題，則不是本質(zhì)的。因?yàn)橛妹商乜_方法解任何具體問題時(shí)，所使用的隨機(jī)數(shù)的個(gè)數(shù)總是有限的，只要所用隨機(jī)數(shù)的個(gè)數(shù)不超過偽隨機(jī)數(shù)序列出現(xiàn)循環(huán)現(xiàn)象時(shí)的長(zhǎng)度就可以了。 用數(shù)學(xué)方法產(chǎn)生的偽隨機(jī)數(shù)容易在計(jì)算機(jī)上得到，可以進(jìn)行復(fù)算，而且不受計(jì)算機(jī)型號(hào)的限制。因此，

8、這種方法雖然存在著一些問題，但仍然被廣泛地在計(jì)算機(jī)上使用，是在計(jì)算機(jī)上產(chǎn)生偽隨機(jī)數(shù)的主要方法。 發(fā)生周期性循環(huán)現(xiàn)象的偽隨機(jī)數(shù)的個(gè)數(shù)稱為偽隨機(jī)數(shù)的周期。對(duì)于前面介紹的情況，偽隨機(jī)數(shù)的周期為nn。 從偽隨機(jī)數(shù)序列的初始值開始，到出現(xiàn)循環(huán)現(xiàn)象為止，所產(chǎn)生的偽隨機(jī)數(shù)的個(gè)數(shù)稱為偽隨機(jī)數(shù)的最大容量。前面的例子中，偽隨機(jī)數(shù)的最大容量為n 。 乘同余方法是由Lehmer在1951年提出來的，它的一般形式是：對(duì)于任一初始值x1，偽隨機(jī)數(shù)序列由下面遞推公式確定： 其中a為常數(shù)。 )(mod,1Mxaxii, 2 , 1,11iMxii 對(duì)于任意正整數(shù)M，根據(jù)數(shù)論中的標(biāo)準(zhǔn)分解定理，總可以分解成如下形式： 其中P0=

9、2，P1， Pr表示不同的奇素?cái)?shù)，0表示非負(fù)整數(shù)，1，r表示正整數(shù)。a無論取什么值，乘同余方法的最大容量的上界為： 的最小公倍數(shù)。其中：rrPPPM1010)()(),()(1010rrPPPM222101)(0200000當(dāng)當(dāng)或當(dāng)PriPPPiiiii, 2 , 1),1()(11 如果a與x1滿足如下條件： 對(duì)于 ， x1與M互素，則乘同余方法產(chǎn)生的偽隨機(jī)數(shù)序列的最大容量達(dá)到最大可能值(M)。 2)8(mod532)4(mod31)2(mod1000當(dāng)或當(dāng)當(dāng)a)(0iiPn)(mod1iinPa 為了便于在計(jì)算機(jī)上使用，通常取 ：=2s 其中s為計(jì)算機(jī)中二進(jìn)制數(shù)的最大可能有效位數(shù)x1= 奇

10、數(shù) a = 52k+1 其中k為使52k+1在計(jì)算機(jī)上所能容納的最大整數(shù)，即a為計(jì)算機(jī)上所能容納的5的最大奇次冪。一般地，s=32時(shí)，a=513；s=48，a=515等。偽隨機(jī)數(shù)序列的最大容量(M)=2s-2 。 乘同余方法是使用的最多、最廣的方法，在計(jì)算機(jī)上被廣泛地使用。 產(chǎn)生偽隨機(jī)數(shù)的乘加同余方法是由Rotenberg于1960年提出來的，由于這個(gè)方法有很多優(yōu)點(diǎn)，已成為僅次于乘同余方法產(chǎn)生偽隨機(jī)數(shù)的另一主要方法。 乘加同余方法的一般形式是，對(duì)任意初始值x1，偽隨機(jī)數(shù)序列由下面遞推公式確定： 其中a和c為常數(shù)。 )(mod,1Mcxaxii, 2 , 1,11iMxii 關(guān)于乘加同余方法的最

11、大容量問題，有如下結(jié)論：如果對(duì)于正整數(shù)M的所有素?cái)?shù)因子P，下式均成立： 當(dāng)M為4的倍數(shù)時(shí)，還有下式成立： c與M互素，則乘加同余方法所產(chǎn)生的偽隨機(jī)數(shù)序列的最大容量達(dá)到最大可能值M。 )(mod1Pa )4(mod1a 為了便于在計(jì)算機(jī)上使用，通常取M = 2s 其中s為計(jì)算機(jī)中二進(jìn)制數(shù)的最大可能有效位數(shù)。a = 2b + 1(b2)c = 1 這樣在計(jì)算中可以使用移位和指令加法，提高計(jì)算速度。 l 取中方法l 加同余方法 判斷偽隨機(jī)數(shù)序列是否滿足均勻和相互獨(dú)立的要求，要靠統(tǒng)計(jì)檢驗(yàn)的方法實(shí)現(xiàn)。對(duì)于偽隨機(jī)數(shù)的統(tǒng)計(jì)檢驗(yàn)，一般包括兩大類：均勻性檢驗(yàn)和獨(dú)立性檢驗(yàn)。 六十年代初，人們開始用定性的方法研究偽

12、隨機(jī)數(shù)序列的均勻性和獨(dú)立性問題，簡(jiǎn)要敘述如下。 這里只考慮偽隨機(jī)數(shù)序列1,2，n全體作為子樣時(shí)的均勻性問題。其中n為偽隨機(jī)數(shù)序列的最大容量。 對(duì)于任意的0 x1，令Nn(x)表示偽隨機(jī)數(shù)序列1,2，n中適合不等式i x i=1，2，n 的個(gè)數(shù)，則 標(biāo)志偽隨機(jī)數(shù)序列1,2，n的均勻程度，稱為均勻偏度。|)(|)(sup10 xnxNnnx 將偽隨機(jī)數(shù)序列1,2，n從小至大重新排列 并令 ，則由(n)的定義，容易證明 很明顯，對(duì)于固定的，(n)的值越小越好。它是描述偽隨機(jī)數(shù)序列均勻程度的基本量。對(duì)于任意隨機(jī)數(shù)序列，均有如下不等式成立： 當(dāng) 時(shí)，所對(duì)應(yīng)的偽隨機(jī)數(shù)序列為最佳分布。n211, 010n|

13、 , |)(110maxnininiixnn21)(nn21)( 可以證明，偽隨機(jī)數(shù)序列為最佳分布的充要條件是它取遍序列 的所有值。 對(duì)于計(jì)算機(jī)上使用的乘同余方法，按照前面介紹的方法選取a、x1時(shí)，所產(chǎn)生的偽隨機(jī)數(shù)序列的均勻偏度 對(duì)于乘加同余方法 對(duì)于部分偽隨機(jī)數(shù)的均勻性問題通常用統(tǒng)計(jì)檢驗(yàn)方法檢驗(yàn)。 nini, 2 , 1212nn43)(nn1)( 對(duì)于任意 ，令 表示(1,2)， (2,3)， (n,n+1)中適合不等式 的個(gè)數(shù)，根據(jù)隨機(jī)變量間相互獨(dú)立的定義和頻率近似概率的方法，令 則(n)標(biāo)志偽隨機(jī)數(shù)序列1,2，n的獨(dú)立程度，簡(jiǎn)稱為獨(dú)立偏度。對(duì)于固定的n,(n)的值越接近于零，偽隨機(jī)數(shù)序列的獨(dú)立性越好。 1,0yx),(yxNnyxii1,|)()(),(|