Web And Email Hosting, Jsp Web Hosting Blog

10 RANDOM NUMBERS 3.2.1 The special case c = 0 deserves explicit mention, since the number gener- ation process is a little faster when c = 0 than it is when c # 0. We shall see later that the restriction c = 0 cuts down the length of the period of the sequence, but it is still possible to make the period reasonably long. Lehmer s original generation method had c = 0, although he mentioned c # 0 as a possibility; the idea of taking c # 0 to obtain longer periods is due to Thomson [Comp. J. 1 (1958), 83, 861 and, independently, to Rotenberg [JACM 7 (1960), 75-77. The terms multiplicative congruential method and mixed congruential method are used by many authors to denote linear congruential sequences with c = 0 and c # 0, respectively. The letters m, a, c, and X0 will be used throughout this chapter in the sense described above. Furthermore, we will find it useful to define b=a-1, (4) in order to simplify many of our formulas. We can immediately reject the case a = 1, for this would mean that X, = (X0 + nc) modm, and the sequence would certainly not behave as a random sequence. The case a = 0 is even worse. Hence for practical purposes we may assume that a 2 2, b> 1. (5) Now we can prove a generalization of Eq. (2), X n+k = (akXn + (a -l)c/b) mod m, k 2 0, n 2 0, (6) which expresses the (n+k)th term directly in terms of the nth term. (The special case 12 = 0 in this equation is worthy of note.) It follows that the subsequence consisting of every kth term of (Xn) is another linear congruential sequence, having the multiplier ak mod m and the increment ((a -l)c/b) mod m. An important corollary of (6) is that the general sequence defined by m, a, c, and X0 can be expressed very simply in terms of the special case where c = 1 and X0 = 0. Let YO = 0, Y,+, = (au, + 1) mod m. (7) According to Eq. (6) we will have Yk = (a -1)/b (modulo m), hence the general sequence defined in (2) satisfies X, = (AY, + X0) mod m, where A = (Xob + c) mod m. 63) EXERCISES 1. [IO] Example (3) shows a situation in which X4 = X0, so the sequence begins again from the beginning. Give an example of a linear congruential sequence with m = 10 for which X0 never appears again in the sequence.

3.2.1 THE LINEAR CONGRUENTIAL METHOD 9 3.2. GENERATING UNIFORM RANDOM NUMBERS IN THIS SECTION we shall consider methods for generating a sequence of random fractions, i.e., random real numbers U,, uniformly distributed between zero and one. Since a computer can represent a real number with only finite accuracy, we shall actually be generating integers X, between zero and some number m; the fraction U, =X,/m will then lie between zero and one. Usually m is the word size of the computer, so X, may be regarded (conservatively) as the integer contents of a computer word with the radix point assumed at the extreme right, and U, may be regarded (liberally) as the contents of the same word with the radix point assumed at the extreme left. 3.2.1. The Linear Congruential Method By far the most popular random number generators in use today are special cases of the following scheme, introduced by D. H. Lehmer in 1949. [See Proc. 2nd Symp. on Large-Scale Digital Calculating Machinery (Cambridge: Harvard University Press, 1951), 141-146.1 We choose four magic numbers : m, the modulus; m > 0. a, the multiplier; O

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.)

3.1 INTRODUCTION 7 h) Assume that 10 horses are entered in a race and that you know nothing whatever about their qualifications. Assign to these horses the digits 0 to 9, in arbitrary fashion, and after the race use the winner s digit. 2. [M%!?] In a random sequence of a million decimal digits, what is the probability that there are exactly 100,000 of each possible digit? 3. [IO] What number follows 1010101010 in the middle-square method? 4. [IO] Why can t the value of X be zero when step Kll of Algorithm K is performed? What would be wrong with the algorithm if X could be zero? 5. [15] Explain why, in any case, Algorithm K should not be expected to provide infinitely many random numbers, in the sense that (even if the coincidence given in Table 1 had not occurred) one knows in advance that any sequence generated by Algorithm K will eventually be periodic. b 6. [MZJ] Suppose that we want to generate a sequence of integers X0, Xi, Xz, . . . , in the range 0 < X, < m. Let f(z) b e any function such that 0 2 z < m implies 0 5 f(x) < m. Consider a sequence formed by the rule Xn+l = f(Xn). (Examples are the middle-square method and Algorithm K.) a) Show that the sequence is ultimately periodic, in the sense that there exist numbers X and p for which the values X0, Xi, , X,, . . . , Xp+x-i are distinct, but X %+x = X, when n 2 CL. Find the maximum and minimum possible values of p and X. b) (R. W. Floyd.) Show that there exists an n > 0 such that X, = Xzn; and the smallest such value of 72 lies in the range p < n 5 p + X. Furthermore the value of X, is unique in the sense that if X, = X2, and X, = Xzr, then X, = X,. c) Use the idea of part (b) to design an algorithm that calculates p and X for any given function f and any given X0, using only O(k + X) steps and only a bounded number of memory locations. b 7. [MZ] (R. P. Brent, 1977.) Let e(n) be the least power of 2 that is less than or equal to n; thus, for example, e(15) = 8 and .!(e(n)) = e(n). a) Show that, in terms of the notation in exercise 6, there exists an n > 0 such that X, = Xe(n)-i. Find a formula that expresses the least such 72 in terms of p and x. b) Apply this result to design an algorithm that can be used in conjunction with any random number generator of the type X=+1 = f(Xn), to prevent it from cycling indefinitely. Your algorithm should calculate the period length X, and it should use only a small amount of memory space-you must not simply store all of the computed sequence values! 8. [.28] Make a complete examination of the middle-square method in the case of two- digit decimal numbers. (a) We might start the process out with any of the 100 possible values 00, 01, . . . , 99. How many of these values lead ultimately to the repeating cycle 00, 00, . 1 [Example: Starting with 43, we obtain the sequence 43, 84, 05, 02, 00, 00, 00, . . . .] (b) How many possible final cycles are there? How long is the longest cycle? (c) What starting value or values will give the largest number of distinct elements before the sequence repeats? 9. [M14] Prove that the middle-square method using 2n-digit numbers to the base b has the following disadvantage: If the sequence includes any number whose most significant n digits are zero, the succeeding numbers will get smaller and smaller until zero occurs repeatedly.

6 RANDOM NUMBERS 3.1 Table 1 A COLOSSAL COINCIDENCE: THE NUMBER 6065038420 IS TRANSFORMED INTO ITSELF BY ALGORITHM K. Step X (after) Step X (after) Kl K3 K4 K5 K6 K7 K8 K9 KlO Kll K12 K6 K7 K8 K9 KlO Kll K12 K12 K6 K7 K8 6065038420 6065038420 6910360760 8031120760 1968879240 7924019688 9631707688 8520606577 8520506578 8520506578 0323372207 9676627793 2779396766 4942162766 3831051655 3830951656 3830951656 1905867781 3319967479 6680032521 3252166800 2218966800 Y=6 Y=5 Y=4 K9 KlO Kll K12 K5 K6 K7 K8 K9 KlO Kll K12 Kll K12 K4 K5 K6 K7 K8 K9 KlO Kll K12 1107855700 1107755701 1107755701 1226919902 0048821902 9862877579 7757998628 2384626628 1273515517 1273415518 1273415518 5870802097 5870802097 3172562687 1540029446 7015475446 2984524554 2455429845 2730274845 1620163734 1620063735 1620063735 6065038420 - EXERCISES b 1. [ZV] Suppose that you wish to obtain a decimal digit at random, not using a computer. Which of the following methods would be suitable? a) Open a telephone directory to a random place (i.e., stick your finger in it some- where) and use the units digit of the first number found on the selected page. b) Same as (a), but use the units digit of the page number. c) Roll a die that is in the shape of a regular icosahedron, whose twenty faces have been labeled with the digits 0, 0, 1, 1, . . . , 9,9. Use the digit that appears on top, when the die comes to rest. (A felt table with a hard surface is recommended for rolling dice.) d) Expose a geiger counter to a source of radioactivity for one minute (shielding yourself) and use the units digit of the resulting count. Assume that the geiger counter displays the number of counts in decimal notation, and that the count is initially zero. e) Glance at your wristwatch; and if the position of the second-hand is between 6n and 6(n + 1) seconds, choose the digit n. f) Ask a friend to think of a random digit, and use the digit he names. g) Ask an enemy to think of a random digit, and use the digit he names.

3.1 INTRODUCTION 5 K4. [Middle square.] Replace X by lX2/105] mod lOlo, i.e., by the middle of the square of X. K5. [Multiply.] Replace X by (1001001001 X) mod lOlo. K6. [Pseudo-complement.] If X < 100000000, then set X +- X + 9814055677; otherwise set X +- lOlo -X. K7. [Interchange halves.] Interchange the low-order five digits of X with the high-order five digits, i.e., X +- 105(X mod 105) + lX/105], the middle 10 digits of (lOlo + 1)X. K8. [Multiply.] Same as step K5. K9. [Decrease digits.] Decrease each nonzero digit of the decimal representation of X by one. K10. [99999 modify.] If X < 105, set X c X2 + 99999; otherwise set X t x -99999. Kll. [Normalize.] (At this point X cannot be zero.) If X < log, set X + 10X and repeat this step. K12. [Modified middle square.] Replace X by 1X(X -1)/105] mod lOlo, i.e., by the middle 10 digits of X(X -1). K13. [Repeat?] If Y > 0, decrease Y by 1 and return to step K2. If Y = 0, the algorithm terminates with X as the desired random value. I (The machine-language program corresponding to the above algorithm was in- tended to be so complicated that a person reading a listing of it without ex- planatory comments wouldn t know what the program was doing.) Considering all the contortions of Algorithm K, doesn t it seem plausible that it should produce almost an infinite supply of unbelievably random num- bers? No! In fact, when this algorithm was first put onto a computer, it almost immediately converged to the lO-digit value 6065038420, which-by extraordi- nary coincidence-is transformed into itself by the algorithm (see Table 1). With another starting number, the sequence began to repeat after 7401 values, in a cyclic period of length 3178. The moral of this story is that random numbers should not be generated with a method chosen at random. Some theory should be used. In this chapter, we shall consider random number generators that are su- perior to the middle-square method and to Algorithm K; the corresponding se- quences are guaranteed to have certain desirable random properties, and no degeneracy will occur. We shall explore the reasons for this random behavior in some detail, and we shall also consider techniques for manipulating random numbers. For example, one of our investigations will be the shuffling of a simu- lated deck of cards within a computer program. Section 3.6 summarizes this chapter and lists several bibliographic sources.

Each of the ten digits 0 through 9 will occur about & of the time in a (uniform) sequence of random digits. Each pair of two successive digits should occur about & of the time, etc. Yet if we take a truly random sequence of a million digits, it will not always have exactly 100,000 zeros, 100,000 ones, etc. In fact, chances of this are quite slim; a sequence of such sequences will have this character on the average. Any specified sequence of a million digits is equally as probable as the sequence consisting of a million zeros. Thus, if we are choosing a million digits at random and if the first 999,999 of them happen to come out to be zero, the chance that the final digit is zero is still exactly &, in a truly random situation. These statements seem paradoxical to many people, but there is really no contradiction involved. There are several ways to formulate decent abstract definitions of random- ness, and we will return to this interesting subject in Section 3.5; but for the moment, let us content ourselves with an intuitive understanding of the concept. At first, people who needed random numbers in their scientific work would draw balls out of a well-stirred urn or would roll dice or deal out cards. A table of over 40,000 random digits, taken at random from census reports, was published in 1927 by L. H. C. Tippett. Since then, a number of devices have been built to generate random numbers mechanically; the first such machine was used in 1939 by M. G. Kendall and B. Babington-Smith to produce a table of 100,000 random digits, and in 1955 the RAND Corporation published a widely used table of a million random digits obtained with the help of another special