Web And Email Hosting, Jsp Web Hosting Blog

152 RANDOM NUMBERS 3.5 The existence of oo-distributed sequences of a rather simple type is guaran- teed by the next theorem. Theorem F (J. Franklin). The [ 0,l) sequence Vc, U1, . . . , with U, = Pmodl (26) is oo-distributed for almost all real numbers 0 > 1. That is, the set {ele> land(26) is not oo-distributed } is of measure zero. The proofs of this theorem and some generalizations are given in Franklin s paper cited below. 1 Franklin has shown that t9 must be a transcendental number for (26) to be co-distributed. The powers (7rn mod 1) have been laboriously computed for n < 10000, using multiple-precision arithmetic, and the most significant 35 bits of each of these numbers, stored on a disk file, have successfully been used as a source of uniform deviates. According to Theorem F, the probability that the powers (v? mod 1) are oo-distributed is equal to 1; yet because there are uncountably many real numbers, this gives us no information as to whether the sequence is really m-distributed or not. It is a fairly safe bet that nobody in our lifetimes will ever prove that this particular sequence is not oo-distributed; but it might not be. Because of these considerations, one may legitimately wonder if there is any explicit sequence that is oo-distributed; i.e., is there an algorithm to compute real numbers U, for all n 2 0, such that the sequence (Un) is co-distributed? The answer is yes, as shown for example by D. E. Knuth in BIT 5 (1965), 246-250. The sequence constructed there consists entirely of rational numbers; in fact, each number U, has a terminating representation in the binary number system. Another construction of an explicit oo-distributed sequence, somewhat more complicated than the sequence just cited, follows from Theorem W below. See also N. M. Korobov, Izv. Akad. iVauk SSSR 20 (1956), 649-660. C. Does oo-distributed = random? In view of all the above theory about oo-distributed sequences, we can be sure of one thing: the concept of an oo- distributed sequence is an important one in mathematics. There is also a good deal of evidence that the following statement is a valid formulation of the intuitive idea of randomness: Deflnition Rl. A [ 0,l) sequence is defined to be random if it is an co- distributed sequence. We have seen that sequences meeting this definition will satisfy all the statistical tests of Section 3.3.2 and many more.

3.5 WHAT IS A RANDOM SEQUENCE? 151 By definition, 2sN = c c @j(n) -uj(n -d) -(+d -v& -4)))~ lInSN+q O

150 RANDOM NUMBERS 3.5 First we know that lim (~0, + ~1~ + . . . + Y(~-~)~) = i/bm, (16) n–too since the sequence is m-distributed. By Lemma E and Eq. (16), the theorem will be proved if we can show that lim sup (Y& + & + . . . + ytm-l),) I llmb2m-(17) n-03 This inequality is not obvious yet; some rather delicate maneuvering is necessary before we can prove it. Let q be a multiple of m, and consider qn) = c (44 -7 -q ). (18) Olj

3.5 WHAT IS A RANDOM SEQUENCE? 149 Thus a k-distributed sequence is the special case m = 1 in Definition E; the case m = 2 means that the k-tuples starting in even positions must have the same density as the k-tuples starting in odd positions, etc. Several properties of Definition E are obvious: An (m, k)-distributed sequence is (m, n)-distributed for 1 5 rc 5 k. (12) An (m, k)-distributed sequence is (d, k)-distributed for all divisors d of m. (13) We can also define the concept of an (m, k)-distributed bary sequence, as in Definition D; and the proof of Theorem A remains valid for (m, k)-distributed sequences. The next theorem, which is in many ways rather surprising, shows that the property of being co-distributed is very strong indeed, much stronger than we imagined it to be when we first considered the definition of the concept. Theorem C (Ivan Niven and H. S. Zuckerman). An co-distributed sequence is (m, k)-distributed for all positive integers m and k. Proof. It suffices to prove the theorem for bary sequences, by using the gen- eralization of Theorem A just mentioned. Furthermore, we may assume that m = k, because (12) and (13) tell us that the sequence will be (m, k)-distributed if it is (mk, mk)-distributed. So we will prove that any m-distributed b-ary sequence X0, X1, . . . is (m, m)- distributed for all positive integers m. Our proof is a simplified version of the original one given by Niven and Zuckerman in Pacific J. Math. 1 (1951), 103-109. The key idea we shall use is an important technique that applies to many situations in mathematics: If the sum of m quantities and the sum of their squares are both consistent with the hypothesis that the m quantities are equal, then that hypothesis is true. In a strong form, this principle may be stated as follows: Lemma E. Given m sequences of numbers (yjn) = yjlj~, ~71, . . . for 1 2 j 2 m, suppose that lim (YM + ~2~ + . . . + ymn) = ma, n+00 (14) lim sup (Y:, + yin + . . -+ yk.,) I mff . n-cc Then for each j, lim,,, yjn exists and equals cy. An incredibly simple proof of this lemma is given in exercise 9. 1 Resuming our proof of Theorem C, let z = zlz2.. . zm be a bary number, and say that 5 occurs at position p if Xp–m+lXp–m+2.. .X, = 2. Let ~j(n) be the number of occurrences of x at position p when p < n and pmodm = j. Let yyn = vj(n)/ n; we wish to prove that lim yjn = l/mbm. (15) n+m

148 RANDOM NUMBERS 3.5 We can also show that the serial correlation test is satisfied: Corollary S. If a [ 0,l) sequence is (k + 1)-distributed, the serial correlation coefficient between U, and Un+k tends to zero: lim k c UjUj+k -($ c uj)(k c Uj+k) n oo d(~cU32-(~~uj)2)(~CUjZ+k-(~Cuj+k)2) = * (All summations here are for 0 5 j < n.) Proof. By Theorem B, the quantities tend to the respective limits 4, 6, 6, 4, 4 as 72 + 00. 1 Let us now consider some slightly more general distribution properties of sequences. We have defined the notion of /c-distribution by considering all of the adjacent k-tuples; for example, a sequence is a-distributed if and only if the points @Jo, w, (Ul, u2>, 672, U3), 073, U4), P4, u51, . . . are equidistributed in the unit square. It is quite possible, however, that this can happen while alternate pairs of points (UI, Uz), (Us, U4), (Us, UG), . . . are not equidistributed; if the density of points (U2n–1, Uzn) is deficient in some area, the other points (Uz,, U2n+l) might compensate. For example, the periodic binary sequence (Xn) = o,o,o, 1, o,o,o, 1, l,l,O, 1, l,l,O, 1, o,o,o, 1, . . . , (11) with a period of length 16, is seen to be 3-distributed; yet the sequence of even- numbered elements (Xsn) = 0, 0, 0, 0, 1, 0, 1, 0, . . . has three times as many zeros as ones, while the subsequence of odd-numbered elements (Xan+i) = 0, 1, 0, 1, 1, 1, 1, 1, . . . has three times as many ones as zeros. If a sequence (Un) is oo-distributed, example (11) shows that it is not at all obvious that the subsequence of alternate terms (Uzn) = UO, U2, U4, Us, . . . will be co-distributed or even l-distributed. But we shall see that (Uzn) is, in fact, m-distributed, and much more is true. Definition E. A [ 0,l) sequence (Un) is said to be (m, k)-distributed if Pr( l 5 Umn+j < %r u2 2 Umn+j+l < 212, . . . , uk 5 Umn+j+k-1 < vk) = (211 -u1) . . . ( ?& -t k) for all choices of red numbers ur, V~ with 0 2 u7 < v, 5 1 for 1 < r 5 k, and for a1J integers j with 0 5 j < m.

3.5 WHAT IS A RANDOM SEQUENCE? 147 Proof. The definition of a k-distributed sequence states that this result is true in the special case that 1, if u1 5 z1 < wl,.. .,uk 2 xk < vk; f(x1, . . . , xk) = (9) 0, otherwise. Therefore Eq. (8) is true whenever f = al fl +asf~ +. . . +a,fm and when each fj is a function of type (9); in other words, Eq. (8) holds whenever f is a step- function obtained by (i) partitioning the unit k-dimensional cube into subcells whose faces are parallel to the coordinate axes, and (ii) assigning a constant value to f on each subcell. Now let f be any Riemann-integrable function. If E is any positive number, we know (by the definition of Riemann-integrability) that there exist step func- tions f and 7 such that f(zl,. . . , zk) 2 f(xl, . . . , zk) 5 7(x1,. . . , xk), and such that the difference of the integrals of f and 7 is less than 6. Since Eq. (8) holds for f and 7, and since - we conclude that Eq. (8) is true also for f. 1 Theorem B can be applied, for example, to the permutation test of Section 3.3.2. Let (pl,pz,. .., pk) be any permutation of the numbers {1,2,. . . , k}; we want to show that pr(un+p~–l < &1+~~-1 < . . . < un+pk-l) = l/k!. (10) To prove this, assume that the sequence (Un) is k-distributed, and let 1, if xpl < xpz < . < xpr; f(x1,. . . , xk) = 0, otherwise. We have pr(un-tpl-1 < Un+pz–l < *. . < un+pk-l) -I J f(xl, . . . . . . , xk) dXl dXk ~;:;~p~~zpk…lx’” dq,,f2 dxpl = ;. Corollary P. If a [ 0,l) sequence is k-distributed, it satisfies the permutation test of order k, in the sense of Eq. (10). 1

146 RANDOM NUMBERS 3.5 Theorem A. Let (Un) = UO, VI, UZ, . . . be a [ 0,l) sequence. If the sequence (1bjG.J) = lbjUoJ, Ly&J, 14U2J, . . . is a k-distributed bj-ary sequence for all bj in an infinite sequence of integers 1 < bl < bz < b3 < +. ., then the original sequence (Un) is k-distributed. As an example of this theorem, suppose that bj = 2j. The sequence [2Wo], 12jU1J, . . . is essentially the sequence of the first j bits of the binary representations of UO, VI, . . . . If all these integer sequences are k-distributed, in the sense of Definition D, then the real-valued sequence UO, UI, . . . must also be k-distributed in the sense of Definition B. Proof of Theorem A. If the sequence [bU,-,J, LbUlJ, . . . is k-distributed, it follows by the addition of probabilities that Eq. (5) holds whenever each Uj and V, is a rational number with denominator b. Now let Uj, VU~ be any real numbers, and let ~5, v$ be rational numbers with denominator b such that U> 5 Uj < IL; + l/b, 215 2 Vj < 215 + l/b. Let S(n) be the statement that u1 5 U, < VI, . . . , uk 5 Un+k-l < vk. we have FS(n)) I Pr 4 I U, < vi + f , . . . , ?k 5 h+k-1 < 21; + f 1 = v;-u;– b NOW I($ - U: f l/b) -(Vj -Uj)J 5 2/b; since our inequalities hold for all b = bj, and since bj + COas j + 00, we have (vl -ul). . . (vk -uk) 5 i?@(n)) 5 E(S(n)) 5 (Vl -Ul). . . (vk -uk). 1 The next theorem is our main tool for proving things about k-distributed sequences. Theorem B. Let (Un) be a k-distributed [ 0,l) sequence, and Jet f(zl, ~2,. . . , zk) be a Riemann-integrable function of k variables; then h c f(uj,Uj+l,…rUj+k–l) n-+m n OIj

3.5 WHAT IS A RANDOM SEQUENCE? 145 sequence 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, . . . . It has been conjectured that this sequence is co-distributed, but nobody has yet been able to prove that it is even l-distributed. Let us analyze these concepts a little more closely in the case when Ic equals a million. A binary sequence that is lOOOOOO-distributed is going to have runs of a million zeros in a row! Similarly, a [ 0,l) sequence that is lOOOOOO-distributed is going to have runs of a million consecutive values each of which is less than 4. It is true that this will happen only (4) loooooo of the time, on the average, but the fact is that it does happen. Indeed, this phenomenon will occur in any truly random sequence, using our intuitive notion of truly random. One can easily imagine that such a situation will have a drastic effect if this set of a million truly random numbers is being used in a computer-simulation experiment; there would be good reason to complain about the random number generator. However, if we have a sequence of numbers that never has runs of a million consecutive U s less than f , the sequence is not random, and it will not be a suitable source of numbers for other conceivable applications that use extremely long blocks of U s as input. In summary, a truly random sequence will exhibit local nonrandomness. Local nonrandomness is necessary in some applications, but it is disastrous in others. We are forced to conclude that no sequence of random numbers can be adequate for every application. In a similar vein, one may argue that there is no way to judge whether a finite sequence is random or not; any particular sequence is just as likely as any other one. These facts are definitely stumbling blocks if we are ever to have a useful definition of randomness, but they are not really cause for alarm. It is still possible to give a definition for the randomness of infinite sequences of real numbers in such a way that the corresponding theory (viewed properly) will give us a great deal of insight concerning the ordinary finite sequences of rational numbers that are actually generated on a computer. Furthermore, we shall see later in this section that there are several plausible definitions of randomness for finite sequences. B. co-distributed sequences. Let us now undertake a brief study of the theory of sequences that are co-distributed. To describe the theory adequately, we will need to use a bit of higher mathematics, so we assume in the remainder of this subsection that the reader knows the material ordinarily taught in an advanced calculus course. First it is convenient to generalize Definition A, since the limit appearing there does not exist for all sequences. Let us define Fr(S(n)) = lim sup (~(n)/n), &(S(n)) = lim&f (~(n)/n). (7) 72-00 Then Pr(S(n)), i f i t exists, is the common value of Pr(S(n)) and E(S(n)). We have seen that a k-distributed [ 0,l) sequence leads to a k-distributed bary sequence, if U is replaced by [MY]. Our first theorem shows that a converse result is also true.

144 RANDOM NUMBERS 3.5 general, for any positive integer k we can require our sequence to be k-distributed in the following sense: Definition B. The sequence (1) is said to be k-distributed if Pr(ul < U, . . . (vk -uk) (5) for a11 choices of real numbers Uj, vj, with 0 2 Uj < 1-j < 1, for 1 5 j 5 k. An equidistributed sequence is a l-distributed sequence. Note that if k > 1, a k-distributed sequence is always (k -1)-distributed, since we may set uk = 0 and vk = 1 in Eq. (5). Thus, in particular, any sequence that is known to be 4-distributed must also be 3-distributed, a-distributed, and equidistributed. We can investigate the largest k for which a given sequence is k-distributed; and this leads us to formulate Definition C. A sequence is said to be co-distributed if it is k-distributed for all positive integers k . So far we have considered [ 0,l) sequences, i.e., sequences of real numbers lying between zero and one. The same ideas apply to integer-valued sequences; let us say a sequence (Xn) = X0, X1, X2, . . . is a bary sequence if each X, is one of the integers 0, 1, . . . , b - 1. Thus, a 2-ary (binary) sequence is a sequence of zeros and ones. We also say that a k-digit bary number is a string of k integers ~1~2 . . . xk, where 0 5 xj < b for 1 5 j 5 k. Definition D. A b-ary sequence is said to be k-distributed if Pr(x,&+1.. .&f&l = X1X2.. . xk) = l/bk (6) for all b-ary numbers x1x2 . . . xk. It is clear from this definition that if U,-,, VI, . . . is a k-distributed [ 0,l) sequence, then the sequence LbUoJ, [bUIJ, . . . is a k-distributed bary sequence. (If we set Uj = xj/b, vj = (Zj + 1)/b, X, = [bun], Eq. (5) becomes Eq. (6).) Furthermore, every k-distributed bary sequence is also (k -1)-distributed, if k > 1: we add together the probabilities for the bary numbers xl.. . xk-10, Xl . . . xk-1 1, . . . , xl . . . xk-1 (b -1) to obtain Pr(x, . . .a&+&2 = X1 . . .x&l) = l/b - . (Probabilities for disjoint events are additive; see exercise 5.) It therefore is natural to speak of an co-distributed bary sequence, as in Definition C above. The representation of a positive real number in the radix-b number system may be regarded as a bary sequence; for example, 7r corresponds to the lo-ary

3.5 WHAT IS A RANDOM SEQUENCE? 143 an adequate definition of randomness according to these criteria, although many interesting questions remain to be answered. Let u and u be real numbers, 0 5 u < u 2 1. If U is a random variable that is uniformly distributed between 0 and 1, the probability that u 5 U < w is equal to ZI - u. For example, the probability that 3 5 U < $ is 4. How can we translate this property of the single number U into a property of the infinite sequence UO, VI, Uz, . . . ? The obvious answer is to count how many times U, lies between u and w, and the average number of times should equal w - u. Our intuitive idea of probability is based in this way on the frequency of occurrence. More precisely, let v(n) be the number of values of j, 0 5 j < n, such that u 5 Uj < v; we want the ratio v(n)/n to approach the value v - u as n approaches infinity: lim V(n)/n = 2, - u. (4 n-00 If this condition holds for all choices of u and v, the sequence is said to be equidistributed. Let S(n) be a statement about the integer n and the sequence VI, U2, . . . ; for example, S(n) might be the statement considered above, u < U, < v. We can generalize the idea used in the preceding paragraph to define the probability that S(n) is true with respect to a particular infinite sequence: Let v(n) be the number of values of j, 0 5 j < n, such that S(j) is true. Definition A. We say Pr(S(n)) = X, if limn–rm u(n)/n = X. (Read, The probability that S(n) is true equals X, if the limit as n tends to infinity of v(n)/n equals A. ) In terms of this notation, the sequence Uo, VI, . . . is equidistributed if and only if Pr(u 2 U,, < V) = v -u, for all real numbers u, u with 0 5 u < v 5 1. A sequence may be equidistributed without being random. For example, if uo, Ul, … and VO, VI, . . . are equidistributed sequences, it is not hard to show that the sequence ~,~,W2,~,.*. = @Jo, $+po, gJ1, i+g4 7 … is also equidistributed, since the subsequence DUO, $UI, . . . is equidistributed between 0 and 4, while the alternate terms f + $VO, 3 + JVl, . . . , are equi- distributed between 4 and 1. In the sequence of W s, a value less than i is always followed by a value greater than or equal to 4, and conversely; hence the sequence is not random by any reasonable definition. A stronger property than equidistribution is needed. A natural generalization of the equidistribution property, which removes the objection stated in the preceding paragraph, is to consider adjacent pairs of numbers of our sequence. We can require the sequence to satisfy the condition Pr(ul 5 U, < 211 and ~2 2 G+I < 7~2)= (ul -u1)(v2 - u2) (4)