Starting a web site - 88 RANDOM NUMBERS 3.3.3 EXERCISES-Second Set In many
88 RANDOM NUMBERS 3.3.3 EXERCISES-Second Set In many cases, exact computations with integers are quite difficult to carry out, but we can attempt to study the probabilities that arise when we take the average over all real values of 1: instead of restricting the calculation to integer values. Although these results are only approximate, they shed some light on the subject. It is convenient to deal with numbers U,, between zero and one; for linear con- gruential sequences, U, = Xn/m, and we have U,+l = {au,, + 0}, where 0 = c/m and {z} denotes x mod 1. For example, the formula for serial correlation now becomes 1 C= x(ax+8)dx-(~1xdx)1)/(~1~2dx-(~xdx)1) b 21. [HA&B] (R. R. Coveyou.) What is the value of C in the formula just given? b 22. [M22] Let a be an integer, and let 0 5 6 < 1. If x is a real number between 0 and 1, and if s(x) = {ax + 0}, what is the probability that s(x) < x? (This is the real number analog of Theorem P.) 23. [68] The previous exercise gives the probability that Un+l < U,. What is the probability that Un+z < Un+l < Un, assuming that Un is a random real number between zero and one? 24. [A4691 Under the assumptions of the preceding problem, except with 0 = 0, show that U, > Un+l > .. > Un++i occurs with probability What is the average length of a descending run starting at U,, assuming that U, is selected at random between zero and one? b 25. [A4951 Let QI, p, Q , /3 be real numbers with 0 5 o < p < 1, 0 2 cr < /I < 1. Under the assumptions of exercise 22, what is the probability that o 5 z < p and Q 2 s(x) < /I ? (This is the real number analog of exercise 19.) 26. [MZY] Consider a Fibonacci generator, where Un+l = {U,+U,-I}. Assuming that U1 and Uz are independently chosen at random between 0 and 1, find the prob- ability that VI < Uz < Us, Ul < U3 < UZ, UZ < Ui < UX, etc. [Hint: Divide the unit square, i.e., the points of the plane {(sly) ] 0 2 x,y < l}, into six parts, depending on the relative order of x, y, and {x $ y}, and determine the area of each part.] 27. [A&Z?] In the Fibonacci generator of the preceding exercise, let UO and UI be chosen independently in the unit square except that UO > VI. Determine the probabil- ity that Vi is the beginning of an upward run of length k, so that UO > VI < . . . < Uk > Uk+l. Compare this with the corresponding probabilities for a random sequence. 28. [M%] According to Eq. 3.2.1.3-5, a linear congruential generator with potency 2 satisfies the condition X,-l -2X,, + X n+i G (a -1)c (modulo m). Consider a generator that abstracts this situation: let U,+l = {a + 2U, -U,-I}. As in exercise 26, divide the unit square into parts that show the relative order of Vi, UZ, and Us for each pair (VI, Us). Are there any values of QI for which all six possible orders are achieved with probability &, assuming that UI and U2 are chosen at random in the unit square?