3.5 WHAT IS (Web hosting asp) A RANDOM SEQUENCE? 157 because
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