On the Average Discrepancy of Successive Tuples of Pseudo-Random Numbers over Parts of the Period

 In the present paper we give an upper and a lower bound for the average value of the discrepancy of non-overlapping s-tuples of successive elements of a first order congruential pseudo-random-number generator (with prime modulus and maximal period). The estimates are – up to logarithmic factors – sharp also for short parts of the period. Received 30 January 1997; in revised form 2 May 1997