3.1 ANSWERS (Mac os x web server) TO EXERCISES 517 (c) The markings
3.1 ANSWERS TO EXERCISES 517 (c) The markings on the faces will slightly bias the die, but for practical purposes this method is quite satisfactory (and it has been used by the author in the preparation of several examples in this set of books). See Math. Comp. 15 (1961), 94-95, for further discussion of these dice. (d) (This is a hard question thrown in purposely as a surprise.) The number is not quite uniformly random. If the average number of emissions per minute is m, the probability that the counter registers k is e- mk/k! (the Poisson distribution); so the digit 0 is selected with probability e- c,,, mlok /(lOk)!, etc. The units digit will be even with probability e- cash m = 4 + ieZ2n, and this is never equal to i (although the error is negligibly small when m is large). (e) Okay, provided that the time since the previous digit selected in this way is random. However, there is possible bias in borderline cases. (f,g) No, people usually think of certain digits (like 7) with higher probability. (h) Okay; your assignment of numbers to the horses had probability & of assigning a given digit to the winning horse. 2. The number of such sequences is the multinomial coefficient 1000OOO!/(lOOOOO!) ; the probability is this number divided by 101oooooo, the total number of sequences of a million digits. By Stirling s approximation we find that the probability is close to 1/(167r410z2fi) x 2.55 X 10-26, about one chance in 4 X 10z5. 3. 3040504030. 4. Step Kll can be entered only from step KlO or step K2, and in either case we find it impossible for X to be zero by a simple argument. If X could be zero at that point, the algorithm would not terminate. 5. Since only lOlo ten-digit numbers are possible, some value of X must be repeated during the first 10 + 1 steps; and as soon as a value is repeated, the sequence continues to repeat its past behavior. 6. (a) Arguing as in the previous exercise, the sequence must eventually repeat a value; let this repetition occur for the first time at step p + X, where X,+X = X,. (This condition defines p and X.) We have 0 2 p < m, 0 < X 5 m, p + X 5 m. The values p = 0, X = m are attained iff f is a cyclic permutation; and p = m -1, X = 1 occurs, e.g., if X0 = 0, f(z) = z $ 1 for 2 < m -1, and f(m -1) = m -1. (b) We have, for r 2 n, X, = X, iff r -n is a multiple of X and n 2 p. Hence X2, = X, iff n is a multiple of X and n 2 p. The desired results now follow immediately. [Note: This is essentially a proof of the familiar mathematical result that the powers of an element in a finite semigroup include a unique idempotent element: take Xc = a, f(x) = ax.1 (c) Once n has been found, generate X, and X,+, for i > 0 until first finding x = Xntz; then p = i. If none of the values of Xn+i for 0 27 5 p is equal to X,, it follows that X = n, otherwise X is the smallest such i. 7. (a) The least n > 0 such that n -(e(n) -1) is a multiple of X and e(n) -1 2 p is n = 2r gmax(~f1,X)1 -1 + X. [This may be compared with the least n > 0 such that Xz,, = X,, namely X6,0 + p + X - 1 - ((p + X - 1) mod X).] (b) Start with X = Y = Xc, k = m = 1. (At key places in this algorithm we will have X = Xzm-k-1, Y = X,-l, and m = e(2m -k).) To generate the next random number, do the following steps: Set X + f(X) and k + k -1. If X = Y, stop (the period length X is equal to m-k). Otherwise if k = 0, set Y + X, m + 2m, k + m. Output X.
You need excellent and relaible webhost company to host your web applications? Then pay a visit to Inexpensive Web Hosting services.