Access Restriction

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

   Open content in new tab
Source: ACM Digital Library