J2ee Web Hosting, Perl Scripting And Developing Blog

3.5 WHAT IS A RANDOM SEQUENCE? 161 Now when E 2 min(p, 4) we have ln(p/(p + c))~+ = -6 -$ + $ -& +. *. < -E, ln(q/(q -E)) + = +c -$ -$ -& -. . < E-G, so we have the following bound for all r > 0 and 0 5 E 5 min(p, 4): (33) But C(r, E) is 2r+1 times this left,-hand quantity, in the special case p = q = f , hence by (32) B(r, t) has measure 2 2- C(r, t) < 2ePtZ7. The next step is to define B*(r, t) = B(r, E) u B(r + 1, E) U B( + 2, t) U . . . . The measure of B*(r, E) is at most CkZ,. 2eeEZk, and this is the remainder of a convergent series, so rlimm(measure of B*(r, E)) = 0. (34) Now if z is a real number whose binary expansion (0.X,x1 . . . )2 leads to an infinite sequence (X,,)R that is not l-distributed, and if v(r) denotes the number of zeros in the first r elements of the latter sequence, then for some E > 0 and infinitely many r. This means z is in B*(r, E) for all r. So finally we find that WRY .9 = u n B*(r, l/t); t>2 ry1 an4 by (341, flTrl B*(r, l/t) has measure zero for all t. Hence N(R, S) has measure zero. 1 From the existence of binary sequences satisfying Definition R6, we can show the existence of [ 0,l) sequences that are random in this sense. For details, see exercise 36. The consistency of Definition R6 is thereby established. E. Random finite sequences. An argument was given above to indicate that it is impossible to define the concept of randomness for finite sequences; any given finite sequence is as likely as any other. Still, nearly everyone would agree that the sequence 011101001 is more random than 101010101, and even the latter

160 RANDOM NUMBERS 3.5 Therefore let R and S be fixed. Consider the set T(alas . . . a,) defined for all binary numbers al as . . . a7 as the set of all 2 corresponding to (Xn), such that (X8,)2 has 2 r elements whose first r elements are respectively equal to al, us, . ..) a,. Our first result is that T(ula2,. . a,) has measure < 2-r. (32) To prove this, we start by observing that T(arus . . . a,) is a measurable set: Each element of T(ula2 . . . a,) is a real number z = (O.XoXr . . . )Z for which there exists an integer m such that algorithm S determines distinct values SO, sl, . . . , s,, and rule R determines a subsequence of X,,, X,,, . . . , XsW such that X,, is the rth element of this subsequence. The set of all real y = (O.YoY, . . . )s such that Y,, = X,, for 0 2 Ic 5 m also belongs to T(alus . . .a,), and this is a measurable set consisting of the finite union of dyadic subintervals Ibl...bt. Since there are only countably many such dyadic intervals, we see that T(ulus . . . a,) is a countable union of dyadic intervals, and it is therefore measurable. Furthermore, this argument can be extended to show that the measure of T(ul . . . ar-l 0) equals the measure of T(ur . . . ~~-1 l), since the latter is a union of dyadic intervals obtained from the former by requiring that Y,, = X,, for 0 5 Ic < m and Y,, # X,,. Now since T(al . , . u,.-~ 0) U T(UI . . . a7--1 1) 2 T(al . . . a,-r), the measure of T(UIU~ . . . a,) is at most one-half the measure of T(ul . . . a,-l). The inequality (32) follows by induction on T. Now that (32) has been established, the remainder of the proof is essentially to show that the binary representations of almost all real numbers are equi- distributed. The next few paragraphs constitute a rather long but not difficult proof of this fact, and they serve to provide probability estimates that are useful in many other problems. For 0 < E < 1, let B(r, E) be U T(ur . . . a,), where the union is taken over all binary numbers al . . . a, for which the number V(T) of zeros among al . . . a7 satisfies Iv(r) -$1 > 1 + U. The number of such binary numbers is C(T, e) = C (;) summed over the values of lc with (k - &rI 2 1 + ET. A suitable estimate for the tail of the binomial distribution can be obtained by the following standard trick: Let 2: and p be any positive numbers less than 1, let q = 1 -p, and let s = (p + 6)~. Then ; pkqr-kZs-k 5 0 By elementary calculus, the minimum value of ss(q + p/z> occurs when x = (p/(p + c))/(q/(q -E)), and this value of x yields c (r>p% * I ((–$) (&y. k 2 (TJ+E)~

3.5 WHAT IS A RANDOM SEQUENCE? 159 To show finally that sequences satisfying Definition R5 exist, we note first that if (Un) is a [ 0,l) sequence of rational numbers and if R is a computable sub- sequence rule for a bary sequence, we can make R into a computable subsequence rule R for (Un) by letting fL(xl,. . . , z,) in R equal fn(LbzlJ,. . . , lbxnJ) in R. If the [ 0,l) sequence (Un)R is equidistributed, so is the bary sequence ([bUnJ)R. Now the set of all computable subsequence rules for bary sequences, for all values of b, is countable (since only countably many effective algorithms are possible), so they may be listed in some sequence RI, R2, . . . ; therefore Algorithm W defines a [ 0,l) sequence that is random in the sense of Definition R5. This brings us to a somewhat paradoxical situation. As we mentioned earlier, no effective algorithm can define a sequence that satisfies Definition R4, and for the same reason there is no effective algorithm that defines a sequence satisfying Definition R5. A proof of the existence of such random sequences is necessarily nonconstructive; how then can Algorithm W construct such a sequence? There is no contradiction here; we have merely stumbled on the fact that the set of all effective algorithms cannot be enumerated by an effective algo- rithm. In other words, there is no effective algorithm to select the jth comput- able subsequence rule Rj; this happens because there is no effective algorithm to determine if a computational method ever terminates. (We shall return to this topic in Chapter 11.) Important large classes of algorithms can be systemati- cally enumerated; thus, for example, Algorithm W shows that it is possible to construct, with an effective algorithm, a sequence that satisfies Definition R5 if we restrict consideration to subsequence rules that are primitive recursive. By modifying step W6 of Algorithm W, so that it sets U, t Vjft instead of vj, where t is any nonnegative integer depending on al, . . . , a,, we can show that there are uncountably many [ 0,l) sequences satisfying Definition R5. The following theorem shows still another way to prove the existence of uncountably many random sequences, using a less direct argument based on measure theory, even if the strong definition R6 is used: Theorem M. Let the real number x, 0 5 x < 1, correspond to the binary sequence (Xn) if the binary representation of x is (0.X0X1.. .)2. Under this correspondence, almost all x correspond to binary sequences that are random in the sense of Definition R6. (In other words, the set of all real x that correspond to a binary sequence that is nonrandom by Definition R6 has measure zero.) Proof. Let S be an effective algorithm that determines an infinite sequence of distinct nonnegative integers (s,), where the choice of s, depends only on n and X,, for 0 2 Ic < n; and let R be a computable subsequence rule. Then any binary sequence (Xn) leads to a subsequence (X,,)R, and Definition R6 says this subsequence must either be finite or l-distributed. It suffices to prove that for fixed R and S the set N(R, S) of all real x corresponding to (Xn), such that (X,,)R is infinite and not l-distributed, has measure zero. For x has a nonrandom binary representation if and only if x is in U N( R, S), taken over the countably many choices of R and S.

158 RANDOM NUMBERS 3.5 Strictly speaking, this is not an algorithm, since it doesn t terminate; it would of course be easy to modify the procedure to stop when n reaches a given value. The reader will find it easier to grasp the idea of the construction by trying it out manually, replacing the number 3 .4 -l of step W4 by 27 during this experiment. Algorithm W is not meant to be a practical source of random numbers. It is intended to serve only a theoretical purpose: Theorem W. Let (Un) be the sequence of rational numbers defined by Algorithm W, and let Ic be a positive integer. If the subsequence (Un)Rk is infinite, it is l-distributed. Proof. Let A[al, . . . , a,] denote the (possibly empty) subsequence of (Un) con- taining precisely those elements U, that, for all j < T, belong to subsequence (Un)Rj if aj = 1 and d o not belong to subsequence (Un)Rj if aj = 0. It suffices to prove, for all r 2 1 and all pairs of binary numbers al . . . a,. and bl. . . b,, that Pr(U, E Ib1…6,) = 2- with respect to the subsequence 4~1,. . . , a,], whenever the latter is infinite. (See Eq. (30).) For if r 2 k, the infinite sequence (U,)Rk is the finite union of the disjoint subsequences -+I,. . . , a,] for ak = 1 and aj = 0 or 1 for 1 5 j 5 T, j # Ic; and it follows that Pr(U, E lbl…t+) = 2- with respect to (Un)Rk. (See exercise 33.) This is enough to show that the sequence is l-distributed, by Theorem A. Let B[al, . . . , a,] denote the subsequence of (Un) that consists of the values for those n in which C[al,. . . , a,] is increased by one in step W6 of the algo- rithm. By the algorithm, B[al, . . . , a,] is a finite sequence with at most 3.4 -l elements. All but a finite number of the members of A[al, . . . , a,] come from the subsequences B[al, . . . , a,, . . . , at], where aj = 0 or 1 for r < j 5 t. Now assume that A[al, . . . ,ar] is infinite, and let A[al,. . . ,a,] = (Us,), where SO < s1 < s2 5 … . If N is a large integer, with 4r 5 44 < N 5 44+ , it follows that the number of values of k < N for which Us, is in Ibl,..*, is (except for finitely many elements at the beginning of the subsequence) v(N) = v(N1) +. . . + v(N,). Here m is the number of subsequences B[al, . . . , at] listed above in which Us, appears for some k < N; Nj is the number of values of k with Us, in the corresponding subsequence; and v(Nj) is the number of such values that are also in 4, ,,,t,, . Therefore by Lemma T, Iv(N) -2-?NI = lv(Nl) -2- N1 +. . . + v(N,) -2- lv,l 2 Iv(Nl) -2- N1I + . . . + Iv(Nm) -2-7N,I

3.5 WHAT IS A RANDOM SEQUENCE? 157 because we believe that a truly random sequence exists and satisfies R6; but a proof is really necessary to show that the definition is consistent. An interesting method for constructing sequences satisfying Definition R5 has been found by A. Wald, starting with a very simple l-distributed sequence. Lemma T. Let the sequence of real numbers (I&) be defined in terms of the binary system as follows: vi = 0, VI = .l, v2 = .Ol, v, = .ll, vi = .OOl, . . . v, = .C,…Cll ifn=2r+c12r-1+…+c,. (29) Let, Ibl…b, denote the set of all real numbers in [ 0,l) whose binary representation begins with O.bl . . . b,; thus &…b, = [(Oh . . . br)2, (Oh . . . br)2 + 2-7. (30) Then if u(n) denotes the number of Vj in Ibl…b, for 0 5 k < n, we have Iu(n)/n -2Trl 5 l/n. (31) Proof. Since u(n) is the number of Ic for which k mod 27 = (b, . . b1)2, we have u(n) = t or t + 1 when [n/27] = t. Hence Iv(n) -n/a 1 5 1. 1 It follows from (31) that the sequence ([2 T/nJ) is an equidistributed 2r-ary sequence; hence by Theorem A, (I&) is an equidistributed [ 0,l) sequence. Indeed, it is pretty clear that (Vn) is about as equidistributed as a [ 0,l) sequence can be. (For further discussion of this and related sequences, see J. G. van der Corput, Proc. Koninklijke Nederl. Akad. Wetenschappen 38 (1935), 813-821, 1058-1066; J. H. Halton, Numerische Math. 2 (1960), 84-90, 196; L. H. Ramshaw, J. Number Theory, to appear.) Now let R1, R2, . . . be infinitely many subsequence rules; we seek a sequence (Un) for which all the infinite subsequences (Un)Rj are equidistributed. Algorithm W (Wald sequence). Given an infinite sequence of subsequence rules RI, R2, . . . that define subsequences of [ 0,l) sequences of rational numbers, this procedure defines a [ 0,l) sequence (Un). The computation involves infinitely many auxiliary variables C[al, . . . , a,], where r 2 1 and where a3 = 0 or 1 for 1 5 j 2 r. These variables are initially all zero. Wl. [Initialize n.] Set n t 0. W2. [Initialize r.] Set r t 1. W3. [Test R,.] If the element lJ, is to be in the subsequence defined by R,, based on the values of uk for 0 5 k < n, set a, t 1; otherwise set a, t 0. w4. [B[a+., a,] full?] If C[Ul ) . . . , a,] < 3.4 - , go to W6. W5. [Increase r.] Set 7 e r + 1 and return to W3. W6. [Set Un.] Increase the value of C[al, . . . , a,] by 1 and let k be its new value. Set U, c Vk, where Vk is defined in Lemma T above. W7. [Advance n.] Increase n by 1 and return to W2. 1

156 RANDOM NUMBERS 3.5 Definition R5. A b-ary sequence is said to be random if every infinite sub- sequence defined by a computable subsequence rule is l-distributed. A [ 0,l) sequence (Un) is said to be random if the b-ary sequence (lbUnJ) is random for all integers b 2 2. Note that Definition R5 says only l-distributed, not co-distributed. It is interesting to verify that this may be done without loss of generality. For we may define an obviously computable subsequence rule @al. . . Q) as follows, givenanyb-arynumberal…ak:Letf,(zl,…,z,)=lifandonlyifnLk-l and zn-k+l = al, . . . , x,-l = a&l, Z% = C.&. Now if (Xn) is a h-distributed bary sequence, this rule R(ul . . . ak)-which selects the subsequence consisting of those terms just following an occurrence of al . . . uk-defines an infinite sub- sequence; and if this subsequence is l-distributed, each of the (lc + 1)-tuples a1 . . . a@k+l for 0 5 ak+l < b occurs with probability l/b +l in (Xn). Thus we can prove that a sequence satisfying Definition R5 is k-distributed for all k, by induction on k. Similarly, by considering the composition of subsequence rules-if R1 defines an infinite subsequence (X,)Rl, then we can define RlRs to be the subsequence rule for which (Xn)R1R2 = ((X,)Rl)Rz-we find that all subsequences considered in Definition R5 are co-distributed. (See exercise 32.) The fact that co-distribution comes out of Definition R5 as a very special case is encouraging, and it is a good indication that we may at last have found the definition of randomness we have been seeking. But alas, there still is a problem. It is not clear that sequences satisfying Definition R5 must satisfy Definition R4. The computable subsequence rules we have just specified always enumerate subsequences (X,,) for which SO < s1 < … , but (sn) does not have to be monotone in R4; it must only satisfy the condition s, # s, for n # m. To meet this objection, we may combine Definitions R4 and R5 as follows: Definition R6. A b-ary sequence (Xn) is said to be random if, for every effective algorithm that specifies an infinite sequence of distinct nonnegative integers (sn) as a function of n and the values of X,,, . . . , X,,-,, the subsequence (X,,) corresponding to this algorithm is random in the senseof Definition R5. A [ 0,l) sequence (Un) is said to be random if the b-ary sequence ( [bUnJ) is random for all integers b 2 2. The author contends* that this definition surely meets all reasonable philo- sophical requirements for randomness, so it provides an answer to the principal question posed in this section. D. Existence of random sequences. We have seen that Definition R3 is too strong, in the sense that no sequence can satisfy that definition; and the formulation of Definitions R4, R5, and R6 above was carried out in an attempt to recapture the essential characteristics of Definition R3. In order to show that Definition R6 is not overly restrictive, it is still necessary for us to prove that sequences satisfying all these conditions exist. Intuitively, we feel quite sure that there is no problem, *At least, he made such a contention when originally preparing the material for this section in 1966.

3.5 WHAT IS A RANDOM SEQUENCE? 155 contradiction, since almost all 6 tire uncomputable by algorithms. The following facts are known, for example: (i) The sequence (en mod 1) satisfies Definition R4 for almost all real 0 > 1, if co-distributed is replaced by l-distributed. This theorem was proved by J. F. Koksma, Compositio Mathematics 2 (1935), 250- 258. (ii) The particular sequence (escn) mod 1) is co-distributed for almost all real 19 > 1, if (s(n)) . for which s(n + 1) -s(n) -+ co 1s a sequence of integers as n + co. For example, we could have s(n) = n2, or s(n) = LnlgnJ. Definition R4 is much stronger than Definition Rl; but it is still reasonable to claim that Definition R4 is too weak. For example, let (Un) be a truly random sequence, and define the subsequence (Us,) by the following rules: SO = 0, and (for n > 0) s, is the smallest integer 2 n for which Us,–l, Us,-2, . . . , Usn-n are all less than 4. Thus we are considering the subsequence of values following the first consecutive run of n values less than 4. Suppose that U, < 3 corresponds to the value heads in the flipping of a coin. Gamblers tend to feel that a long run of heads makes the opposite condition, tails, more probable, assuming that a true coin is being used; and the subsequence (Us,) just defined corresponds to a gambling system for a man who places his nth bet on the coin toss following the first run of n consecutive heads. The gambler may think that Pr(Us, 2 4) is more than 4, but of course in a truly random sequence (Us,) will be completely random. No gambling system will ever be able to beat the odds! Definition R4 says nothing about subsequences formed according to such a gambling system, so apparently we need something more. Let us define a subsequence rule R as an infinite sequence of functions (fn(G,.. . > 2,)) where, for n 2 0, fn is a function of n variables, and the value of fn(sl,. . . , z,) is either 0 or 1. Here x1, . . . , 2, are elements of some set S. (Thus, in particular, fo is a constant function, either 0 or 1.) A sub- sequence rule R defines a subsequence of any infinite sequence (Xn) of elements of S as follows: The nth term X, is in the subsequence (Xn)R if and only if fn(XO,Xl,… ,XnpI) = 1. Note that the subsequence (Xn)R thus defined is not necessarily infinite, and it may in fact contain no elements at all. For example, the gambler s subsequence just described corresponds to the following subsequence rule: fo = 1; and for n > 0, fn(zl,. . . , z,) = 1 if and only if there is some k in the range 0 < k 2 n such that the k consecutive parameters x,, x,-l, . . . , x,-k+1 are all < 3 when m = n but not when k < m < n. A subsequence rule R is said to be computable if there is an effective algo- rithm that determines the value of fn(xl,. . . ,x,), when n and x1, . . . , 2, are given as input. We had better restrict ourselves to computable subsequence rules when trying to define randomness, lest we obtain an overly restrictive definition like R3 above. But effective algorithms cannot deal nicely with arbitrary real numbers as inputs; for example, if a real number x is specified by an infinite radix-10 expansion, there is no algorithm to determine if x is < 6 or not, since all digits of the number 0.333.. . have to be examined. Therefore computable subsequence rules do not apply to all [ 0,l) sequences, and it is convenient to base our next definition on bary sequences.

154 RANDOM NUMBERS 3.5 Note that the definition of equidistribution says that Pr(u 2 U, < U) = v -U. There is an obvious way to generalize this definition, using measure theory: If S c [ 0,l) is a set of measure 1-1, then Pr(U, E S) = p, (27) for all random sequences (Un). In particular, if S is the set of rationals, it has measure zero, so no sequence of rational numbers is equidistributed in this generalized sense. It is reasonable to expect that Theorem B could be extended to Lebesgue integration instead of Riemann integration, if property (27) is stipulated. However, once again we find that definition (27) is too strict, for no sequence satisfies that property. If Ue, Ui, . . . is any sequence, the set s = {UO,Ul,...} is of measure zero, yet Pr(U, E S) = 1. Thus, by the force of the same argument we used to exclude rationals from random sequences, we can exclude all random sequences. So far Definition Rl has proved to be defensible. There are, however, some quite valid objections to it. For example, if we have a random sequence in the intuitive sense, the infinite subsequence uo, Ul, u4, us, . ", u,a, . . . (28) should also be a random sequence. This is not always true for an oo-distributed sequence. In fact, if we take any oo-distributed sequence and set U,Z c 0 for all n, the counts ok that appear in the test of k-distributivity are changed by at most fi, so the limits of the ratios vk(n)/n remain unchanged. Definition Rl unfortunately fails to satisfy this randomness criterion. Perhaps we should strengthen Rl as follows: Definition R3. A [ 0,l) sequence is said to be random if each of its infinite subsequences is oo-distributed. Once again, however, the definition turns out to be too strict; any equidistributed sequence (Un) has a monotonic subsequence with US, < US, < US, < . . . . The secret is to restrict the subsequences so that they could be defined by somebody who does not look at U, before deciding whether or not it is to be in the subsequence. The following definition now suggests itself: Definition R4. A [ 0,l) seqyence (Un) is said to be random if, for every effective algorithm that specifies an infinite sequence of distinct nonnegative integers sn for n > 0, the subsequence US,, U,,, US,, . . . corresponding to this algorithm is oo-distributed. The algorithms referred to in Definition R4 are effective procedures that compute s,, given n. (See Section 1.1.) Thus, for example, the sequence (.rr mod 1) will not satisfy R4, since it is either not equidistributed or there is an effective algorithm that determines an infinite subsequence sn with (~$0 mod 1) < (+ modl) < (7rITs2 < ... . Similarly, no explicitly defined sequence modl) can satisfy Definition R4; this is appropriate, if we agree that no explicitly defined sequence can really be random. It is quite likely, however, that the sequence (19~ mod 1) will satisfy Definition R4, for almost all real numbers 0 > 1; this is no

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