On the discrepancy of quadratic congruential pseudorandom numbers with power of two modulus
type: Item
instance of: scholarly article
title: On the discrepancy of quadratic congruential pseudorandom numbers with power of two modulus
zbMATH Open document ID: 0827.65003
DOI: 10.1016/0377-0427(94)90064-7
published in: Journal of Computational and Applied Mathematics
publication date: 1995-12-11T00:00:00Z
review text: Consider an integer-valued sequence \(y_{n+1} = ay^2_n + by_n + c \text{ mod }m\) \((m = 2^l\geq 5)\). Then \[ (x_n \equiv y_n/m)_{n \geq 0} \subset [0,1) \] serves as a pseudorandom sequence approximating the independently sampled realizations of a random variable with the uniform distribution on \([0,1)\). For any fixed integer \(k \geq 3\) consider a statistical discrepancy of \(N\) generated \(k\)-tuples \({\mathbf x}_0, {\mathbf x}_1, \dots, {\mathbf x}_{N - 1}\) from \([0,1)^k\) defined as \(D^{(k)}_N = \sup_J \left |{\#({\mathbf x}_i \in J) \over N} - \text{Volume}(J) \right |\), where \(J\) is a \(k\)- dimensional cube \(\subset [0,1)^k\) and \({\mathbf x}_n = (x_n, x_{n+1}, \dots, x_{n + k - 1}) \in [0,1)^k\). It is shown that \(D^{(k)}_m \geq \text{Const }m^-{1\over 3}\) and a disappointing conclusion about the goodness of the generator is reached based on the probabilistic result \(D^{(k)}_m \geq \text{Const }m^{-{1\over 2}}\) for a truly random sequence. Unfortunately, such a comparison is not well suited here because the probabilistic analysis assumes the \(k\)-tuples to be independent random vectors, whereas in the case under consideration the successive \(k\)- tuples have \(k - 1\) random variables in common, which makes them highly correlated and consequently a larger discrepancy factor ought to be exptected (as proven by the author, via complex exponential sum technique for integer-lattice). Incidently, it would be of interest to obtain the discrepancy estimate for the nonoverlapping \(k\)-tuples, which is expected to only decrease, and might reveal the actual goodness (or lack of it) of the generator in question.
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 11K45
zbMATH DE Number: 721016
zbMATH Keywords: quadratic congruential pseudorandom numbers
zbMATH Keywords: law of the iterated logarithm
zbMATH Keywords: statistical discrepancy
zbMATH Keywords: complex exponential sum
author: Jürgen Eichenauer-Herrmann
reviewed by: A. Korzeniowski
MaRDI profile type: Publication
full work available at URL: 0377-0427(94)90064-7
OpenAlex ID: W1974773451
cites work: A remark on the discrepancy of quadratic congruential pseudorandom numbers
cites work: Inversive Congruential Pseudorandom Numbers: A Tutorial
cites work: On the discrepancy of quadratic congruential pseudorandom numbers
cites work: On large deviations of the empiric D.F. of vector chance variables and a law of the iterated logarithm
cites work: Q3935355
cites work: Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers
cites work: Recent trends in random number and random vector generation
cites work: Q4003879
description: scientific article; zbMATH DE number 721016