zbMATH — the first resource for mathematics

Statistical independence of nonlinear congruential pseudorandom numbers. (English) Zbl 0652.65007
Nonlinear congruential pseudorandom numbers were introduced by J. Eichenauer, H. Grothe and J. Lehn [Metrika 35, 241-250 (1988))] in the following way. Let p be large prime and generate a sequence \(y_ 0,y_ 1,..\). of integers in \(F_ p=\{0,1,...,p-1\}\) by the recursion \(y_{n+1}\equiv f(y_ n)mod p\) for \(n=0,1,...\), where f is an integer-valued function on \(F_ p\) such that the sequence of \(y_ n\) is purely periodic with period \(p\) and \(\{y_ 0,y_ 1,...,y_{p- 1}\}=F_ p\). Then the pseudorandom numbers \(x_ n\) are obtained by \(x_ n=y_ n/p\). The following equivalent description was given by the author [Metrika (to appear)]: there exists a uniquely determined polynomial \(g\) over the finite field \(F_ p\) such that \(y_ n=g(n)\) for all \(n\in F_ p\) and \(1\leq s:=\deg (g)\leq p-2\), where \(\{g(0),g(1),...,g(p-1)\}=F_ p.\)
In the present paper the behavior of these pseudorandom numbers under the \(k\)-dimensional serial test is investigated by considering the discrepancy \(D_ N^{(k)}\) of the points \(\bar x_ n=(x_ n,x_{n+1},...,x_{n+k-1})\), \(n=0,1,...,N-1\). It is shown that \(D_ p^{(k)}=O(sp^{-1/2}(\log p)^ k)\) for all \(k\leq s\) and \(D_ N^{(K)}=O(N^{-1}sp^{1/2}(\log p)^{k+1})\) for \(1\leq N<p\) and all \(k\leq s-1\). It is also proved that these bounds are essentially best possible. As a consequence, nonlinear congruential pseudorandom numbers with an appropriate value of \(s\) have satisfactory statistical independence properties up to rather high dimensions.
Reviewer: H.Niederreiter

65C10 Random number generation in numerical analysis
11K16 Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc.
11K45 Pseudo-random numbers; Monte Carlo methods
Full Text: DOI EuDML
[1] Cochrane, T.: On a trigonometric inequality of Vinogradov. J. Number Th.27, 9-16 (1987). · Zbl 0629.10030
[2] Eichenauer, J., Grothe, H., Lehn, J.: Marsaglia’s lattice test and non-linear congruential pseudo random number generators. Metrika35, 241-250 (1988). · Zbl 0653.65006
[3] Eichenauer, J., Lehn, J.: A non-linear congruential pseudo random number generator. Statist. Hefte27, 315-326 (1986). · Zbl 0607.65001
[4] Eichenauer, J., Lehn, J., Topuzo?lu, A.: A non-linear congruential pseudo random number generator with power of two modulus. Math. Comp. (To appear.) · Zbl 0609.65005
[5] Knuth, D. E.: The Art of Computer Programming, vol. 2: Seminumerical Algorithms. 2nd ed. Reading: Addison-Wesley. 1981. · Zbl 0477.65002
[6] Lidl, R., Niederreiter, H.: Finite Fields. Reading: Addison-Wesley. 1983. · Zbl 0554.12010
[7] Marsaglia, G.: Random numbers fall mainly in the planes. Proc. Nat. Acad. Sci. U.S.A.61, 25-28 (1968). · Zbl 0172.21002
[8] Marsaglia, G.: The structure of linear congruential sequences. In: Applications of Number Theory to Numerical Analysis (Ed. by S. K. Zaremba), pp. 249-285. New York: Academic Press. 1972.
[9] Niederreiter, H.: Pseudo-random numbers and optimal coefficients. Adv. Math.26, 99-181 (1977). · Zbl 0366.65004
[10] Niederreiter, H.: Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Soc.84, 957-1041 (1978). · Zbl 0404.65003
[11] Niederreiter, H.: Number-theoretic problems in pseudorandom number generation. In: Proc. Symp. on Applications of Number Theory to Numerical Analysis, Lecture Notes No. 537, pp. 18-28. Kyoto: Research Inst. of Math. Sciences. 1984.
[12] Niederreiter, H.: The serial test for pseudo-random numbers generated by the linear congruential method. Numer. Math.46, 51-68 (1985). · Zbl 0554.65006
[13] Niederreiter, H.: Pseudozufallszahlen und die Theorie der Gleichverteilung. Sitzungsber. Ă–sterr. Akad. Wiss. Math.-Naturwiss. Kl.195, 109-138 (1986). · Zbl 0616.10040
[14] Niederreiter, H.: Remarks on nonlinear congruential pseudorandom numbers. Metrika. (To appear.) · Zbl 0663.65005
[15] Weil, A.: On some exponential sums. Proc. Nat. Acad. Sci. U.S.A.34, 204-207 (1948). · Zbl 0032.26102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.