# 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

##### MSC:
 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:
##### References:
  Cochrane, T.: On a trigonometric inequality of Vinogradov. J. Number Th.27, 9-16 (1987). · Zbl 0629.10030  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  Eichenauer, J., Lehn, J.: A non-linear congruential pseudo random number generator. Statist. Hefte27, 315-326 (1986). · Zbl 0607.65001  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  Knuth, D. E.: The Art of Computer Programming, vol. 2: Seminumerical Algorithms. 2nd ed. Reading: Addison-Wesley. 1981. · Zbl 0477.65002  Lidl, R., Niederreiter, H.: Finite Fields. Reading: Addison-Wesley. 1983. · Zbl 0554.12010  Marsaglia, G.: Random numbers fall mainly in the planes. Proc. Nat. Acad. Sci. U.S.A.61, 25-28 (1968). · Zbl 0172.21002  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.  Niederreiter, H.: Pseudo-random numbers and optimal coefficients. Adv. Math.26, 99-181 (1977). · Zbl 0366.65004  Niederreiter, H.: Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Soc.84, 957-1041 (1978). · Zbl 0404.65003  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.  Niederreiter, H.: The serial test for pseudo-random numbers generated by the linear congruential method. Numer. Math.46, 51-68 (1985). · Zbl 0554.65006  Niederreiter, H.: Pseudozufallszahlen und die Theorie der Gleichverteilung. Sitzungsber. Österr. Akad. Wiss. Math.-Naturwiss. Kl.195, 109-138 (1986). · Zbl 0616.10040  Niederreiter, H.: Remarks on nonlinear congruential pseudorandom numbers. Metrika. (To appear.) · Zbl 0663.65005  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.