[23] Let x1x2 ...xn be a random sequence with C(x|n) ≥ n.

(a) Use a Martin-L¨of test to show that x10x20 ... 0xn is not random with respect to the uniform distribution.

(b) Use a Martin-L¨of test to show that the ternary sequence y1y2 ...yn with y1 = xn + x1 and yi = xi−1 + xi for 1 < i ≤ n is not random with respect to the uniform distribution.

Comments. Hint: In Item

(b) in the y-string the blocks 02 and 20 do not occur. Extend the definition of random sequences from binary to ternary. Source: [R. von Mises, Probability, Statistics and Truth, Dover, 1981].