120 RANDOM NUMBERS 3.4.1 b . . a
120 RANDOM NUMBERS 3.4.1 b . . a .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 ~ S s+h Fig. 10. Density functions for which Algorithm L may be used to generate random numbers. In order to generate such rectangular portions of the distribution, we simply compute x=QJ+s, (16) where U is uniform and S takes the value (J -1)/5 with probability pj. Since pl + . . . + p15 = .9183, we can use simple uniform deviates like this about 92 percent of the time. In the remaining 8 percent, we will usually have to generate one of the wedge-shaped distributions Frs, . . . , Fso. Typical examples of what we need to do are shown in Fig. 10. When z < 1, the curved part is concave downward, and when 2 > 1 it is concave upward, but in each case the curved part is reasonably close to a straight line, and it can be enclosed in two parallel lines as shown. To handle these wedge-shaped distributions, we will rely on yet another general technique, von Neumann s rejection method for obtaining a complicated density from another one that encloses it. The polar method described above is a simple example of such an approach: Steps Pl-P3 obtain a random point inside the unit circle by first generating a random point in a larger square, rejecting it and starting over again if the point was outside the circle. The general rejection method is even more powerful than this. To generate a random variable X with density f, let g be another probability density function such that f(t) 2 cdt) (17) for all t, where c is a constant. Now generate X according to density g, and also generate an independent uniform deviate U. If U 2 f(X)/cg(X), reject X and start again with another X and U. When the condition U < f(X)/cg(X) finally occurs, the resulting X will have density f as desired. [Proof: X 2 2 will occur with probability p(z) = Jz,(g(t)dt . f(t)/cg(t)) + qp(z), where the quantity 4 = r&w * (1 - fwm)) = 1 - l/ c is the probability of rejection; hence p(z) = sz, f(t) dt.] The rejection technique is most efficient when c is small, since there will be c iterations on the average before a value is accepted. (See exercise 6.) In some