RECENT DEVELOPMENTS ON PSEUDO-RANDOM NUMBER GENERATORS AND THEIR THEORETICAL JUSTIFICATIONS

隨機數的最新進展與理論驗證

鄧利源(Lih-Yuan Deng)

《中國統計學報》 54卷4期 (2016/12) Pp. 154-179

摘要

To improve the performance of the classical Linear Congruential Generators (LCGs), it is common to consider two popular extensions: Multiple Recursive Generator (MRG) and Matrix Congruential Generator (MCG). MRG is generated from a linear combination of the past k pseudo-random numbers and MCG is a k-dimensional extension of the classical LCG. In this paper, we review some of the recent developments on the MRGs and MCGs and we also point out some of the research works needed such as their theoretical justifications. We develop a general theory for the asymptotic uniformity and independence of the MCGs, MRGs and combination generators to provide statistical justifications. Some intuitive discussions about these asymptotic results are also given.

關鍵字

Asymptotic independence ； asymptotic uniformity ； combination generators ； matrix congruential generator ； multiple recursive generator

並列摘要

為了提升古典線性同餘產生器(LCGs)隨機數的綜合性能，我們建議考慮兩個流行的擴展多項遞迴產生器(MRG)和矩陣同餘產生器(MCG)。多項遞迴產生器線性組合了前K個獨立的擬隨機數以遞迴式的產生下一個擬隨機數；而矩陣同餘產生器則使用K個線性獨立的方程式於一組K維向量產生的下一組K維向量。上述兩種產生器均可以視為線性同餘產生器的擴展。在本文中，我們回顧了一些多項遞迴產生器和矩陣同餘產生器的最新進展，也提供一些研究需要的理論與理據。並提出了漸近均勻性與漸近獨立性的一般理論可供多項遞迴產生器、矩陣同餘產生器或任何組合性隨機數產生器作為統計的理據。也在此討論一些直觀式的漸近結果。

並列關鍵字

中文關鍵詞 ； 近獨立 ； 漸近均勻性 ； 組合產生器 ； 多項遞迴產生器 ； 矩陣同餘產生器

參考文獻

Agrawal, M.,Kayal, N.,Saxena, N.(2004).Primes is in p..Annals of Mathematics.781-793.

Alanen, J.,Knuth, D. E.(1964).Tables of finite fields.Sankhyā: The Indian Journal of Statistics, Series A.305-328.

Anderson, S. L.(1990).Random number generators on vector supercomputers and other advanced architectures.Annals of Mathematics.32,221-251.

Bratley, P.,Fox, B. L.,Schrage, L. E.(1987).A Guide to Simulation.New York:Springer-Verlag.

Brown, M.,Solomon, H.(1979).On combining pseudorandom number generators.he Annals of Statistics.7(3),691-695.