A Nonempirical Test on the Weight of Pseudorandom Number Generators
We introduce a theoretical test, named weight discrepancy test, on pseudorandom number generators. This test measures the X 2-discrepancy between the distribution of the number of ones in some specified bits in the generated sequence and the binomial dist
- PDF / 1,731,633 Bytes
- 15 Pages / 439.37 x 666.14 pts Page_size
- 27 Downloads / 185 Views
2
Faculty of IRS , Kyoto University, Kyot o 606-8501, JAPAN matumoto @math .h .kyoto-u .ac .jp Faculty of Science, Yam agat a University, Yam agata 990-8560 , JAPAN [email protected] agata-u .ac.jp
Abstract . We introduce a theoreti cal test , nam ed weight dis crepancy t est, on pseudor andom number gener ators. This test measures the X 2 -discrepancy between the distribution of the number of ones in some spec ified bits in t he gener ated sequ ence and t he binomial distribution, under t he assum ption that the initial value is randomly selected . This t est ca n be p erformed for most gener ators based on a linear recursion over the two-elem ent field lF2, and pr edict s with high pr ecision for which sample size the generator will be rej ect ed by a classical st atist ical t est called the weight dist ribution test . This test may be considere d as a theoreti cal version of a one-d imension al random walk t est . Differ ently from the empirical te st s which can reject only very bad generato rs, this t est assign s a ranking to generators. Thus it is useful t o select good generat ors, simil arly t o the sp ectral tests and the k-distribution t ests . This t est rejects pr actic ally all generators linear over lF2 that are known to fail in som e physical tests although they pass k-di stribution t ests .
1
Necessity of a theoretical test on weight
Among th e numerous pseudorandom number generators available, some are known to be defective , and some seem to be good. For more than thirty years , GFSRs[ll] based on three-term relations ar e known to suffer from statistical nonsymmetricity between a and 1, and to be rejected by x 2-test on the goodness-of-fit to the binomial distribution
[12][6][3][18][16] .
However, these warnings were not loud enough to reach the users. These three-t erm GFSRs were introduced to t he computational physics community by [8] suggesting the recursion X j = Xj-10 3 EEl Xj -250 , and became fairly popular. In middl e 80's, physicists began to find the failure of these generators in simulations of physical models, such as Ising mod els [5] [2] [1] and random walks [4]. These physical mod els ar e simplified and proposed as tests of randomness in [22], which we call physi cal tests here. In these works some phy sicists proposed two ways of improving GFSR: one is to increase the degree of t he recurrence (e.g. [2]) , and the other is to use five or mor e-term relations (e.g. [24]) . These follow from an intuitive observation K.‒T. Fang et al. (eds.)., Monte Carlo and Quasi-Monte Carlo Methods 2000 © Springer-Verlag Berlin Heidelberg 2002
382
t hat few-te rm relati ons in a short ra nge should lead to a deviation , and t hat increasin g t he numb er of terms or the ran ge of t he correlat ion will improve t he deviation. These imp rovements are shown to be effective in t he physical tests. However , it is not clear which degree will be sufficient, or how many terms are enough for th e required randomness. Five-t erm relations of degree 89 behave well for 106 samples, bu t are r
Data Loading...
