第六章隨機數生成器

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

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

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

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

如果n足夠大(n≥4000)，R近似滿足自由度為6的分布。第22頁，課件共25頁，創作于2023年2月相關性檢驗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.