The serial test for pseudo-random numbers generated by the linear congruential method
Let \(y_ 0,y_ 1,..\). be a sequence of integers in the least residue system mod m generated by the recursion \(y_{n+1}\equiv \lambda y_ n+r mod m\) for \(n=0,1,...\), and let \(x_ n=y_ n/m\in [0,1)\) be the corresponding linear congruential pseudo-random numbers. Here \(\lambda\) and m are relatively prime integers with \(2\leq \lambda<m\) and r is an integer \(\not\equiv(1-\lambda)y_ 0 mod m.\) The statistical independence of successive \(x_ n\) is analyzed by the serial test, which is a type of multivariate Kolmogorov test. For a given dimension s we consider the point \(\underline x_ n= (x_ n,x_{n+1},...,x_{n+s-1})\in [0,1)^ s, n=0,1,...\), and for \(N\geq 1\) we introduce the quantity \[ D_ N^{(s)}=\sup_{J}| F_ N(J)-Vol(J)|, \] where the supremum is extended over all subintervals J of \([0,1)^ s\), \(F_ N(J)\) is \(N^{-1}\) times the number of terms among \b{x}\({}_ 0,\underline x_ 1,...,\underline x_{N-1}\) falling into J, and Vol(J) denotes the volume of J. Since the sequence of \(x_ n\) is periodic (with least period \(\tau\), say), it suffices to consider N with 1\(\leq N\leq \tau\). Upper bounds for \(D_ N^{(s)}\) in the homogeneous case \(r\equiv 0\) mod m and with \(N=\tau\) were given earlier by the author [Advances Math. 26, 99-181 (1977; Zbl 0366.65004)]. In the present paper, upper bounds for \(D_ N^{(s)}\) are obtained for arbitrary r and arbitrary N, 1\(\leq N\leq \tau\). We also establish lower bounds for \(D_ N^{(s)}\) which, in the cases of practical interest, differ from the upper bounds only by logarithmic factors. We deal mainly with the most common choices for m, namely primes or prime powers. The case where m is a power of 10 has also been treated by the author [Proc. Third Pannonian Symp. on Math. Statistics, Visegrád, 1982, 255-269, Akadémiai Kiadó, Budapest (1983)].
- scientific article; zbMATH DE number 3868483
- Statistical independence of nonlinear congruential pseudorandom numbers
- scientific article; zbMATH DE number 4090661
- The Serial Test for Congruential Pseudorandom Numbers Generated by Inversions
- Marsaglia's lattice test and non-linear congruential pseudo-random number generators
- scientific article; zbMATH DE number 3141365 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 3753929 (Why is no real title available?)
- scientific article; zbMATH DE number 3633609 (Why is no real title available?)
- scientific article; zbMATH DE number 3440485 (Why is no real title available?)
- On the Distribution of Pseudo-Random Numbers Generated by the Linear Congruential Method
- On the Distribution of Pseudo-Random Numbers Generated by the Linear Congruential Method. II
- On the Distribution of Pseudo-Random Numbers Generated by the Linear Congruential Method. III
- Optimal multipliers for pseudo-random number generation by the linear congruential method
- Pseudo-random numbers and optimal coefficients
- Pseudo-Random Numbers: The Exact Distribution of Pairs
- Quasi-Monte Carlo methods and pseudo-random numbers
- The serial test for linear congruential pseudo-random numbers
- On the adequacy of pseudy-random number generators (or: How big a period do we need?)
- Evaluation of the discrepancy of the linear congruential pseudo-random number sequences
- Variants of the Koksma-Hlawka inequality for vertex-modified quasi-Monte Carlo integration rules
- A brief and understandable guide to pseudo-random number generators and specific models for security
- Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers
- The Serial Test for Congruential Pseudorandom Numbers Generated by Inversions
- scientific article; zbMATH DE number 4090661 (Why is no real title available?)
- On the autocorrelation structure of inversive congruential pseudorandom number sequences
- Statistical Independence of a New Class of Inversive Congruential Pseudorandom Numbers
- Pseudorandom Vector Generation by the Multiple-Recursive Matrix Method
- Parallel streams of linear random numbers in the spectral test
- The serial test for a nonlinear pseudorandom number generator
- On the discrepancy of quadratic congruential pseudorandom numbers
- Optimal coefficients modulo prime powers in the three-dimensional case
- Upper bounds for the Beyer ratios of linear congruential generators
- Statistical independence properties of pseudorandom vectors produced by matrix generators
This page was built for publication: The serial test for pseudo-random numbers generated by the linear congruential method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794386)
