Serial Correlation in the Generation of Pseudo-Random Numbers

ABSTRACT

Many practiced and proposed methods for the generation of pseudo-random numbers for use in Monte Carlo calculation can be expressed in the following way: One chooses an integer P, the base; an integer &lgr;, the multiplier, prime to P; and an integer &mgr;, the increment, less than P (&mgr; is frequently, but not always, zero). One then defines recursively a sequence x0, x1, x2, … (1) of integers by x0 = a, (2) xn+1 ≡ &lgr;xn + &mgr; (mod P), (3) 0 ≦ xn < P. (4) It is clear that such a sequence is periodic with period P or less. Much work has been done on the determination of the period for various choices of P, &lgr; and &mgr; [1-7]. From this work one concludes that it is relatively easy to assure an adequately long period and that other considerations should determine the choice of these parameters. As for P, machine convenience dictates the choices P = 2q or P = 10q for a q-place binary or decimal machine, respectively. No other choice of P appears to have any practical advantage whatever. As for &lgr; and &mgr; it is the thesis of this note that they should be chosen to reduce serial correlation in the sequence (1), and we proceed to show how this may be done. We assume that &lgr; and &mgr; are such that the sequence (1) has an adequately long period. Then, clearly, one may assume, with error of order 1/P or less, that the sequence (1) is continuously and uniformly distributed on the interval (0, P). Then, if (&lpargt;Z⦔) denotes the mean value of Z, &lpargt;xn⦔ = 1/P ∫P0 x dx = P/2 (5) &lpargt;xn2⦔ = 1/P ∫P0 x2 dx = P2/3 (6) and Var (xn) = P2/3 - P2/4 = P2/12. (7) Further, one may write xn+1 = P{(&lgr;xn + &mgr;)P-1}; (8) where {···} denotes “fractional part of.” (9) Also &lpargt;xnxn+1⦔ = 1/P ∫P0 xP {(&lgr;x + &mgr;)P-1} dx. (10) An elementary but tedious integration yields (see Appendix) &lpargt;xnxn+1⦔ = P2/4 + P2 - 6&mgr;(P - &mgr;)/12&lgr;. (10′) Hence cov (xn, xn+1) = P2 - 6&mgr;(P - &mgr;)/12&lgr;, (11) and, if &rgr; (x, y) = the correlation coefficient of x and y, (12) then &rgr; (xn, xn+1) = 1 - 6 &mgr;/P (1 - &mgr;/P)/&lgr;. (13) One must be cautious of the conclusions one draws from (13) because of the approximate nature of its derivation. But one can say that a method which uses very small values of &lgr; and &mgr; is faulty. Unfortunately, such methods have been repeatedly suggested, and in one case within the author's knowledge serious difficulties were encountered in a Monte Carlo calculation because of the use of one such method. One should not lose sight of the fact that the correlation between a random number and its immediate successor is by no means the only one of importance. It is very difficult to give a precise rule, but it seems plausible that the correlation between the current random number and, at least, its next 10 or 20 successors should be controlled. Fortunately, for any such method one may write xn+p ≡ &lgr;pxn + &mgr;p (mod P), (14) with &lgr;p ≡ &lgr;p (mod P) (15) and &mgr;p ≡ &lgr;p - 1/&lgr; - 1 &mgr; (mod P), (16) and again one may estimate the correlation with the use of equation (13).

REFERENCES

• 1: D. H. LEHMER, Mathematical methods in large-scale computing units. Annals of the Computation Laboratory of Harvard University, No. 26, Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, p. 141 (1951).
• 2: J. TODD AND O. TAUSSKY TODD, "Generation of Pseudo-Random Numbers," in Symposium on Monte Carlo Methods (H. A. Meyer, Ed ), pp. 15-28 (John Wiley and Sons, New York, 1956).
• 3: M. L. JuscosA, Random number generation on the BRL high-speed computing machines, Report No. 855, Ballistics Research Laboratories, Aberdeen Proving Ground, Maryland, 1953.
• 4: D. L. jOHNSON, Generating and testing pseudo-random numbers on the IBM Type 701, Math. Tables Aids Comp. 10 (1956), 8-13.
• 5: Jack Moshman, The Generation of Pseudo-Random Numbers on a Decimal Calculator, Journal of the ACM (JACM), v.1 n.2, p.88-91, April 1954 [doi>10.1145/320772.320775]
• 6: Eve Bofinger , V. J. Bofinger, On a Periodic Property of Pseudo-Random Sequences, Journal of the ACM (JACM), v.5 n.3, p.261-265, July 1958 [doi>10.1145/320932.320937]
• 7: J. Certaine, On Sequences of Pseudo-Random Numbers of Maximal Length, Journal of the ACM (JACM), v.5 n.4, p.353-356, Oct. 1958 [doi>10.1145/320941.320949]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Performance, Theory