8 RANDOM NUMBERS 3.1 10. [M16] Under the (Graphic web design)
8 RANDOM NUMBERS 3.1 10. [M16] Under the assumptions of the preceding exercise, what can you say about the sequence of numbers following X if the least significant n digits of X are zero? What if the least significant n + 1 digits are zero? b 11. [ML?6] Consider sequences of random number generators having the form de- scribed in exercise 6. If we choose f(s) and X0 at random, i.e., if we assume that each of the mm possible functions f(z) is equally probable and that each of the m possible values of X0 is equally probable, what is the probability that the sequence will eventually degenerate into a cycle of length X = l? (Note: The assumptions of this problem give a natural way to think of a random random number generator of this type. A method such as Algorithm K may be expected to behave somewhat like the generator considered here; the answer to this problem gives a measure of how colossal the coincidence of Table 1 really is.) b 12. [i!431] Under the assumptions of the preceding exercise, what is the average length of the final cycle? What is the average length of the sequence before it begins to cycle? (In the notation of exercise 6, we wish to examine the average values of X and of k + X.) 13. [M@] If f(x) is chosen at random in the sense of exercise 11, what is the average length of the longest cycle obtainable by varying the starting value XO? (Note: We have already considered the analogous problem in the case that f(z) is a random permutation; see exercise 1.3.3-23.) 14. [M38] If f(x) is chosen at random in the sense of exercise 11, what is the average number of distinct final cycles obtainable by varying the starting value? [Cf. exercise 8(b).l 15. [A&Y] If f(z) is chosen at random in the sense of exercise 11, what is the prob- ability that none of the final cycles has length 1, regardless of the choice of X0? 16. [IS] A sequence generated as in exercise 6 must begin to repeat after at most m values have been generated. Suppose we generalize the method so that X,+1 depends on X,-l as well as on X,; formally, let f(z, y) be a function such that 0 5 x, y < m implies 0 2 f(x,y) < m. The sequence is constructed by selecting X0 and X1 arbitrarily, and then letting X n+1 = f(Xn, -L-l), for n > 0. What is the maximum period conceivably attainable in this case? 17. [la] Generalize the situation in the previous exercise so that, Xn+l depends on the preceding k values of the sequence. 18. [it&?01 Invent a method analogous to that of exercise 7 for finding cycles in the general form of random number generator discussed in exercise 17. 19. [A448] Solve the problems of exercises 11 through 15 for the more general case that X n+l depends on the preceding k values of the sequence; each of the mm functions f(n,…, zk) is to be considered equally probable. (Note: The number of functions that yield the maximum period is analyzed in exercise 2.3.4.2-23.)