Statistical independence of nonlinear congruential pseudorandom numbers
type: Item
instance of: scholarly article
title: Statistical independence of nonlinear congruential pseudorandom numbers
zbMATH Open document ID: 0652.65007
DOI: 10.1007/BF01298835
author: Harald Niederreiter
published in: Monatshefte für Mathematik
publication date: 1988-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/178398
review text: Nonlinear congruential pseudorandom numbers were introduced by \textit{J. Eichenauer}, \textit{H. Grothe} and \textit{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.
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 11K16
Mathematics Subject Classification ID: 11K45
zbMATH DE Number: 4064342
zbMATH Keywords: statistical independence of nonlinear congruential pseudorandom numbers
zbMATH Keywords: Nonlinear congruential pseudorandom numbers
zbMATH Keywords: serial test
MaRDI profile type: Publication
cites work: On a trigonometric inequality of Vinogradov
cites work: Marsaglia's lattice test and non-linear congruential pseudo-random number generators
cites work: Q3746773
cites work: A multiple recursive nonlinear congruential pseudo random number generator
cites work: Q3935355
cites work: Q3216750
cites work: RANDOM NUMBERS FALL MAINLY IN THE PLANES
cites work: Pseudo-random numbers and optimal coefficients
cites work: Quasi-Monte Carlo methods and pseudo-random numbers
cites work: Q4724719
cites work: Remarks on nonlinear congruential pseudorandom numbers
cites work: On Some Exponential Sums
OpenAlex ID: W2022173438
description: scientific article; zbMATH DE number 4064342