### Serial Correlation in the Generation of Pseudo-Random NumbersSerial Correlation in the Generation of Pseudo-Random Numbers

Access Restriction
Subscribed

 Author Coveyou, R. R. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1960 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $\textit{P},$ the base; an integer λ, the multiplier, prime to $\textit{P};$ and an integer $\textit{μ},$ the increment, less than $\textit{P}$ $(\textit{μ}$ is frequently, but not always, zero). One then defines recursively a sequence $\textit{x}0,$ $\textit{x}1,$ $\textit{x}2,$ … (1) of integers by $\textit{x}0$ = $\textit{a},$ (2) $\textit{xn}+1$ ≡ $λ\textit{xn}$ + $\textit{μ}$ (mod $\textit{P}),$ (3) 0 ≦ $\textit{xn}$ < $\textit{P}.$ (4) It is clear that such a sequence is periodic with period $\textit{P}$ or less. Much work has been done on the determination of the period for various choices of $\textit{P},$ λ and $\textit{μ}$ [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 $\textit{P},$ machine convenience dictates the choices $\textit{P}$ = $2\textit{q}$ or $\textit{P}$ = $10\textit{q}$ for a $\textit{q}-place$ binary or decimal machine, respectively. No other choice of $\textit{P}$ appears to have any practical advantage whatever. As for λ and $\textit{μ}$ 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 λ and $\textit{μ}$ are such that the sequence (1) has an adequately long period. Then, clearly, one may assume, with error of order $1/\textit{P}$ or less, that the sequence (1) is continuously and uniformly distributed on the interval (0, $\textit{P}).$ Then, if $(&lpargt;\textit{Z}⦔)$ denotes the mean value of $\textit{Z},$ $&lpargt;\textit{xn}⦔$ = $1/\textit{P}$ $∫\textit{P}0$ x dx = $\textit{P}/2$ (5) $&lpargt;\textit{xn}2⦔$ = $1/\textit{P}$ $∫\textit{P}0$ $\textit{x}2$ $\textit{dx}$ = $\textit{P}2/3$ (6) and Var $(\textit{xn})$ = $\textit{P}2/3$ - $\textit{P}2/4$ = $\textit{P}2/12.$ (7) Further, one may write $\textit{xn}+1$ = $\textit{P}{(λ\textit{xn}$ + $\textit{μ})\textit{P}-1};$ (8) where {···} denotes “fractional part of.” (9) Also $&lpargt;\textit{xnxn}+1⦔$ = $1/\textit{P}$ $∫\textit{P}0$ $\textit{xP}$ ${(λ\textit{x}$ + $\textit{μ})\textit{P}-1}$ $\textit{dx}.$ (10) An elementary but tedious integration yields (see Appendix) $&lpargt;\textit{xnxn}+1⦔$ = $\textit{P}2/4$ + $\textit{P}2$ - $6\textit{μ}(\textit{P}$ - $\textit{μ})/12λ.$ (10′) Hence cov $(\textit{xn},$ $\textit{xn}+1)$ = $\textit{P}2$ - $6\textit{μ}(\textit{P}$ - $\textit{μ})/12λ,$ (11) and, if $\textit{&rgr;}$ $(\textit{x},$ $\textit{y})$ = the correlation coefficient of $\textit{x}$ and $\textit{y},$ (12) then &rgr; $(\textit{xn},$ $\textit{xn}+1)$ = 1 - 6 $\textit{μ}/\textit{P}$ (1 - $\textit{μ}/\textit{P})/λ.$ (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 $\textit{very}$ small values of λ and $\textit{μ}$ 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 $\textit{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 $\textit{xn}+\textit{p}$ ≡ $λ\textit{p}\textit{xn}$ + $\textit{μ}\textit{p}$ (mod $\textit{P}),$ (14) with $λ\textit{p}$ ≡ $λ\textit{p}$ (mod $\textit{P})$ (15) and $\textit{μ}\textit{p}$ ≡ $λ\textit{p}$ - 1/λ - 1 $\textit{μ}$ (mod $\textit{P}),$ (16) and again one may estimate the correlation with the use of equation (13). ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1960-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 7 Issue Number 1 Page Count 3 Starting Page 72 Ending Page 74

#### Open content in new tab

Source: ACM Digital Library