146 RANDOM NUMBERS 3.5 (Bulletproof web design) Theorem A. Let (Un)
146 RANDOM NUMBERS 3.5 Theorem A. Let (Un) = UO, VI, UZ, . . . be a [ 0,l) sequence. If the sequence (1bjG.J) = lbjUoJ, Ly&J, 14U2J, . . . is a k-distributed bj-ary sequence for all bj in an infinite sequence of integers 1 < bl < bz < b3 < +. ., then the original sequence (Un) is k-distributed. As an example of this theorem, suppose that bj = 2j. The sequence [2Wo], 12jU1J, . . . is essentially the sequence of the first j bits of the binary representations of UO, VI, . . . . If all these integer sequences are k-distributed, in the sense of Definition D, then the real-valued sequence UO, UI, . . . must also be k-distributed in the sense of Definition B. Proof of Theorem A. If the sequence [bU,-,J, LbUlJ, . . . is k-distributed, it follows by the addition of probabilities that Eq. (5) holds whenever each Uj and V, is a rational number with denominator b. Now let Uj, VU~ be any real numbers, and let ~5, v$ be rational numbers with denominator b such that U> 5 Uj < IL; + l/b, 215 2 Vj < 215 + l/b. Let S(n) be the statement that u1 5 U, < VI, . . . , uk 5 Un+k-l < vk. we have FS(n)) I Pr 4 I U, < vi + f , . . . , ?k 5 h+k-1 < 21; + f 1 = v;-u;– b NOW I($ - U: f l/b) -(Vj -Uj)J 5 2/b; since our inequalities hold for all b = bj, and since bj + COas j + 00, we have (vl -ul). . . (vk -uk) 5 i?@(n)) 5 E(S(n)) 5 (Vl -Ul). . . (vk -uk). 1 The next theorem is our main tool for proving things about k-distributed sequences. Theorem B. Let (Un) be a k-distributed [ 0,l) sequence, and Jet f(zl, ~2,. . . , zk) be a Riemann-integrable function of k variables; then h c f(uj,Uj+l,…rUj+k–l) n-+m n OIj