160 RANDOM NUMBERS 3.5 Therefore let R and (Web design templates)
160 RANDOM NUMBERS 3.5 Therefore let R and S be fixed. Consider the set T(alas . . . a,) defined for all binary numbers al as . . . a7 as the set of all 2 corresponding to (Xn), such that (X8,)2 has 2 r elements whose first r elements are respectively equal to al, us, . ..) a,. Our first result is that T(ula2,. . a,) has measure < 2-r. (32) To prove this, we start by observing that T(arus . . . a,) is a measurable set: Each element of T(ula2 . . . a,) is a real number z = (O.XoXr . . . )Z for which there exists an integer m such that algorithm S determines distinct values SO, sl, . . . , s,, and rule R determines a subsequence of X,,, X,,, . . . , XsW such that X,, is the rth element of this subsequence. The set of all real y = (O.YoY, . . . )s such that Y,, = X,, for 0 2 Ic 5 m also belongs to T(alus . . .a,), and this is a measurable set consisting of the finite union of dyadic subintervals Ibl...bt. Since there are only countably many such dyadic intervals, we see that T(ulus . . . a,) is a countable union of dyadic intervals, and it is therefore measurable. Furthermore, this argument can be extended to show that the measure of T(ul . . . ar-l 0) equals the measure of T(ur . . . ~~-1 l), since the latter is a union of dyadic intervals obtained from the former by requiring that Y,, = X,, for 0 5 Ic < m and Y,, # X,,. Now since T(al . , . u,.-~ 0) U T(UI . . . a7--1 1) 2 T(al . . . a,-r), the measure of T(UIU~ . . . a,) is at most one-half the measure of T(ul . . . a,-l). The inequality (32) follows by induction on T. Now that (32) has been established, the remainder of the proof is essentially to show that the binary representations of almost all real numbers are equi- distributed. The next few paragraphs constitute a rather long but not difficult proof of this fact, and they serve to provide probability estimates that are useful in many other problems. For 0 < E < 1, let B(r, E) be U T(ur . . . a,), where the union is taken over all binary numbers al . . . a, for which the number V(T) of zeros among al . . . a7 satisfies Iv(r) -$1 > 1 + U. The number of such binary numbers is C(T, e) = C (;) summed over the values of lc with (k - &rI 2 1 + ET. A suitable estimate for the tail of the binomial distribution can be obtained by the following standard trick: Let 2: and p be any positive numbers less than 1, let q = 1 -p, and let s = (p + 6)~. Then ; pkqr-kZs-k 5 0 By elementary calculus, the minimum value of ss(q + p/z> occurs when x = (p/(p + c))/(q/(q -E)), and this value of x yields c (r>p% * I ((–$) (&y. k 2 (TJ+E)~