3.4.1 NUMERICAL DISTRIBUTIONS 133 by making the substitution (Php web hosting)
3.4.1 NUMERICAL DISTRIBUTIONS 133 by making the substitution tl = sul, tl + t2 = ~~12, . . . , tl + +. . + t,-1 = XL,-1. The latter ratio is the corresponding probability that uniform deviates Vl, ** , U,-I satisfy VI 2 WI, . . . , V,-l 5 ~~-1, given that they also satisfy Ul 2 … 5 Urn-l. A more efficient but somewhat more complicated technique for binomial and Poisson deviates is sketched in exercise 22. G. For further reading. The forthcoming book Non-Uniform Random Numbers by J. H. Ahrens and U. Dieter discusses many more algorithms for the genera- tion of random variables with nonuniform distributions, together with a careful consideration of the efficiency of each technique on typical computers. From a theoretical point of view it is interesting to consider optimal methods for generating random variables with a given distribution, in the sense that the method produces the desired result from the minimum possible number of random bits. For the beginnings of a theory dealing with such questions, see D. E. Knuth and A. C. Yao, Algorithms and Complexity, ed. by J. F. Traub (New York: Academic Press, 1976), 357-428. Exercise 16 is recommended as a review of many of the techniques in this section. EXERCISES 1. [IO] If QI and ,B are real numbers with CY < ,B, how would you generate a random real number uniformly distributed between CY and p? 2. [MI61 Assuming that mU is a random integer between 0 and m -1, what is the exact probability that LkuJ = r, if 0 < r < k? Compare this with the desired probability l/k. b 3. [&I Discuss treating U as an integer and dividing by k to get a random integer between 0 and k -1, instead of multiplying as suggested in the text. Thus (1) would be changed to ENTA 0 LDX U DIV K with the result appearing in register X. Is this a good method? 4. [M20] Prove the two relations in (8). b 5. [21] Suggest an efficient method to compute a random variable with the distribu- tion px + qx2 + rx3, where p 2 0, q 2 0, r 2 0, and p + q + r = 1. 6. [HA4211 A quantity X is computed by the following method: Step 1. Generate two independent uniform deviates U, V. Step 2. If U2 + V2 2 1, return to step 1; otherwise set X +- U. What is the distribution function of X? How many times will step 1 be performed? (Give the mean and standard deviation.)