3.3.2 EMPIRICAL TESTS (Space web hosting) 63 Algorithm C (Data for
3.3.2 EMPIRICAL TESTS 63 Algorithm C (Data for coupon collector s test). Given a sequence of integers Yo, K, , with 0 5 Y, < d, this algorithm counts the lengths of n consecutive coupon collector segments. At the conclusion of the algorithm, COUNT[r] is the number of segments with length r, for d 5 T < t, and COUNT[t] is the number of segments with length 2 t. Cl. [Initialize.] Set j c -1, s c 0, and set COUNT[r] +- 0 for d 5 r 5 t. C2. [Set q,r zero.] Set o c T c 0, and set OCCURS[k] c 0 for 0 5 k < d. C3. [Next observation.] Increase T and j by 1. If OCCURS[Yj] # 0, repeat this step. C4. [Complete set?] Set OCCURS[Y~] c 1 and o t q + 1. (The subsequence observed so far contains q distinct values; if q = d, we therefore have a complete set.) If q < d, return to step C3. C5. [Record the length.] If r > t, increase COUNT[t] by one, otherwise increase COUNT[r] by one. C6. [n found?] Increase s by one. If s < n, return to step C2. 1 For an example of this algorithm, see exercise 7. We may think of a boy collecting d types of coupons, which are randomly distributed in his breakfast cereal boxes; he must keep eating more cereal until he has one coupon of each type. A chi-square test is to be applied to COUNT[d], COUNT[d + 11, . . . , COUNT[t], with k = t-d+ 1, after Algorithm C has counted n lengths. The corresponding probabilities are d