3.3.1 ANSWERS TO EXERCISES 531 27. Let J, (Web hosting uk)
3.3.1 ANSWERS TO EXERCISES 531 27. Let J, = LkX,,/m]. Lemma: After the (k* + 7k -2)/2 consecutive values 0 k+2 10 ktl 2 Ok . (k -1) O3 occur in the (Jn) sequence, Algorithm B will have V[i] < m/k for 0 2 j < k, and also Y < mfk. Proof. Let S, be the set of positions i such that V[i] < mfk just before X, is generated, and let & be the index such that V[$] t X,. If j, @ S, and J, = 0, then S,+r = S, U {j,}; if j, E S, and J, = 0, then S,+i = S, and j,+r = 0. After k + 2 successive O s, we must therefore have 0 E S, and $+I = 0. Then after 1 Ok+ we must have (0, l} c S, and j,+i = 0; after 2 Ok we must have (0, 1,2} c S, and j,+r = 0; and so on. Corollary: For X 2 2(k2+7k-2)k(k2-t7k-2)/2, either Algorithm B yields a period of length X or the sequence (X,) is poorly distributed. Proof. The probability that any given length-l pattern of J s does not occur in a random sequence of length X is less than (1 -k- )x/L < exp(-k-lX/J). For 1 = (k2 + i k -2)/2 this is at most e - ; hence the stated pattern should appear. After it does, the subsequent behavior of Algorithm B will be the same each time it reaches this part of the period. SECTION 3.3.1 1. There are k = 11 categories, so the line v = 10 should be used. 2.2 A lLi9&Zj_Qix2 49, 49, ib, &a, 491 49, 4gr 4gr 491 491 49 3. V = 7$$$, only very slightly higher than that obtained from the good dice! There are two reasons why we do not detect the weighting: (a) The new probabilities (cf. exercise 2) are not really very far from the old ones in Eq. (1). The sum of the two dice tends to smooth out the probabilities; if we considered instead each of the 36 possible pairs of values, and counted these, we would probably detect the difference quite rapidly (assuming that the two dice are distinguishable). (b) A far more important reason is that n is too small for a significant difference to be detected. If the same experiment is done for large enough n, the faulty dice will be discovered (see exercise 12). 4. p, = & for 2 5 s 5 12 and s # 7; pr = &. The value of V is 16$, which falls between the 75% and 95% entries in Table 1; so it is reasonable, in spite of the fact that not too many sevens actually turned up. 5. K&, = 1.15; KG = 0.215; these do not differ significantly from random behavior (being at about the 94% and 86% levels), but they are mighty close. (The data values in this exercise come from Appendix A, Table 1.) 6. The probability that X, 2 z is F(z), so we have the binomial distribution discussed in Section 1.2.10. Fn(s) = s/ n with probability (y) F(z) (l -F(s)) - ; the mean is F(s); the standard deviation is d/F(z)(l -F(z))/n. [Cf. Eq. 1.2.10-19. This suggests that a slightly better statistic would be to define see exercise 22. We can calculate the mean and standard deviation of Fn(z) -Fn(y), for z < y, and obtain the covariance of Fn(z),Fn(y). Using these facts, it can be
Go visit our java server pages services for a reliable, lowcost webhost to satisfy all your needs.