Web And Email Hosting, Jsp Web Hosting Blog

54 RANDOM NUMBERS 3.3.1 normal distribution (cf. exercise 1.2.10-16); therefore points in a differential volume dz 2.. . dzk of S occur with probability approximately proportional to exp (-(24 + . . . + $)/2). (It is at this point in the derivation that the chi- square method becomes only an approximation for large n.) The probability that V 2 v is now S~zl,…,zrc)inSandzl+…+z,,Iv exP(-(z? + …+Z:)/2)dz~…dZk exp (-(zy + . + . + zg)/2) dz2 . . . dzk . (20) J(zl,…,zk)in S Since the hyperplane (19) passes through the origin of k-dimensional space, the numerator in (20) is an integration over the interior of a (k -1)-dimensional hypersphere centered at the origin. An appropriate transformation to generalized polar coordinates with radius x and angles ~1, . . . , wk-2 transforms (20) into Sp

3.3.1 GENERAL TEST PROCEDURES 53 examples of the previous misuse of statistics; and he also proved that certain runs at roulette (which he had experienced during two weeks at Monte Carlo in 1892) were so far from the expected frequencies that odds against the assumption of an honest wheel were some 1O2g to one! A general discussion of the chi-square test and an extensive bibliography appear in the survey article by William G. Cochran, Annals Math. Stat. 23 (1952), 315-345. Let us now consider a brief derivation of the theory behind the chi-square test. The exact probability that Y1 = yl,. . . , Yk = yk is easily seen to be n! PY .pp. Yl!…Yk! l . . If we assume that Y, has the value ys with the Poisson probability e -nps(np,)y* Ys! , and that the Y s are independent, then (Y1,. . . , Yk) will equal (yl,. . . , yk) with probability –nps(np,)Ys II y,! l

52 RANDOM NUMBERS Range of Kt Range of K; Fig. 5. The KS tests applied to the same data as Fig. 2. in Fig. 2 (showing which KS values are beyond the 99-percent level, etc.); the results in this case are shown in Fig. 5. Note that Generator D (Lehmer s original method) shows up very badly in Fig. 5, while chi-square tests on the very same data revealed no difficulty in Fig. 2; contrariwise, Generator E (the Fibonacci method) does not look so bad in Fig. 5. The good generators, A and B, passed all tests satisfactorily. The reasons for the discrepancies between Fig. 2 and Fig. 5 are primarily that (a) the number of observations, 200, is really not large enough for a powerful test, and (b) the reject, suspect, almost suspect ranking criterion is itself suspect. (Incidentally, it is not fair to blame Lehmer for using a bad random number generator in the 194Os, since his actual use of Generator D was quite valid. The ENIAC computer was a highly parallel machine, programmed by means of a plugboard; Lehmer set it up so that one of its accumulators was repeatedly multiplying its own contents by 23, mod (lO*+l), yielding a new value every few microseconds. Since this multiplier 23 is too small, we know that each value obtained by such a process was too strongly related to the preceding value to be considered sufficiently random; but the durations of time between actual uses of the values in the special accumulator by the accompanying program were comparatively long and subject to some fluct,uation. So the effective multiplier was 23 for large, varying values of Ic.) C. History, bibliography, and theory. The chi-square test was introduced by Karl Pearson in 1900 [Philosophical Magazine, Series 5, 50, 157-1751. Pearson s important paper is regarded as one of the foundations of modern statistics, since before that time people would simply plot experimental results graphically and assert that they were correct. In his paper, Pearson gave several interesting

3.3.1 GENERAL TEST PROCEDURES 51 may mean that the sequence has too much local nonrandomness; but a better general method would be to plot the empirical distribution of these 10 values and to compare it to the correct distribution, which may be obtained from Table 1. This would give a clearer picture of the results of the x2 tests, and in fact the statistics K& and K, could be determined as an indication of the success or failure. With only 10 values or even as many as 100 this could all be done easily by hand, using graphical methods; with a larger number of V s, a computer subroutine for calculating the chi-square distribution would be necessary. Notice that all 20 of the observations in Fig. 4(c) fall between the 5 and 95 percent levels, so we would not have regarded any of them as suspicious, individually; yet collectively the empirical distribution shows that these observations are not at all right. An important difference between the KS test and the chi-square test is that the KS test applies to distributions F(z) having no jumps, while the chi-square test applies to distributions having nothing but jumps (since all observations are divided into k categories). The two tests are thus intended for different sorts of applications. Yet it is possible to apply the x2 test even when F(X) is continuous, if we divide the domain of F(s) into k parts and ignore all variations within each part. For example, if we want to test whether or not VI, U2, . . . , U, can be considered to come from the uniform distribution between zero and one, we want to test if they have the distribution F(s) = z for 0 5 5 5 1. This is a natural application for the KS test. But we might also divide up the interval from 0 to 1 into k = 100 equal parts, count how many U s fall into each part, and apply the chi-square test with 99 degrees of freedom. There are not many theoretical results available at the present time to compare the effectiveness of the KS test versus the chi-square test. The author has found some examples in which the KS test pointed out nonrandomness more clearly than the x2 test, and others in which the x2 test gave a more significant result. If, for example, the 100 categories mentioned above are numbered 0, 1, . . . , 99, and if the deviations from the expected values are positive in compartments 0 to 49 but negative in compartments 50 to 99, then the empirical distribution function will be much further from F(z) than the x2 value would indicate; but if the positive deviations occur in compartments 0, 2, . . . , 98 and the negative ones occur in 1, 3, . . . , 99, the empirical distribution function will tend to hug F(z) much more closely. The kinds of deviations measured are therefore somewhat different. A x2 test was applied to the 200 observations that led to Fig. 4, with k = 10, and the respective values of V were 9.4, 17.7, and 39.3; so in this particular case the values are quite comparable to the KS values given in (16). Since the x2 test is intrinsically less accurate, and since it requires comparatively large values of n, the KS test has several advantages when a continuous distribution is to be tested. A further example will also be of interest. The data that led to Fig. 2 were chi-square statistics based on n = 200 observations of the maximum-of-t criterion for 1 5 t 2 5, with the range divided into 10 equally probable parts. KS statistics K&,, and KyoO can be computed from exactly the same sets of 200 observations, and the results can be tabulated in just the same way as we did

50 RANDOM NUMBERS 3.3.1 is the actual distribution the statistic KT, should have. Figure 4(a) shows the . . . . . empirical dlstrlbutlon of K& obtained from the sequence Y n+l = (3141592653Y, + 2718281829) mod 235, u,, = Y,/235, and it is satisfactorily random. Part (b) of the figure came from the Fibonacci method; this sequence has globally nonrandom behavior, i.e., it can be shown that the observations X, in the maximum of 5 test do not have the correct distribution F(z) = z 5. Part (c) came from the notorious and impotent linear congruential sequence Y,+l = ((2l* + l)Y, + 1) mod 235, U, = Y,/235. The KS test applied to the data in Fig. 4 gives the results shown in (12). Referring to Table 2 for n = 20, we see that the values of K& and KG for Fig. 4(b) are almost suspect (they lie at about the 5 percent and 88 percent levels) but not quite bad enough to be rejected outright. The value of K,, for Part (c) is, of course, completely out of line, so the maximum of 5 test shows a definite failure of that random number generator. We would expect the KS test in this experiment to have more difficulty locating global nonrandomness than local nonrandomness, since the basic obser- vations in Fig. 4 were made on samples of only 10 numbers each. If we were to take 20 groups of 1000 numbers each, part (b) would show a much more significant deviation. To illustrate this point, a single KS test was applied to all 200 of the observations that led to Fig. 4, and the following results were obtained: Part (a) Part (b) Part (c) K&o 0.477 1.537 2.819 Kzoo 0.817 0.194 0.058 (16) The global nonrandomness of the Fibonacci generator has definitely been de- tected here. We may summarize the Kolmogorov-Smirnov test as follows. We are given n independent observations Xl, . . . , X, taken from some distribution specified by a continuous function F(z). That is, F(z) must be like the functions shown in Fig. 3(b) and 3(c), having no jumps like those in Fig. 3(a). The procedure explained just before Eqs. (13) is carried out on these observations, so we obtain the statistics K,+ and K;. These statistics should be distributed according to Table 2. Some comparisons between the KS test and the x2 test can now be made. In the first place, we should observe that the KS test may be used in conjunction with the x2 test, to give a better procedure than the ad hoc method we mentioned when summarizing the x2 test. (That is, there is a better way to proceed than to make three tests and to consider how many of the results were suspect .) Suppose we have made, say, 10 independent x2 tests on different parts of a random sequence, so that values VI, VZ, . . . , VIO have been obtained. It is not a good policy simply to count how many of the V s are suspiciously large or small. This procedure will work in extreme cases, and very large or very small values

3.3.1 GENERAL TEST PROCEDURES 49 of Chapter 5. On the other hand, it is possible to avoid sorting in this particular application, as shown in exercise 23.) Step 3. The desired statistics are now given by the formulas (13) An appropriate choice of the number of observations, n, is slightly easier to make for this test than it is for the x2 test, although some of the considerations are similar. If the random variables X, actually belong to the probability distribution G(z), while they were assumed to belong to the distribution given by F(z), it will take a comparatively large value of n to reject the hypothesis that G(s) = F(z); f or we need n large enough that the empirical distributions G,(z) and F,(z) are expected to be observably different. On the other hand, large values of n will tend to average out locally nonrandom behavior, and such behavior is an undesirable characteristic that is of significant importance in most computer applications of random numbers; this makes a case for smaller values of n. A good compromise would be to take n equal to, say, 1000, and to make a fairly large number of calculations of KT,b,, on different parts of a random sequence, thereby obtaining values G3J,N~ G&L . . . , GJcdr)~ (14) We can also apply the KS test again to these results: Let F(x) now be the distribution function for KT,b,,, and determine the empirical distribution F7(x) obtained from the observed values in (14). Fortunately, the function F(z) in this case is very simple; for a large value of n like n = 1000, the distribution of K,+ is closely approximated by F,(z) = 1 - e-2z2, x 2 0. (15) The same remarks apply to K;, since Kz and K; have the same expected behavior. This method of using several tests for moderately large n, then combining the observations later in another KS test, will tend to detect both local and global nonrandom behavior. An experiment of this type (although on a much smaller scale) was made by the author as this chapter was being written. The maximum of 5 test described in the next section was applied to a set of 1000 uniform random numbers, yielding 200 observations X1, X2, . . . , XZOO that were supposed to belong to the distribution F(x) = x5 (0 5 x 2 1). The observations were divided into 20 groups of 10 each, and the statistic Kc, was computed for each group. The 20 values of K&, thus obtained, led to the empirical distributions shown in Fig. 4. The smooth curve shown in each of the diagrams in Fig. 4

RANDOM NUMBERS Table 2 SELECTED PERCENTAGE POINTS OF THE DISTRIBUTIONS K$ AND K, As in the chi-square test, we may now look up the values K,t, K; in a percentile table to determine if they are significantly high or low. Table 2 may be used for this purpose, both for K,+ and K;. For example, the probability is 75 percent that K,, will be 0.7975 or less. Unlike the chi-square test, the table entries are not merely approximations that hold for large values of n; Table 2 gives exact values (except, of course, for roundoff error), and the KS test may be reliably used for any value of VZ. As they stand, formulas (11) are not readily adapted to computer calculation, since we are asking for a maximum over infinitely many values of z. From the fact that F(z) is increasing and the fact that Fn(z) increases only in finite steps, however, we can derive a simple procedure for evaluating the statistics K,f and K;: Step 1. Obtain the observations X1,X2,. . . ,X, . Step 2. Rearrange the observations so that they are sorted into ascending order, i.e., so that Xr < X2 5 ..a 2 X,. (Efficient sorting algorithms are the subject

3.3.1 GENERAL TEST PROCEDURES 47 for a uniformly distributed random real number between zero and one, so the probability that X 5 2 is simply equal to z when 0 < z 5 1; for example, the probability that X < 3 is, naturally , 2. And part (c) shows the limiting distribution of the value V in the chi-square test (shown here with 10 degrees of freedom); this is a distribution that we have already seen represented in another way in Table 1. Note that F(z) always increases from 0 to 1 as z increases from –cm to +oo. If we make n independent observations of the random quantity X, thereby obtaining the values X1, X2, . . . , X, , we can form the empirical distribution function F,(z), where numberofXl,Xz,…,X,thatare