3.5 WHAT IS A RANDOM SEQUENCE? (Email web hosting) 159 To
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.