3.5 WHAT IS A RANDOM SEQUENCE? 161 Now (Frontpage web hosting)
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