Autocorrelation Peaks in Congruential Pseudorandom Number Generators

One of the desirable properties of a pseudorandom number generator is that the sequence of numbers it generates should have very low autocorrelation for all shifts except for zero shift and those that are multiples of its cycle length. Due to the simple methods of constructing random numbers via modulo arithmetic, the ideal is often not quite fulfilled. The results of this paper were obtained by the simple method of examining the complete correlation structure of several generators of the same type and small cycle length. Once the regularities were discovered, the mathematical relationships were derived which describe the regular behavior for all generators of the same class. As examples, it is shown in this paper that high correlation exists in mixed and multiplicative congruential random number generators and prime moduli Lehmer generators for shifts a fraction of their cycle lengths.