Web host - 560 ANSWERS TO EXERCISES 3.5 Fig. A-5. Directed
560 ANSWERS TO EXERCISES 3.5 Fig. A-5. Directed graph for the construction in exercise 30. the cyclic path are numbered from 1 to 32, and the cyclic sequence is (00001000110010101001101110111110)(00001.. .). Note that Pr(Xz, = 0) = fi in th is sequence. The sequence is clearly (2lc)-distributed, since each (2/c)-tuple 2122.. . Z2k occurs 1 + f(zl,. . . ,zz~) + 1 - f(zl,. . . ,zz~) = 2 times in the cycle. The fact that Pr(X2, = 0) has the desired value comes from the fact that the maximum value on the right-hand side in the proof of the preceding exercise has been achieved by this construction. 31. Use Algorithm W with rule RI selecting the entire sequence. [For a generalization of this type of nonrandom behavior in R5-sequences, see Jean Ville, l&de Critique de Is notion de Collectif (Paris, 1939), 55-62. Perhaps R6 is also too weak, from this standpoint.] 32. If R, R are computable subsequence rules, so is R = RR defined by the following functions: fc(zo, . . . , ~~-1) = 1 iff R defines the subsequence x71, . . . , zTk of 20, . . . , ~~-1, where k 2 0 and 0 5 rl < . . . < rk < n and &(z~~, . . . , s7,) = 1. Now (Xn)R R is ((Xn)R)R . The result follows immediately. 33. Given E > 0, find NO such that N > NO implies that both Iv,(N)/N -pi < E and Iv,(N)/N--pi < E. Then find Nl such that N > Nl implies that tN is TM or S,U for some M > NO. Now N > Nl implies that 34. For example, if the binary representation of t is (1 Obh2 10 1 1 Oa2 1 . . . 1 Oak)z, where Oa stands for a sequence of a consecutive zeros, let the rule Rt accept U, if and only if [bU,+kj = al, . . . , [bU,-,J = ak. 35. Let a0 = SO and am+1 = max{ Sk 1 0 2 k < 2am }. Construct a subsequence rule that selects element X, if and only if n = Sk for some Ic < 2am, when n is in the range am 5 n < a,+l. Then limm+oo v(a,)/a, = 4.