The serial test for pseudo-random numbers generated by the linear congruential method (Q794386)

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)].