蒙特卡羅方法在隨機(jī)數(shù)中的應(yīng)用.ppt

第二章 隨機(jī)數(shù),隨機(jī)數(shù)的定義及產(chǎn)生方法 偽隨機(jī)數(shù) 產(chǎn)生偽隨機(jī)數(shù)的乘同余方法 產(chǎn)生偽隨機(jī)數(shù)的乘加同余方法 產(chǎn)生偽隨機(jī)數(shù)的其他方法 偽隨機(jī)數(shù)序列的均勻性和獨(dú)立性 作 業(yè),第二章 隨機(jī)數(shù),由具有已知分布的總體中抽取簡(jiǎn)單子樣，在蒙特卡羅方法中占有非常重要的地位。總體和子樣的關(guān)系，屬于一般和個(gè)別的關(guān)系，或者說(shuō)屬于共性和個(gè)性的關(guān)系。由具有已知分布的總體中產(chǎn)生簡(jiǎn)單子樣，就是由簡(jiǎn)單子樣中若干個(gè)性近似地反映總體的共性。 隨機(jī)數(shù)是實(shí)現(xiàn)由已知分布抽樣的基本量，在由已知分布的抽樣過(guò)程中，將隨機(jī)數(shù)作為已知量，用適當(dāng)?shù)臄?shù)學(xué)方法可以由它產(chǎn)生具有任意已知分布的簡(jiǎn)單子樣。,什么是隨機(jī)數(shù)？,單個(gè)的數(shù)字不是隨機(jī)數(shù),是指一個(gè)數(shù)列，其中的每一個(gè)體稱為隨機(jī)數(shù)，其值與數(shù)列中的其它數(shù)無(wú)關(guān)；,在一個(gè)均勻分布的隨機(jī)數(shù)中，每一個(gè)體出現(xiàn)的概率是均等的；,例如：在0,1區(qū)間上均勻分布的隨機(jī)數(shù)序列中，0.00001與0.5出現(xiàn)的機(jī)會(huì)均等,隨機(jī)數(shù)應(yīng)具有的基本特性,考慮一個(gè)對(duì)高能粒子反應(yīng)過(guò)程的模擬：需用隨機(jī)數(shù)確定：,出射粒子的屬性：能量、方向、,粒子與介質(zhì)的相互作用,對(duì)這一過(guò)程的模擬應(yīng)滿足以下要求（相空間產(chǎn)生過(guò)程）：,出射粒子的屬性應(yīng)是互不相關(guān)的，即每一粒子的屬性的確定獨(dú)立于其它的粒子的屬性的確定；,粒子的屬性的分布應(yīng)滿足物理所要求的理論分布；,所模擬的物理過(guò)程要求隨機(jī)數(shù)應(yīng)具有下列特性：,隨機(jī)數(shù)序列應(yīng)是獨(dú)立的、互不相關(guān)的(uncorrelated)：,即序列中的任一子序列應(yīng)與其它的子序列無(wú)關(guān)；,長(zhǎng)的周期(long period)：,實(shí)際應(yīng)用中，隨機(jī)數(shù)都是用數(shù)學(xué)方法計(jì)算出來(lái)的，這些算法具有周期性，即當(dāng)序列達(dá)到一定長(zhǎng)度后會(huì)重復(fù)；,均勻分布的隨機(jī)數(shù)應(yīng)滿足均勻性(Uniformity)：,隨機(jī)數(shù)序列應(yīng)是均勻的、無(wú)偏的，即：如果兩個(gè)子區(qū)間的“面積”相等，則落于這兩個(gè)子區(qū)間內(nèi)的隨機(jī)數(shù)的個(gè)數(shù)影相等。,例如：對(duì)0,1)區(qū)間均勻分布的隨機(jī)數(shù)，如果產(chǎn)生了足夠多的隨機(jī)數(shù)，而有一半的隨機(jī)數(shù)落于區(qū)間0,0.1不滿足均勻性,如果均勻性不滿足，則會(huì)出現(xiàn)序列中的多組隨機(jī)數(shù)相關(guān)的情況均勻性與互不相關(guān)的特性是有聯(lián)系的,有效性（Efficiency):,模擬結(jié)果可靠,模擬產(chǎn)生的樣本容量大,所需的隨機(jī)數(shù)的數(shù)量大,隨機(jī)數(shù)的產(chǎn)生必須快速、有效，最好能夠進(jìn)行并行計(jì)算。,隨機(jī)數(shù)的定義及產(chǎn)生方法,隨機(jī)數(shù)的定義及性質(zhì) 隨機(jī)數(shù)表 物理方法,隨機(jī)數(shù)的定義及性質(zhì),在連續(xù)型隨機(jī)變量的分布中，最簡(jiǎn)單而且最基本的分布是單位均勻分布。由該分布抽取的簡(jiǎn)單子樣稱，隨機(jī)數(shù)序列，其中每一個(gè)體稱為隨機(jī)數(shù)。 單位均勻分布也稱為0，1上的均勻分布，其分布密度函數(shù)為： 分布函數(shù)為 ：,由于隨機(jī)數(shù)在蒙特卡羅方法中占有極其重要的位置，我們用專門的符號(hào)表示。由隨機(jī)數(shù)序列的定義可知，1，2，是相互獨(dú)立且具有相同單位均勻分布的隨機(jī)數(shù)序列。也就是說(shuō)，獨(dú)立性、均勻性是隨機(jī)數(shù)必備的兩個(gè)特點(diǎn)。 隨機(jī)數(shù)具有非常重要的性質(zhì)：對(duì)于任意自然數(shù)s，由s個(gè)隨機(jī)數(shù)組成的s維空間上的點(diǎn)（n+1，n+2，n+s）在s維空間的單位立方體Gs上均勻分布，即對(duì)任意的ai， 下等式成立：,其中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)單子樣的問(wèn)題，但就產(chǎn)生方法而言，卻有著本質(zhì)上的差別。,隨機(jī)數(shù)表,為了產(chǎn)生隨機(jī)數(shù)，可以使用隨機(jī)數(shù)表。隨機(jī)數(shù)表是由0，1，9十個(gè)數(shù)字組成，每個(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ā)生器。用來(lái)作為隨機(jī)數(shù)發(fā)生器的物理源主要有兩種：一種是根據(jù)放射性物質(zhì)的放射性，另一種是利用計(jì)算機(jī)的固有噪聲。 一般情況下，任意一個(gè)隨機(jī)數(shù)在計(jì)算機(jī)內(nèi)總是用二進(jìn)制的數(shù)表示的： 其中i（i=1，2，m）或者為0，或者為1。,因此，利用物理方法在計(jì)算機(jī)上產(chǎn)生隨機(jī)數(shù)，就是要產(chǎn)生只取0或1的隨機(jī)數(shù)字序列，數(shù)字之間相互獨(dú)立，每個(gè)數(shù)字取0或1的概率均為0.5。 用物理方法產(chǎn)生的隨機(jī)數(shù)序列無(wú)法重復(fù)實(shí)現(xiàn)，不能進(jìn)行程序復(fù)算，給驗(yàn)證結(jié)果帶來(lái)很大困難。而且，需要增加隨機(jī)數(shù)發(fā)生器和電路聯(lián)系等附加設(shè)備，費(fèi)用昂貴。因此，該方法也不適合在計(jì)算機(jī)上使用。,偽隨機(jī)數(shù),偽隨機(jī)數(shù) 偽隨機(jī)數(shù)存在的兩個(gè)問(wèn)題 偽隨機(jī)數(shù)的周期和最大容量,偽隨機(jī)數(shù),在計(jì)算機(jī)上產(chǎn)生隨機(jī)數(shù)最實(shí)用、最常見(jiàn)的方法是數(shù)學(xué)方法，即用如下遞推公式： 產(chǎn)生隨機(jī)數(shù)序列。對(duì)于給定的初始值1,2，k，確定n+k，=1，2，。經(jīng)常使用的是k=1的情況，其遞推公式為： 對(duì)于給定的初始值1，確定n+1，=,偽隨機(jī)數(shù)存在的兩個(gè)問(wèn)題,用數(shù)學(xué)方法產(chǎn)生的隨機(jī)數(shù)，存在兩個(gè)問(wèn)題： 遞推公式和初始值1,2，k確定后，整個(gè)隨機(jī)數(shù)序列便被唯一確定。不滿足隨機(jī)數(shù)相互獨(dú)立的要求。 由于隨機(jī)數(shù)序列是由遞推公式確定的，而在計(jì)算機(jī)上所能表示的0，1上的數(shù)又是有限的，因此，這種方法產(chǎn)生的隨機(jī)數(shù)序列就不可能不出現(xiàn)無(wú)限重復(fù)。一旦出現(xiàn)這樣的n，n (n n )，使得下面等式成立： 隨機(jī)數(shù)序列便出現(xiàn)了周期性的循環(huán)現(xiàn)象。對(duì)于k=1的情況，只要有一個(gè)隨機(jī)數(shù)重復(fù)，其后面的隨機(jī)數(shù)全部重復(fù)，這與隨機(jī)數(shù)的要求是不相符的。,由于這兩個(gè)問(wèn)題的存在，常稱用數(shù)學(xué)方法產(chǎn)生的隨機(jī)數(shù)為偽隨機(jī)數(shù)。對(duì)于以上存在的兩個(gè)問(wèn)題，作如下具體分析。 關(guān)于第一個(gè)問(wèn)題，不能從本質(zhì)上加以改變，但只要遞推公式選得比較好，隨機(jī)數(shù)間的相互獨(dú)立性是可以近似滿足的。至于第二個(gè)問(wèn)題，則不是本質(zhì)的。因?yàn)橛妹商乜_方法解任何具體問(wèn)題時(shí)，所使用的隨機(jī)數(shù)的個(gè)數(shù)總是有限的，只要所用隨機(jī)數(shù)的個(gè)數(shù)不超過(guò)偽隨機(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)的限制。因此，這種方法雖然存在著一些問(wèn)題，但仍然被廣泛地在計(jì)算機(jī)上使用，是在計(jì)算機(jī)上產(chǎn)生偽隨機(jī)數(shù)的主要方法。,偽隨機(jī)數(shù)的周期和最大容量,發(fā)生周期性循環(huán)現(xiàn)象的偽隨機(jī)數(shù)的個(gè)數(shù)稱為偽隨機(jī)數(shù)的周期。對(duì)于前面介紹的情況，偽隨機(jī)數(shù)的周期為nn。 從偽隨機(jī)數(shù)序列的初始值開(kāi)始，到出現(xiàn)循環(huán)現(xiàn)象為止，所產(chǎn)生的偽隨機(jī)數(shù)的個(gè)數(shù)稱為偽隨機(jī)數(shù)的最大容量。前面的例子中，偽隨機(jī)數(shù)的最大容量為n 。,產(chǎn)生偽隨機(jī)數(shù)的乘同余方法,乘同余方法是由Lehmer在1951年提出來(lái)的，它的一般形式是：對(duì)于任一初始值x1，偽隨機(jī)數(shù)序列由下面遞推公式確定： 其中a為常數(shù)。 (mod為取模運(yùn)算axk除以M后的余數(shù)）,乘同余方法的最大容量的上界,對(duì)于任意正整數(shù)M，根據(jù)數(shù)論中的標(biāo)準(zhǔn)分解定理，總可以分解成如下形式： 其中P0=2，P1， Pr表示不同的奇素?cái)?shù)，0表示非負(fù)整數(shù)，1，r表示正整數(shù)。a無(wú)論取什么值，乘同余方法的最大容量的上界為： 的最小公倍數(shù)。其中：,關(guān)于a與x1的取值,如果a與x1滿足如下條件： 對(duì)于 ， x1與M互素，則乘同余方法產(chǎn)生的偽隨機(jī)數(shù)序列的最大容量達(dá)到最大可能值(M)。,乘同余方法在計(jì)算機(jī)上的使用,為了便于在計(jì)算機(jī)上使用，通常取 ： =2s 其中s為計(jì)算機(jī)中二進(jìn)制數(shù)的最大可能有效位數(shù) x1= 奇數(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ù)的乘加同余方法,產(chǎn)生偽隨機(jī)數(shù)的乘加同余方法是由Rotenberg于1960年提出來(lái)的，由于這個(gè)方法有很多優(yōu)點(diǎn)，已成為僅次于乘同余方法產(chǎn)生偽隨機(jī)數(shù)的另一主要方法。 乘加同余方法的一般形式是，對(duì)任意初始值x1，偽隨機(jī)數(shù)序列由下面遞推公式確定： 其中a和c為常數(shù)。,乘加同余方法的最大容量,關(guān)于乘加同余方法的最大容量問(wèn)題，有如下結(jié)論：如果對(duì)于正整數(shù)M的所有素?cái)?shù)因子P，下式均成立： 當(dāng)M為4的倍數(shù)時(shí)，還有下式成立： c與M互素，則乘加同余方法所產(chǎn)生的偽隨機(jī)數(shù)序列的最大容量達(dá)到最大可能值M。,M，x1，a，c的取值,為了便于在計(jì)算機(jī)上使用，通常取 M = 2s 其中s為計(jì)算機(jī)中二進(jìn)制數(shù)的最大可能有效位數(shù)。 a = 2b + 1 (b2) c = 1 這樣在計(jì)算中可以使用移位和指令加法，提高計(jì)算速度。,產(chǎn)生偽隨機(jī)數(shù)的其他方法,取中方法 加同余方法,偽隨機(jī)數(shù)序列的均勻性和獨(dú)立性,判斷偽隨機(jī)數(shù)序列是否滿足均勻和相互獨(dú)立的要求，要靠統(tǒng)計(jì)檢驗(yàn)的方法實(shí)現(xiàn)。對(duì)于偽隨機(jī)數(shù)的統(tǒng)計(jì)檢驗(yàn)，一般包括兩大類：均勻性檢驗(yàn)和獨(dú)立性檢驗(yàn)。 六十年代初，人們開(kāi)始用定性的方法研究偽隨機(jī)數(shù)序列的均勻性和獨(dú)立性問(wèn)題，簡(jiǎn)要敘述如下。,偽隨機(jī)數(shù)的均勻性,這里只考慮偽隨機(jī)數(shù)序列1,2，n全體作為子樣時(shí)的均勻性問(wèn)題。其中n為偽隨機(jī)數(shù)序列的最大容量。 對(duì)于任意的0x1，令Nn(x)表示偽隨機(jī)數(shù)序列1,2，n中適合不等式 i x i=1，2，n 的個(gè)數(shù)，則 標(biāo)志偽隨機(jī)數(shù)序列1,2，n的均勻程度，稱為均勻偏度。,將偽隨機(jī)數(shù)序列1,2，n從小至大重新排列 并令 ，則由(n)的定義，容易證明 很明顯，對(duì)于固定的，(n)的值越小越好。它是描述偽隨機(jī)數(shù)序列均勻程度的基本量。對(duì)于任意隨機(jī)數(shù)序列，均有如下不等式成立： 當(dāng) 時(shí)，所對(duì)應(yīng)的偽隨機(jī)數(shù)序列為最佳分布。,可以證明，偽隨機(jī)數(shù)序列為最佳分布的充要條件是它取遍序列 的所有值。 對(duì)于計(jì)算機(jī)上使用的乘同余方法，按照前面介紹的方法選取a、x1時(shí)，所產(chǎn)生的偽隨機(jī)數(shù)序列的均勻偏度 對(duì)于乘加同余方法 對(duì)于部分偽隨機(jī)數(shù)的均勻性問(wèn)題通常用統(tǒng)計(jì)檢驗(yàn)方法檢驗(yàn)。,偽隨機(jī)數(shù)的獨(dú)立性,對(duì)于任意 ，令 表示(1,2)， (2,3)， (n,n+1)中適合不等式 的個(gè)數(shù)，根據(jù)隨機(jī)變量間相互獨(dú)立的定義和頻率近似概率的方法，令 則