UNIFORM PSEUDO-RANDOM VARIABLE GENERATION In this paragraph, our goals will be to look at, in more detail, how and whether particular types of pseudo-random variable generators work, and how, if necessary, we can implement a generator of our own choosing. Below a list of requirements is listed for our uniform random variable generator: A uniform marginal distribution, Independence of the uniform variables, Repeatability and portability, Computational speed.

CURRENT ALGORITHMS The generation of pseudo-random variates through algorithmic methods is a mature field in the sense that a great deal is known theoretically about different classes of algorithms, and in the sense that particular algorithms in each of those classes have been shown, upon testing, to have good statistical properties. In this section, let describe the main classes of generators, and then let make specific recommendation about which generators should be implemented.

Congruential Generators The most widely used and best understood class of pseudo-random number generators are those based on the linear congruential method introduced by Lehmer (1951). Such generators are based on the following formula: U i =( a U i−1 +c )mod⁡m , where U i ,i=1,2,... are the output random integers; U 0 is the chosen starting value for the recursion, called the seed and a,c, and m are prechosen constants. to convert to uniform ( 0,1 ) variates, we need only divide by modulus m, that is, we use the sequence { U i /m } . The following properties of the algorithm are worth stating explicitly: Because of the “mod m” operation (for background on modular operations, see Knuth, (1981) ), the only possible values the algorithm can produce are the integers 0,1,2,...,m−1. This follows because, by definition, x mod m is the remainder after x is divided by m. Because the current random integer U i depends only on the previous random integer U i−1 once a previous value has been repeated, the entire sequence after it must be repeated. Such a repeating sequence is called a cycle, and its period is the cycle length. Clearly, the maximum period of the congruential generator is m. For given choices of a, c, and m, a generator may contain many short cycles, (see the Example 1 below), and the cycle you enter will depend on the seed you start with. Notice that the generator with many short cycles is not a good one, since the output sequence will be one of a number of short series, each of which may not be uniformly distributed or randomly dispersed on the line or the plane. Moreover, if the simulation is long enough to cause the random numbers to repeat because of the short cycle length, the outputs will not be independent. If we are concern with a uniform ( 0,1 ) variates, the finest partition of the interval ( 0,1 ) that this generator can provide is [ 0,1/m,2/m,...,( m−1/m ) ] . This is, of course, not truly a uniform ( 0,1 ) distribution since, for any k in ( 0,m−1 ) , we have P[ k/m<U<( k+1 )/m ]=0 , not 1/m are required by theory for continuous random variables. Choices of a,c, and m, will determine not only the fineness of the partition of ( 0,1 ) and the cycle length, and therefore, the uniformity of the marginal distribution, but also the independence properties of the output sequence. Properly choosing a,c, and m is a science that incorporates both theoretical results and empirical tests. The first rule is to select the modulus m to be “as large as possible”, so that there is some hope to address point 3 above and to generate uniform variates with an approximately uniform marginal distribution. However, simply having m large is not enough; one may still find that the generator has many short cycles, or that the sequence is not approximately independent. See example 1 below. Consider U i =2 U i−1 mod⁡ 2 32 Where a seed of the form 2 k creates a loop containing only integers that are powers of 2, or U i =( U i−1 +1 )mod⁡ 2 32 which generates the nonrandom sequence of increasing integers. Therefore, the second equation gives a generator that has the maximum possible cycle length but is useless for simulating a random sequence. Fortunately, one a value of the m has been selected; theoretical results exist that give conditions for choosing values of the multiplier a and the additive constant c such that all the possible integers, 0 through m−1 , are generated before any are repeated. this does not eliminate the second counterexample above, which already has the maximal cycle length, but is a useless random number generator.

THEOREM I A linear congruential generator will have maximal cycle length m, if and only if: c is nonzero and is relatively prime to m (i.e., c and m have no common prime factors). ( amod⁡q )=1 for each prime factor q of m. ( amod⁡4 )=1 if 4 is a factor of m. PROOF Knuth (1981, p.16). As a mathematical note, c is called relatively prime to m if and only if c and m have no common divisor other than 1, which is equivalent to c and m having no common prime factor. A related result concerns the case of c chosen to be 0. This case does not conform to condition in a Theorem I, a value U i of zero must be avoided because the generator will continue to produce zero after the first occurrence of a zero. In particular, a seed of zero is not allowable. By Theorem I, a generator with c=0 , which is called a multiplicative congruential generator, cannot have maximal cycle length m. However, By Theorem II. It can have cycle length m−1 . THEOREM II If c=0 in a linear congruential generator, then U i =0 can never be included in a cycle, since the 0 will always repeat. However, the generator will cycle through all m−1 integers in the set ( amod⁡q ) if and only if: m is a prime integer and m is a primitive element modulo m . PROOF Knuth (1981, p.19). A formal definition or primitive elements modulo m, as well as theoretical results for finding them, are given in Knuth (1981). In effect, when m is a prime, a is a primitive element if the cycle is of length m−1 . The results of Theorem II are not intuitively useful, but for our purposes, it is enough to note that such primitive elements exist and have veen computed by researchers, e.g., Table24.8 in Abramowitz and Stegun, 1965. Hence, we now must select one of two possibilities: Choose a, c, and m according to Theorem I and work with a generator whose cycle length is known to be m. Choose c=0 , take a and m according to Theorem II, use a number other than zero as the seed, and work with a generator whose cycle length is known to be m−1 . A generator satisfying these conditions is known as a prime-modulus multiplicative congruential generator and, because of the simpler computation, it usually has an advantage in terms of speed over the mixed congruential generator. Another method frequency speeding up a random number generator that has c=0 is to choose the modulus m to be computationally convenient. For instance, consider m= 2 k . This is clearly not a prime number, but on a computer the modulus operation becomes a bit-shift operation in machine code. In such cases, Theorem III gives a guise to the maximal cycle length. THEOREM III If c=0 and m= 2 k with k>2 , then the maximal possible cycle length is 2 k−2 . This is achieved if and only if two conditions hold: a is a primitive element modulo m. the seed is odd. PROOF Knuth (1981, p.19). Notice that we sacrifice some of the cycle length and, as we will se in Theorem IV, we also lose some randomness in the low-order bits of the random variates. Having use any of Theorems I, II, or III to select triples (a, c, m) that lead to generators with sufficiently long cycles of known length, we can ask which triple gives the most random (i.e., approximately independent ) sequence. Although some theoretical results exist for generators as a whole, these are generally too weak to eliminate any but the worst generators. Marsaglia (1985) and Knuth(1981, Chap. 3.3.3) are good sources for material on that results. THEOREM IV If U i =a U i−1 mod⁡ 2 k , and we define Y i = U i mod⁡ 2 j ,0<j<k then Y i =a Y i−1 mod⁡ 2 j . In practical terms, this means that the sequence of j-lo-order binary bits of the U i sequence, namely Y i cycle with cycle length at most 2 j . In particular, sequence of the least significant bit (i.e., j=1) in ( U 1 , U 2 , U 3 ,... ) must behave as ( 0,0,0,0,... ),( 1,1,1,1,... ),( 0,1,0,1,... ) or ( 1,0,1,0,... ) . PROOF Knuth (1981, pp. 12-14). Such normal behavior in the low-order bits of a congruential generator with non-prime-modulus m is an undesirably property, which may be aggravated by techniques such as the recycling of uniform variates. It has been observed (Hutchinson, 1966) that prime-modulus multiplicative congruential generators with full cycle (i.e., when m is a positive primitive element) tend to have fairly randomly distributed low-order bits, although no theory exists to explain this. THEOREM V If our congruential generator produces the sequence ( U 1 , U 2 ,... ) , and we look at the following sequence of points in n dimensions: ( U 1 , U 2 , U 3 ,..., U n ),( U 2 , U 3 , U 4 ,..., U n+1 ),( U 3 , U 4 , U 5 ,..., U n+2 ),... then the points will all lie in fewer than ( n|m ) 1/n parallel hyper planes. PROOF Marsaglia (1976). Given these known limitations of congruential generator, we are still left with the question of how to choose the “best” values for a, c, and m. To do this, researchers have followed a straightforward but time-consuming procedure: Take values a, c, and m that give a sufficiently long, known cycle length and usa the generator to produce sequences of uniform variates. Subject the output sequences to batteries of statistical tests for independence and a uniform marginal distribution. Document the results. Subject the generator to theoretical tests. In particular, the spectral test of Coveyou and MacPherson (1967) is currently widely used and recognized as a very sensitive structural test for distinguishing between good and bad generators. Document the results. As new, more sensitive tests appear, subject to generator to those tests. Several such tests are discussed in Marsaglia(1985).