第六章隨機數(shù)生成器

第六章隨機數(shù)生成器第1頁，課件共25頁，創(chuàng)作于2023年2月隨機數(shù)在離散系統(tǒng)仿真中，隨機數(shù)是一個必不可少的基本元素（0，1）均勻分布隨機數(shù)是產(chǎn)生其他許多分布的隨機數(shù)的基礎(chǔ)一個隨機數(shù)序列必須滿足兩個重要的統(tǒng)計性質(zhì)：均勻性和獨立性第2頁，課件共25頁，創(chuàng)作于2023年2月隨機數(shù)的性質(zhì)均勻性如果將區(qū)間[0，1]分為n個等長的子區(qū)間，那么在每個區(qū)間的期望觀測次數(shù)為N/n，其中N為觀測的總次數(shù)獨立性觀測值落在某個特定區(qū)間的概率與以前的觀測值無關(guān)第3頁，課件共25頁，創(chuàng)作于2023年2月隨機數(shù)的產(chǎn)生方法物理方法：利用某些物理過程來產(chǎn)生均勻分布隨機數(shù)隨機數(shù)表：利用物理過程得到的大量隨機數(shù)，制成隨機數(shù)表隨機數(shù)產(chǎn)生程序：按照一定的算法計算出具有類似于均勻分布隨機變量的獨立取樣值性質(zhì)的數(shù)偽隨機數(shù)第4頁，課件共25頁，創(chuàng)作于2023年2月計算機產(chǎn)生隨機數(shù)的要求產(chǎn)生的隨機數(shù)要盡可能的逼近理想的均勻性和獨立性統(tǒng)計性質(zhì)產(chǎn)生的隨機數(shù)要有足夠長的周期產(chǎn)生隨機數(shù)的速度要快，占用的內(nèi)存空間要小隨機數(shù)必須是可重復(fù)的對于給定的起始點或初始條件，應(yīng)當能夠產(chǎn)生相同的隨機數(shù)序列，而且與正被仿真的系統(tǒng)完全無關(guān)第5頁，課件共25頁，創(chuàng)作于2023年2月產(chǎn)生隨機數(shù)的算法是利用遞推公式：

第6頁，課件共25頁，創(chuàng)作于2023年2月平方取中法20世紀40年代由馮·諾依曼提出的第一個隨機數(shù)生成器例：設(shè)有一個4位正整數(shù)Z0，對之取平方得到一個8位正整數(shù)（如果不夠8位數(shù)，可以在左側(cè)加上0補足8位）。而后取中間的4位獲得一個新的4位正整數(shù)Z1。將Z1/10000得到一個[0，1]之間的小數(shù)，則獲得第一個“隨機數(shù)”U1。然后基于Z1重復(fù)上述操作，得到Z2和U2，依次類推……第7頁，課件共25頁，創(chuàng)作于2023年2月線性同余隨機數(shù)生成器（LCG）其中，a稱為乘法因子，c稱為加法因子，m為模數(shù)當a=1時，為加同余法；當c=0時，為乘同余法；當a≠1、c≠0時，為混合同余法第8頁，課件共25頁，創(chuàng)作于2023年2月例：使用線性同余法產(chǎn)生隨機數(shù)序列，其中Z0=27、a=17、c=43、m=100。解：Zk=(aZk-1+c)modmZ1=(17×27+43)mod100=502mod100=2Z2=(17×2+43)mod100=77mod100=77Z3=(17×77+43)mod100=1352mod100=52……U1=2/100=0.02,U2=77/100=0.77,U3=0.52第9頁，課件共25頁，創(chuàng)作于2023年2月LCG的周期用LCG方法產(chǎn)生的隨機數(shù)序列會出現(xiàn)周期循環(huán)的現(xiàn)象，一旦Zi取值和以前出現(xiàn)的某個值相同，此后的隨機數(shù)序列就開始循環(huán)。循環(huán)的長度稱為生成器的周期；由于0≤Zi≤m-1，因此最大周期是m，稱之為滿周期；為了產(chǎn)生成百上千的隨機數(shù)，必須采用周期足夠長的LCG，最好是滿周期的生成器，這樣對隨機數(shù)的均勻性也很有利。第10頁，課件共25頁，創(chuàng)作于2023年2月定理：LCG具有滿周期，當且僅當以下3個條件成立：1.m和c互質(zhì)；2.存在一個質(zhì)數(shù)q，能夠同時整除m和a-1；3.m和a-1能夠被4整除。第11頁，課件共25頁，創(chuàng)作于2023年2月模數(shù)m的取值為了使LCG的周期足夠長，m的取值應(yīng)該較大；為了加快計算機的處理速度，選擇m=2b，其中b為計算機CPU一次能處理的最大位數(shù)；目前b=32-1=31第12頁，課件共25頁，創(chuàng)作于2023年2月例：使用不同種子的周期使用乘同余法，對a=13、m=26=64且Z0=1,2,3,4,求產(chǎn)生器的周期。第13頁，課件共25頁，創(chuàng)作于2023年2月iXiXiXiXi0123411326395224118593632142632041734514529582365750437371047833235945710927115331124919136155142511155151613第14頁，課件共25頁，創(chuàng)作于2023年2月隨機數(shù)的檢驗為了檢驗產(chǎn)生的隨機數(shù)序列是否滿足均勻性和獨立性，有必要進行一系列的檢驗：均勻性檢驗（頻率檢驗）序列檢驗游程檢驗相關(guān)性檢驗第15頁，課件共25頁，創(chuàng)作于2023年2月均勻性檢驗其中，Oi為第i組中數(shù)據(jù)的觀測值個數(shù)，Ei為第i組中數(shù)據(jù)的期望個數(shù)，n為組數(shù)。

第16頁，課件共25頁，創(chuàng)作于2023年2月均勻性檢驗H0：Ri服從U[0，1]H1：Ri不服從U[0，1]檢驗方法：選定一個顯著性水平如果

第17頁，課件共25頁，創(chuàng)作于2023年2月序列檢驗序列檢驗是運用檢驗來檢驗隨機數(shù)序列的n維均勻性，以此判斷隨機數(shù)序列的獨立性。假設(shè)Ui是獨立同分布U(0,1)的隨機變量，則構(gòu)造n個d維隨機變量：U1=(U1,U2,…,Ud),U2=(Ud+1,Ud+2,…,U2d),…將[0,1]等分為k個子區(qū)間，則在d維空間中共有kd個子區(qū)間，n個隨機變量落在每個區(qū)間的個數(shù)期望值（期望頻度）為n/kd。設(shè)fj1,j2,…,jd為落在子區(qū)間j1j2…jd的觀測值個數(shù)（觀測頻度），第18頁，課件共25頁，創(chuàng)作于2023年2月序列檢驗則第19頁，課件共25頁，創(chuàng)作于2023年2月游程檢驗游程檢驗是一種對獨立性假設(shè)的更為直接的檢驗。對Ui序列進行檢驗，以得到Ui的不間斷子序列，每個子序列都是Ui單調(diào)增長的最長子序列，每個子序列稱為游程。例：[0.86],[0.11,0.23],[0.03,0.13],[0.06,0.55,0.64,0.87],[0.10]第20頁，課件共25頁，創(chuàng)作于2023年2月游程檢驗給定一個有n個Ui的序列，對長度為1,2,3,4,5,6…的游程進行計數(shù)，則可以定義則可構(gòu)造如下檢驗統(tǒng)計量：第21頁，課件共25頁，創(chuàng)作于2023年2月游程檢驗

如果n足夠大(n≥4000)，R近似滿足自由度為6的分布。第22頁，課件共25頁，創(chuàng)作于2023年2月相關(guān)性檢驗0.120.010.230.280.890.310.640.280.830.930.990.150.330.350.910.410.600.270.750.880.680.490.050.430.950.580.