3.3.2 EMPIRICAL TESTS 65 G. Run test. A (My web server)
3.3.2 EMPIRICAL TESTS 65 G. Run test. A sequence may also be tested for runs up and runs down. This means we examine the length of monotone subsequences of the original sequence, i.e., segments that are increasing or decreasing. As an example of the precise definition of a run, consider the sequence of ten numbers 1298536704 ; putting a vertical line at the left and right and between X, and X3+1 whenever X, > X3+1, we obtain /l 2 9181513 6 710 41, (9) which displays the runs up : there is a run of length 3, followed by two runs of length 1, followed by another run of length 3, followed by a run of length 2. The algorithm of exercise 12 shows how to tabulate the length of runs up. Unlike the gap test and the coupon collector s test (which are in many other respects similar to this test), we should not apply a &i-square test to the above data, since adjacent runs are not independent. A long run will tend to be followed by a short run, and conversely. This lack of independence is enough to invalidate a straightforward chi-square test. Instead, the following statistic may be computed, when the run lengths have been determined as in exercise 12: V = k c (COUNT[~] - &,)(couNT[~] -nbY)az3, (10) 11w16 where n is the length of the sequence, and the coefficients at3 and bi are equal to fall a12 a13 a14 a15 a16 (4529.4 9044.9 13568 18091 22615 27892 a21 a22 a23 a24 a25 a26 9044.9 18097 27139 36187 45234 55789 a31 a32 a33 a34 a35 a36 13568 27139 40721 54281 67852 83685 a41 a42 a43 a44 a45 a46 18091 36187 54281 72414 90470 111580 a51 a52 a53 a54 a55 a56 22615 45234 67852 90470 113262 139476 ia61 a62 a63 a64 a65 a66 I= L 27892 55789 83685 111580 139476 172860 (11) (bl bz b3 h b5 b6) = (8 & & +& & &). (The values of az3 shown here are approximate only; exact values may be obtained by using formulas derived below.) The statistic V in (10) should have the chi- square distribution with six (not five) degrees of freedom, when n is large. The value of n should be, say, 4000 or more. The same test can be applied to runs down. A vastly simpler and more practical run test appears in exercise 14, so a reader who is interested only in testing random number generators should skip the next few pages and go on to the maximum-of-t test after looking at exercise 14. On the other hand it is instructive from a mathematical standpoint to see how a complicated run test with interdependent runs can be treated, so we shall now digress for a moment.