The most commonly used techniques to generate a sequence of pseudorandom numbers are those that apply some form of recursive computation. In principle, such recursive formulas are based on calculating the residuals modulo of some integers of a linear transformation. The process of producing a random number sequence is completely deterministic. However, the generated sequence would appear to be uniformly distributed and independent.
Congruential methods for generating n random numbers are based on the fundamental congruence relationship, which can be expressed as (Lehmer, 1951)
Xi+i = {aXi + c}(mod m) i = 1,2,…, n (6.1)
in which a is the multiplier, c is the increment, and m is an integer-valued modulus. The modulo notation (mod m) in Eq. (6.1) represents that
Xi+1 = aXi + c — mIi (6.2)
with Ii = [(aXi + c)/m] denoting the largest positive integer value in (aXi + c)/m. In other words, Xi+1 determined by Eq. (6.1) is the residual resulting from (aXi + c)/m. Therefore, the values of the number sequence generated by Eq. (6.1) would satisfy Xi < m, for all i = 1, 2,…, n. Random number generators that produce a number sequence according to Eq. (6.1) are called mixed congruential generators.
Applying Eq. (6.1) to generate a random number sequence requires the specification of a, c, and m, along with X0, called the seed. Once the sequence of random number Xs are generated, the random number from the unit interval ui є [0,1] can be obtained as
Ui = — i = 1, 2,…, n (6.3)
m
It should be pointed out that the process of generating uniform random numbers is the building block in Monte Carlo simulation.
Owing to the deterministic nature of the number generation, it is clear that the number sequence produced by Eq. (6.1) is periodic, which will repeat itself in, at most, m steps. This implies that the sequence would contain, at most, m distinct numbers and will have a maximum period of length m — 1 beyond which the sequence will get into a loop. For example, consider Xi+1 = 2Xi + 3(mod m = 5), with X0 = 3; the number sequence generated would be 4,1,0, 3,4,1,0,….
From the practical application viewpoint, it is desirable that the generated number sequence have a very long periodicity to ensure that sufficiently large amounts of distinct numbers are produced before the cycle occurs. Therefore, one would choose the value ofthe modulus m to be as large as possible. However, the length of the periodicity in a sequence also depends on the values of multiplier a and increment c. Knuth (1981) derived three conditions under which a sequence from Eq. (6.1) has a full period m. Based on the three conditions of Knuth (1981), Rubinstein (1981) showed that for a computer with a binary digit system, using m = 2в, with в being the word length of the computer, along with an odd number for parameter c and a = 2r + 1, r > 2 would produce a full period sequence. The literature (Hull and Dobell, 1964; MacLaren and Marsagalia, 1965; Olmstead, 1946) indicates that good statistical results can be achieved by using m = 235, a = 27 + 1, and c = 1. Table 6.2 lists suggested values for the parameters in Eq. (6.1) for different computers.
|
TABLE 6.2 Suggested Values for Parameters in Congruential Methods Constants for portable random number generators
SOURCE: After Press et al. (1989). |
A second commonly used generator is called the multiplicative generator-.
Xi+1 = {aXi }(mod m) i = 1,2,…, n (6.4)
which is a special case of the mixed generator with c = 0. Knuth (1981) showed that a maximal period can be achieved for the multiplicative generator in a binary computer system when m = 2e and a = 8r ± 3, with r being any positive integer.
Another type of generator is called the additive congruential generator having the recursive relationship as
Xi+1 = {Xi + Xi-t }(mod m) t = 1,2,…, i — 1 (6.5)
As can be seen, the random numbers generated by the additive congruen — tial generator depend on more than one of its preceding values. When t = 1, Eq. (6.5) would generate a sequence of Fibonacci numbers, which are not satisfactorily random. However, the statistical properties improve as t gets larger.
In summary, to ensure that a sequence of random numbers generated by the congruential methods would have satisfactory statistical properties, Knuth (1981) recommended the following principles to choose the parameters a, c, m, and X0. [9]
