Long range correlations in linear congruential generators (Q1102692)

Different methods for generating sequences \(\{\) X(n)\(|\) \(n\in N\}\) of independently and uniformly distributed random numbers are proposed in the literature. The simple linear congruential generator \(X(n)\equiv a.X(n-1)+b\) (mod M) is recommended especially for use in mini and microcomputers. The parameters a, b (and sometimes M) are chosen to ensure the randomness of the sequence \(\{\) X(n)\(|\) \(n\in N\}.\) In this paper the authors study the case \(M=2\) d. They establish that for a fixed k, among the terms \(X(n+j.2\) k), \(1\leq j\leq p\), there exists a linear relation \(\sum^{p}_{j=0}c_ j.X(n+j.2\quad k)\equiv 0\) (mod 2 d). Therefore a linear congruential generator (with \(M=2\) d) introduces correlations among elements separated sequentially by powers of two. Hence more care must be taken for Monte Carlo procedures; the authors suggest to skip members of the sequence \(\{\) X(n)\(\}\) or to do a random change for the parameter b.