Web hosting domains - 3.4.1 NUMERICAL DISTRIBUTIONS 135 b 16. [HA&Z?] (J.
3.4.1 NUMERICAL DISTRIBUTIONS 135 b 16. [HA&Z?] (J. H. Ahrens.) Develop an algorithm for gamma deviates of order a when 0 < a 5 1, using the rejection method with cg(t) = Y- /I(a) for 0 < t < 1, e- /r(a) for t 2 1. b 17. [M.%?4] What is the distribution function F(s) for the geometric distribution with probability p? What is the generating function G(Z)? What are the mean and standard deviation of this distribution? 18. [M.Z4] Suggest a method to compute a random integer N for which N takes the value n with probability np (1 -p) - , n 2 0. (The case of particular interest is when p is rather small.) 19. [ZZ] The negative binomial distribution (t,p) has integer values N = n with probability ( -L+,f )p (l -p) . (Unlike the ordinary binomial distribution, t need not be an integer, since this quantity is nonnegative for all n whenever t > 0.) Generalizing exercise 18, explain how to generate integers N with this distribution when t is a small positive integer. What method would you suggest if t = p = f? 20. [A&Q] Let A be the area of the shaded region in Fig. 13, and let R be the area of the enclosing rectangle. Let 1 be the area of the interior region recognized by step R2, and let E be the area between the exterior region rejected in step R3 and the outer rectangle. Determine the number of times each step of Algorithm R is performed, for each of its four variants as in (25), in terms of A, R, I, and E. 21. [HA&?9] Derive formulas for the quantities A, R, I, and E defined in exercise 20. (For 1 and especially E you may wish to use an interactive computer algebra system.) Show that c = e1j4 is the best possible constant in step R2 for tests of the form X2 5 4(1 + In c) -4cU. 22. [HM40] Can the exact Poisson distribution for large p be obtained by generating an appropriate normal deviate, converting it to an integer in some convenient way, and applying a (possibly complicated) correction a small percent of the time? 23. [HA4.23] (J. von Neumann.) Are the following two ways to generate a random quantity X equivalent (i.e., does the quantity X have the same distribution) ? Method 1: Set X + sin((r/2)U), where U is uniform. Method 8: Generate two uniform deviates, U, V, and if U2 + V2 2 1, repeat until U2 + V2 < 1. Then set X + IU2 -V l/(U + V ). 24. [HM40] (S. Ulam, J. von Neumann.) Let VO be a randomly selected real number between 0 and 1, and define the sequence (Vn) by the rule V,+l = 4V,(l -Vn). If this computation is done with perfect accuracy, the result should be a sequence with the distribution sin2 TU, where U is uniform, i.e., with distribution function F(x) = s; d+/%$-=-kj. F or i f we write V, = sin2 rU,, we find that U,+l = (2ii,) mod 1; and by the fact that almost all real numbers have a random binary expansion (see Section 3.5), this sequence U, is equidistributed. But if the computation of V, is done with only finite accuracy, the above argument breaks down because we soon are dealing with noise from the roundoff error. [Reference: von Neumann s Collected Works 5, 768-770.1 Analyze the sequence (V,) defined above when only finite accuracy is present, both empirically (for various different choices of VO) and theoretically. Does the sequence have a distribution resembling the expected distribution?