Top web site - 156 RANDOM NUMBERS 3.5 Definition R5. A b-ary
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.