3.3.2 ANSWERS TO EXERCISES 535 3. The probability
3.3.2 ANSWERS TO EXERCISES 535 3. The probability that j values are examined, i.e., the probability that U,-, is the nth element of the sequence lying in the range a < Uj-1 < ,0, is easily seen to be nj-l _ 1 PV - Pd- 7 ( > by enumeration of the possible places in which the other n -1 occurrences can appear and by evaluating the probability of such a pattern. The generating function is G(z) = (PZN -(1 -Pk)) , which makes sense since the given distribution is the n-fold convolution of the same thing for n = 1. Hence the mean and variance are proportional to n; the number of U s to be examined is now easily found to have the characteristics (min n, ave n/p, max co, dev d-/p). A more detailed discussion of this probability distribution when n = 1 may be found in the answer to exercise 3.4.1-17; see also the considerably more general results of exercise 2.3.4.2-26. 4. The probability of a gap of length 2 r is the probability that r consecutive U s lie outside the given range, i.e., (1 -p) . The probability of a gap of length exactly r is the above value for length 2 r minus the value for length 2 (r + 1). 5. As N goes to infinity, so does n (with probability l), hence this test is just the same as the gap test described in the text except for the length of the very last gap, And the text s gap test certainly is asymptotic to the chi-square distribution stated, since the length of each gap is independent of the length of the others. [Notes: A quite complicated proof of this result by E. Bofinger and V. J. Bofinger appears in Annals Math. Stat. 32 (1961), 524-534. Their paper is noteworthy because it discusses several interesting variations of the gap test; they show, for example, that the quantity (X -(NP)P~) c 0<7it (NP)P~ does not approach a chi-square distribution, although others had suggested this statistic as a stronger test because Np is the expected value of n.] 7. 5, 3, 5, 6, 5, 5, 4. 8. See exercise 10, with w = d. 9. (Change d to w in steps Cl and C4.) We have d(d -1). . . (d -w + 1) p, = for w < r < t; d 10. As in exercise 3, we really need consider only the case n = 1. The generating function for the probability that a coupon set has length r is