訪客IP:54.81.71.187
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
本論文永久網址: 
line
研究生:孟祥仁
研究生(外文):Shiang-Ren Mong
論文名稱:隨機數的統計檢定與比較
論文名稱(外文):Comparing random number generators by statistical tests
指導教授:蔡桂宏
指導教授(外文):Gwei-Hung Tsai
學位類別:碩士
校院名稱:銘傳大學
系所名稱:風險管理與統計資訊研究所碩士班
學門:商業及管理學門
學類:風險管理學類
論文出版年:2006
畢業學年度:92
語文別:中文
論文頁數:107
中文關鍵詞:隨機數產生器線性同餘法多項遞迴法DX-1511組合法隨機數檢定隨機數週期二維格子結構
外文關鍵詞:RNGLCGMRGDX-1511combination generatorrandom number testrandom number periodtwo-dimension lattice plot
相關次數:
  • 被引用被引用:7
  • 點閱點閱:113
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
由於電腦發展的普及,在許多的科學研究裡,電腦經被當作輔助的工具。在統計的領域裡,常會參考電腦模擬的結果,來處理較為複雜的問題;而在數學方面,也可利用電腦模擬的方法,來解決數值分析上的問題,例如蒙地卡羅應用在多維度的積分上。所以,如何產生良好的隨機數數列是值得我們去深入研究的課題。然而,一個好的隨機數產生器(Random Number Generator;RNG)必須滿足下列之特性:1. 隨機性(Randomness)、2. 長週期(Long Period)、3. 有效性(Efficiency)、4. 可攜帶性(Portability)、5. 可重複性(Repeatability)。
本文主要是利用Visual Basic 6.0來撰寫隨機數產生器及統計檢定之程式。在隨機數產生器方面,選擇較被廣泛使用的線性同餘產生器(Linear Congruential Generator;LCG),具有目前最長週期紀錄的DX-1511 法(多項遞迴法的推廣)以及組合法。對隨機數產生器所產生之隨機數列做各項比較統計及檢定,得到了DX1511法具有相對較好的統計性質,故針對DX-1511法改變遞迴式中的係數及modulus p,以驗證其穩定性。同時利用二維格子結構圖以比較各隨機數產生器,在兩維度的平面是否具有某些規律性存在。本文主要是透過多種比較統計檢定方法能夠分辨出各隨機數產生器之差異。
Because the efficiency and less cost of computer, the computer is used to contribute many scientific researches. In recent researches, we often deal with complicate problems by referring to the results of the computer simulations. We can also numerically solve problems, such as doing numerical analysis and applying Monte Carlo method for high dimensional integrals. As a consequence, the subject, how to generate better random number sequences, is worthy to investigate. A fine random number sequence has to satisfy the following five characteristics: 1.Randomness 2.Long Period 3.Efficiency 4.Portability 5.Repeatability.
In this thesis, I distinguish the differences of random number generators by ten statistical tests. I write programs of random number generators and statistical tests mainly by using software Visual Basic 6.0 and Maple 9. For random number generators, I choose the Linear Congruential Generator (LCG) which is widely used in recent times, the DX-1511 which is a kind of Multiple Recursive Generator (MRG) with the longest period in current record, and the combination generator. I compare statistical properties by using various empirical tests on random sequences generated from these random number generators. I obtain the result that the DX-1511 generator is the champion considering all the five mentioned characteristics. As a consequence, I also demonstrate the stability of the DX-1511 Generator by changing the multiplier coefficient a and the modulus p. I also judge against these random number generators by using two-dimension lattice plot, and evaluate if there exist some patterns.
目錄
第一章 緒論………….………………………….……………1
第一節 研究背景與動機……………………………………1
第二節 研究目的……………………………………………3
第三節 研究步驟……………………………………………3
第四節 研究範圍與限制............................5
第二章 文獻探討…………...…………………………………6
第三章 研究方法…………...………………………………..14
第一節 統計檢定……………………………………….….14
第二節 隨機數產生器之基本性質…………………….….20
第四章 資料分析…………………………………………….21
第一節 隨機數產生器的選取……………………………..21
第二節 隨機數之統計檢定………………………………..23
第三節 隨機數產生器之評比……………………………..54
第四節 改變DX-1511係數的比較…………………….…58
第五節 二維格子結構圖……………………………….….80
第五章 結論與建議………………………………………….85
第一節 結論…………………………………………….…85
第二節 建議…………………………………………….…88
參考文獻…………………...………………………………....89
附錄一(visual Basic 6.0隨機數產生器程式碼)…………….94
附錄二(Visual Basic 6.0統計檢定程式碼)…………............96
附錄三(Maple 9隨機數產生器程式碼)…………………...105
附錄四(Maple 9二維格子圖程式碼)……………………...106
圖目錄
圖1.3.1:研究架構圖………………………………………………….4
圖4.5.1:二維格子結構圖比較(X軸之值固定在(0,1))..…………...81
圖4.5.2:二維格子結構圖比較(X軸之值固定在(0.70,0.71)).….….82
圖4.5.3:二維格子結構圖比較(X軸之值固定在(0.700,0.701))…...83
圖4.5.4:二維格子結構圖比較(X軸之值固定在(0.7000,0.7001))...84
表目錄
表 4.2.1:卡方檢定例子……………………………………………..23
表4.2.2:均等區間的卡方檢定模擬結果…………………………...24
表4.2.3:升降趨勢檢定模擬結果…………………………………...26
表4.2.4:樸克檢定例子……………………………………………...27
表4.2.5:樸克檢定模擬結果………………………………………...28
表4.2.6:二項分配的卡方檢定例子(n=10)…………………………29
表4.2.7:二項分配的卡方檢定模擬結果(n=10)……………………30
表4.2.8:二項分配的卡方檢定模擬結果(n=20)……………………31
表4.2.9:二項分配的卡方檢定模擬結果(n=30)……………………32
表4.2.10:二項分配的卡方檢定模擬結果(n=40)…………………..33
表4.2.11:二項分配的卡方檢定模擬結果(n=50)…………………..34
表4.2.12:和的常態檢定例子(n=36)………………………………..35
表4.2.13:和的常態檢定模擬結果(n=36)…………………………..36
表4.2.14:和的常態檢定模擬結果(n=64)…………………………..37
表4.2.15:和的常態檢定模擬結果(n=100)…………………………38
表4.2.16:序列檢定例子(d=5)………………………………………39
表4.2.17:序列檢定模擬結果(d=5)…………………………………40
表4.2.18:序列檢定模擬結果(d=10)………………………………..41
表4.2.19:排列檢定例子…………………………………………….42
表4.2.20:排列檢定模擬結果……………………………………….43
表4.2.21:間隔檢定例子…………………………………………….44
表4.2.22:間隔檢定模擬結果……………………………………….45
表4.2.23:K-S檢定例子……………………………………………..46
表4.2.24:K-S檢定模擬結果………………………………………..47
表4.2.25:相關檢定模擬結果(a=2)………………………………….49
表4.2.26:相關檢定模擬結果(a=11)………………………………...50
表4.2.27:相關檢定模擬結果(a=73)………………………………...51
表4.2.28:相關檢定模擬結果(a=3)………………………………….52
表4.2.29:隨機數產生器統計檢定整理表…………………………..53
表4.3.1:電腦執行時間……………………………………………....55
表4.3.2:利用VB 6.0與Maple 9產生LCG法隨機數列………….55
表4.3.3:利用VB 6.0與Maple 9產生DX-1511-2法隨機數列…...56
表4.3.4:利用VB 6.0與Maple 9產生DX-1511-2法隨機數列…...56
表4.3.5:利用VB 6.0與Maple 9產生組合法隨機數列…………...56
表4.3.6:隨機數產生器基本性質整理表……………………………57
表4.4.1:改變DX-1511法係數均等區間的卡方檢定模擬結果…...59
表4.4.2:改變DX-1511法係數升降趨勢檢定模擬結果…………...60
表4.4.3:改變DX-1511法係數樸克檢定模擬結果………………...61
表4.4.4:改變DX-1511法係數二項分配的卡方檢定模擬結果(n=10).62
表4.4.5:改變DX-1511法係數二項分配的卡方檢定模擬結果(n=20).63
表4.4.6:改變DX-1511法係數二項分配的卡方檢定模擬結果(n=30).64
表4.4.7:改變DX-1511法係數二項分配的卡方檢定模擬結果(n=40).65
表4.4.8:改變DX-1511法係數二項分配的卡方檢定模擬結果(n=50).66
表4.4.9:改變DX-1511法係數和的常態檢定模擬結果(n=36)……67
表4.4.10:改變DX-1511法係數和的常態檢定模擬結果(n=64)…..68
表4.4.11:改變DX-1511法係數和的常態檢定模擬結果(n=100)…69
表4.4.12:改變DX-1511法係數序列檢定模擬結果(d=5)…………70
表4.4.13:改變DX-1511法係數序列檢定模擬結果(d=10)………..71
表4.4.14:改變DX-1511法係數排列檢定模擬結果……………….72
表4.4.15:改變DX-1511法係數間隔檢定模擬結果……………….73
表4.4.16:改變DX-1511法係數K-S檢定模擬結果……………….74
表4.4.17:改變DX-1511法係數相關檢定模擬結果(a=2)………….75
表4.4.18:改變DX-1511法係數相關檢定模擬結果(a=11)………...76
表4.4.19:改變DX-1511法係數相關檢定模擬結果(a=73)………...77
表4.4.20:改變DX-1511法係數相關檢定模擬結果(a=3)………….78
表4.4.21:改變DX-1511係數統計檢定整理表……………………..79
參考文獻
唐惠欽,多階質數乘餘法亂數產生器之分析探討,成功大學工業管理研究所博士論文,1997.
唐惠欽,二階質數相乘餘數法亂數產生器之設計,成功大學工業管理研究所碩士論文,1990.
張浩如,常用統計套裝軟體的U(0,1)亂數產生器之探討,政治大學統計研究所碩士論文,2000.
顏月珠,無母數統計方法,台北:陳昭明,1994。
吳明哲、黃世陽、何嘉益、張志成、曹祖聖、吳志忠,Visual Basic 6.0中文版學習範本,台北:文魁資訊股份有限公司,2002。
Deng, L. Y., “Uniform random numbers”, Encyclopedia of Biostatistics, (Editors P. Armitage and T. Colton), John Wiley & Sons, Volume 5, pages 4651-4656, 1998.
Deng, L. Y. and Dennis K. J. Lin, “ Random number generation for the new century”, American Statistician, Vol 54, No. 2, pages 145-150, 2000.
Deng, L. Y. and H. Q. Xu, “A System of High-dimensional, Efficient, Long-cycle and Portable Uniform Random Number Generators’’, ACM Transactions on Modeling and Computer Simulation, Vol. 13, No. 4, pages 299-399, 2003.
Deng, L. Y., ”Generalized Mersenne Prime Number and Its Application to Random Number Generation’’, in Monte Carlo and Quasi-Monte Carlo Methods 2002 (H. Niederreiter, ed.), to appear, 2004.
Deng, L.Y. C. Rousseau and Y. Yuan (1992), “Generalized Lehmer- Tausworthe random number generators”, in: Proceedings of the 30th Annual ACM Southeast Regional Conference, Raleigh, North Carolina, April 8-10 , 108-115.
Eichenauer, J. and Grothe, H., A remark on long-range correlations in multiplicative congruetial pseudo random number generators, Numer. Math., 56(1989), 609-611.
Eichenauer, J. and Grothe, H. and Lehn, J., Marsaglia’s lattice test and non-linear congruential pseudo random generators, Metrika, 35(1988), 241-250.
Eichenauer, J. and Lehn, J., A non-linear congruential pseudo random number generator, Statist. Papers, 27(1986), 315-326.
Franklin, J. N. (1964), “Equidistribution of matrix-power residues modulo one ,” Math. Comp., 18 , 560-568.
Golomb, S. W. (1967), Shift Register Sequence, Holden-Day: San Francisco.
Grothe, H. (1987), “Matrix generators for pseudo-random vector generation,” Statist. Papers, 28, 233-238.
James, F., A review of pseudorandom number generators, Comp. Physics Commu., 60(1990), 329-344.
Knuth, D. E., The art of computer programming Vol 2: Semi-numerical Algorithms, 2nd ed., Addison-Wesley, Reading MA, 1981.
Knuth, D. E. (1981), The Art of Computer Programming, Addison-Wesley: Reading, Mass, Vol 2: Seminumerical Algorithms, Second Edition.
L’Ecuyer, P. and Blouin, F., Linear congruential generators of order K>1, 1988 Winter Simul. Conf.(1988), 432-439.
L’Ecuyer, P. and Blouin, F. and Couture, R., A search for good multiple recursive random number generators, ACM Trans. Modeling and Computer Simu., 3(1993), 87-98.
L’Ecuyer, P. and Proulx, R., About polynomial —time “unpredictable” generators, Proc. Of the 1989 Winter Simul. Conf.(1989), 467-476.
L’Ecuyer, P. (1990), “Random numbers for simulation,” Communications of the ACM, 33, 85-97.
Lehmer, D. H., Proc. 2nd symp. On large-scale digital calculating machinery, Cambridge: Harvard University Press(1951), 141-146.
Lidl, R and H. Niederreiter (1986), Introduction to Finite Fields and Their Applications, Cambridge University Press: Cambridge.
Marsaglia, G., Random number fall mainly in the planes, Proc. Nat. Acad. Sci., 60(1968), 25-28.
Marsaglia, G., A cuttent view of random number generation, Computer Science and Statistics, Proceeding of sixteenth Symposium on the Interface, Atlanta, march 1984. Elsevier Science Publ.(North-Holland), 1985, 3-10.
Marsaglia, G. and Tsay, L. H., Matrices and the strecture of random number sequences, Linear Algebraic and Its Appl., 67(1985), 147-156.
Pagnutti, S and A. De Mattesis., Parallelization of random number generators and long-range correlation, Numer. Math., 53(1988), 595-608.
Neiderreiter, H., Statisticl independence of linear congruential pseudorandom numbers, Bull. Amer. Math. Soc.,82(1976), 927-929.
Neiderreiter, H., Pseudo-random numbers and optimal cofficents, Adv. Math., 26(1977), 99-181.
Neiderreiter, H., The serial test for linear congruential pseudorandom numbers, Bull. Amer. Math. Soc., 84(1978), 273-274.
Neiderreiter, H., Statisticl independence of nonlinear congruential pseudorandom numbers, Monatsh. Math., 106(1988), 149-159.
Neiderreiter, H., Recent trends in random number and random vector generation, Annals of Operations Research, 31(1991), 323-346.
Neiderreiter, H., Random number generation and quasi-Monte Carlo Methods, SIAM, Philadephia, 1992.
Neiderreiter, H., Pseudorandom number and quasirandom points, Z. angew. Math. Mech., 73(1993), T648-T652.
Niederreiter, H. (1986), “A pseudorandom vector generstor based on finite field arithmetic, ‘ Math. Japon., 31, 759-774.
Niederreiter, H. (1990), “Statistical independence properties of pseudorandom vectors produced by matrix generators,” J. Comput. Appl. Math., 31, 139-151.
Park, S. K. and Miller, K. W., Random numbers generators :Good ones are hard to find, Commun. Physics, 77(1988), 267-269.
Ripley, B.D., Stochastic Simulation, New York, Wiley, 1987.
Ripley, B. D., The lattice structure of pseudorandom number generators, Proc. Roy. Soc. London, Series A, 389(1983), 197-204.
Ripley, B. D., Thoughts on pseudorandom number generator, J. of Comput. and Applied Math., 31(1990), 153-163.
Tausworthe, R. C., Random number generated by linear recurrence modulo two, Math. Comput., 19(1965), 201-209.
Tausworthe, R. C. (1965) ,”Random numbers generated by linear recurrence modulo two,” Math. Comp, 19,201-209.
Zierler, N. (1959) , “Linear recurring sequences,” J. SIAM, 7, 31-48.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔