Free php web host - 3.3.3 THEORETICAL TESTS 75 (b) Let C =
3.3.3 THEORETICAL TESTS 75 (b) Let C = N/D, where N and D denote the numerator and denominator of the expression in part (a). Show that N2 < D2, hence -1 5 C 5 1; and obtain a formula for the difference 0 -N2. [Hint: See exercise 1.2.3-30.1 (C) If C = &I, show that oxk + PYk = 7, 0 < k < n, for some constants cy, p, and T, not all zero. 18. [A&%] (a) Show that if n = 2, the serial correlation coefficient (23) is always equal to -1 (unless the denominator is zero). (b) S imilarly, show that when n = 3, the serial correlation coefficient always equals -4. (c) Show that the denominator in (23) is zero if and only if Uo = UI =. = U,-I. 19. [M40] What are the mean and standard deviation of the serial correlation coeffi- cient (23) when n = 4 and the U s are independent and uniformly distributed between zero and one? 20. [M47] Find the distribution of the serial correlation coefficient (23), for general n, assuming that the U, are independent random variables uniformly distributed between zero and one. 21. [I91 What value of f is computed by Algorithm P if it is presented with the permutation (1,2,9,8,5,3,6,7,0,4)? 22. [18] For what permutation of (0, 1,2,3,4,5,6,7,8,9} will Algorithm P produce the value f = 1024? *3.3.3. Theoretical Tests Although it is always possible to test a random number generator using the methods in the previous section, it is far better to have a priori tests, i.e., theoretical results that tell us in advance how well those tests will come out. Such theoretical results give us much more understanding about the generation methods than empirical, trial-and-error results do. In this section we shall study the linear congruential sequences in more detail; if we know what the results of certain tests will be before we actually generate the numbers, we have a better chance of choosing a, m, and c properly. The development of this kind of theory is quite difficult, although some progress has been made. The results obtained so far are generally for statistical tests made over the entire period. Not all statistical tests make sense when they are applied over a full period-for example, the equidistribution test will give results that are too perfect-but the serial test, gap test, permutation test, maximum test, etc. can be fruitfully analyzed in this way. Such studies will detect global nonrandomness of a sequence, i.e., improper behavior in very large samples. The theory we shall discuss is quite illuminating, but it does not eliminate the need for testing local nonrandomness by the methods of Section 3.3.2. Indeed, it appears to be extremely hard to prove anything useful about short subsequences. Only a few theoretical results are known about the behavior of linear congruential sequences over less than a full period; these will be discussed at the end of Section 3.3.4. (See also exercise 18.)