158 RANDOM NUMBERS 3.5 Strictly speaking, this is (Web site templates)
158 RANDOM NUMBERS 3.5 Strictly speaking, this is not an algorithm, since it doesn t terminate; it would of course be easy to modify the procedure to stop when n reaches a given value. The reader will find it easier to grasp the idea of the construction by trying it out manually, replacing the number 3 .4 -l of step W4 by 27 during this experiment. Algorithm W is not meant to be a practical source of random numbers. It is intended to serve only a theoretical purpose: Theorem W. Let (Un) be the sequence of rational numbers defined by Algorithm W, and let Ic be a positive integer. If the subsequence (Un)Rk is infinite, it is l-distributed. Proof. Let A[al, . . . , a,] denote the (possibly empty) subsequence of (Un) con- taining precisely those elements U, that, for all j < T, belong to subsequence (Un)Rj if aj = 1 and d o not belong to subsequence (Un)Rj if aj = 0. It suffices to prove, for all r 2 1 and all pairs of binary numbers al . . . a,. and bl. . . b,, that Pr(U, E Ib1…6,) = 2- with respect to the subsequence 4~1,. . . , a,], whenever the latter is infinite. (See Eq. (30).) For if r 2 k, the infinite sequence (U,)Rk is the finite union of the disjoint subsequences -+I,. . . , a,] for ak = 1 and aj = 0 or 1 for 1 5 j 5 T, j # Ic; and it follows that Pr(U, E lbl…t+) = 2- with respect to (Un)Rk. (See exercise 33.) This is enough to show that the sequence is l-distributed, by Theorem A. Let B[al, . . . , a,] denote the subsequence of (Un) that consists of the values for those n in which C[al,. . . , a,] is increased by one in step W6 of the algo- rithm. By the algorithm, B[al, . . . , a,] is a finite sequence with at most 3.4 -l elements. All but a finite number of the members of A[al, . . . , a,] come from the subsequences B[al, . . . , a,, . . . , at], where aj = 0 or 1 for r < j 5 t. Now assume that A[al, . . . ,ar] is infinite, and let A[al,. . . ,a,] = (Us,), where SO < s1 < s2 5 … . If N is a large integer, with 4r 5 44 < N 5 44+ , it follows that the number of values of k < N for which Us, is in Ibl,..*, is (except for finitely many elements at the beginning of the subsequence) v(N) = v(N1) +. . . + v(N,). Here m is the number of subsequences B[al, . . . , at] listed above in which Us, appears for some k < N; Nj is the number of values of k with Us, in the corresponding subsequence; and v(Nj) is the number of such values that are also in 4, ,,,t,, . Therefore by Lemma T, Iv(N) -2-?NI = lv(Nl) -2- N1 +. . . + v(N,) -2- lv,l 2 Iv(Nl) -2- N1I + . . . + Iv(Nm) -2-7N,I