114 RANDOMNUMBERS 3.4 3.4. OTHER TYPES OF RANDOM
114 RANDOMNUMBERS 3.4 3.4. OTHER TYPES OF RANDOM QUANTITIES WE HAVE NOW SEEN how to make a computer generate a sequence of numbers uo, Ul, u2, . . . that behaves as if each number were independently selected at random between zero and one with the uniform distribution. Applications of random numbers often call for other kinds of distributions, however; for example, if we want to make a random choice from among Ic alternatives, we want a random integer between 1 and k. If some simulation process calls for a random waiting time between occurrences of independent events, a random number with the exponential distribution is desired. Sometimes we don t even want random numbers-we want a random permutation (i.e., a random arrangement of n objects) or a random combination (i.e., a random choice of k objects from a collection of n). In principle, any of these other random quantities may be obtained from the uniform deviates UO, VI, U2, . . . . People have devised a number of important random tricks that may be used to perform these manipulations efficiently on a computer, and a study of these techniques also gives some insight into the proper use of random numbers in any Monte Carlo application. It is conceivable that someday somebody will invent a random number generator that produces one of these other random quantities directly, instead of getting it indirectly via the uniform distribution. But except for the random bit generator described in Section 3.2.2, no direct methods have so far proved to be practical. The discussion in the following section assumes the existence of a random sequence of uniformly distributed real numbers between zero and one. A new uniform deviate U is generated whenever we need it. These numbers are usually represented in a computer word with the decimal point assumed at the left. 3.4.1. Numerical Distributions This section summarizes the best techniques known for producing numbers from various important distributions. Many of the methods were originally suggested by John von Neumann in the early 195Os, and they have gradually been improved upon by other people, notably George Marsaglia, J. H. Ahrens, and U. Dieter. A. Random choices from a finite set. The simplest and most common type of distribution required in practice is a random integer. An integer between 0 and 7 can be extracted from three bits of U on a binary computer; in such a case, these bits should be extracted from the most significant (left-hand) part of the computer word, since the least significant bits produced by many random number generators are not sufficiently random. (See the discussion in Section 3.2.1.1.) In general, to get a random integer X between 0 and k -1, we can multiply by k, and let X = LkUj. On MIX, we would write LDA U MULK (1)