Web design course - 74 RANDOM NUMBERS 3.3.2 7. [08] Apply the
74 RANDOM NUMBERS 3.3.2 7. [08] Apply the coupon collector s test procedure (Algorithm C) with d = 3 and 72 = 7, to the following sequence: 1101221022120202001212201010201121. What lengths do the seven subsequences have? b 8. [MZ?] How many U s need to be examined, on the average, in the coupon collec- tor s test (Algorithm C) before 72 complete sets have been found, assuming that the sequence is random? What is the standard deviation? [Hint: See Eq. 1.2.9-28.1 9. [A4,%?1] Generalize the coupon collector s test so that the search stops as soon as w distinct values have been found, where w is a fixed positive integer less than or equal to d. What probabilities should be used in place of (6)? 10. [A&% ] Solve exercise 8 for the more general coupon collector s test described in exercise 9. 11. [OO] The runs up in a particular permutation are displayed in (9); what are the runs down in that permutation? 12. [ZOO] Let V0, Ul, . . . , V,-l be n distinct numbers. Write an algorithm that determines the lengths of all ascending runs in the sequence. When your algorithm terminates, COUNT[r] should be the number of runs of length r, for 1 5 r 5 5, and COUNF[S] should be the number of rdns of length 6 or more. 13. [MZ?] Show that (16) is the number of permutations of p+q+l distinct elements having the pattern (15) . b 14. [A&5] If we throw away the element that immediately follows a run, so that when Xj is greater than X3+1 we start the next run with X3+2, the run lengths are independent, and a simple chi-square test may be used (instead of the horribly compli- cated method derived in the text). What are the appropriate run-length probabilities for this simple run test? 15. [A4101 In the maximum-of-t test, why are Vi, V, , . . . , VAwl supposed to be uniformly distributed between zero and one? b 16. [IS] (a) Mr. J. H. Quick (a student) wanted to perform the maximum-of-t test for various values of t. Letting Zj, = max(Vj, U3+1,. . . , Uj+t–l), he found a clever way to go from the sequence ZO(~-~), Z1(t-l), , to the sequence Zot, Zlt, . . , using very little time and space. What was his bright idea? (b) He decided to modify the maximum-of-t method so that the jth observation would be max(u, , . . . , Uj+,-,); in other words, he took V, = Zj, instead of V, = Z ctjjt as the text says. He reasoned that all of the Z s should have the same distribution, so the test is even stronger if each ZJt, 0 5 j < n, is used instead of just every tth one. But when he tried a chi-square equidistribution test on the values of V$, he got extremely high values of the statistic V, which got even higher as t increased. Why did this happen? 17. (A4Z5] (a) Given any numbers UO, . . , Un-l, Vi,. . . , Vn-l, let 1 ai=- c uk, v=-; c vk. n O