On the discrepancy of quadratic congruential pseudorandom numbers with power of two modulus (Q1344347): Difference between revisions

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.