The serial test for pseudo-random numbers generated by the linear congruential method
type: Item
instance of: scholarly article
title: The serial test for pseudo-random numbers generated by the linear congruential method
zbMATH Open document ID: 0541.65004
DOI: 10.1007/BF01400255
author: Harald Niederreiter
published in: Numerische Mathematik
publication date: 1985-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/132982
review text: 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)].
Mathematics Subject Classification ID: 65C10
zbMATH DE Number: 3860271
zbMATH Keywords: discrepancy
zbMATH Keywords: serial test
zbMATH Keywords: pseudo-random numbers
zbMATH Keywords: linear congruential method
zbMATH Keywords: upper bounds
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
cites work: Optimal multipliers for pseudo-random number generation by the linear congruential method
cites work: Pseudo-Random Numbers: The Exact Distribution of Pairs
cites work: Q3259107
cites work: Q3935355
cites work: Q4767350
cites work: On the Distribution of Pseudo-Random Numbers Generated by the Linear Congruential Method
cites work: On the Distribution of Pseudo-Random Numbers Generated by the Linear Congruential Method. II
cites work: On the Distribution of Pseudo-Random Numbers Generated by the Linear Congruential Method. III
cites work: Pseudo-random numbers and optimal coefficients
cites work: The serial test for linear congruential pseudo-random numbers
cites work: Quasi-Monte Carlo methods and pseudo-random numbers
cites work: Q4194353
cites work: Q3938413
OpenAlex ID: W2058671594
description: scientific article; zbMATH DE number 3860271