9.12 Fix > 0. Let An = {Ln < kn} for kn = (1 ) log2 n. Explain why An m n

9.12 Fix ε > 0. Let An = {Ln < kn} for kn = (1 − ε) log2 n. Explain why An ⊆

m

n i=1 Bc i , where mn = [n/kn] (integer part) and Bi = {X(i−1)kn+1 = ... = Xikn = 1} are independent events.

Deduce that P(An) ≤ P(Bc i )mn ≤ exp(−nε/(2 log2 n)), for all n large enough.