Flip a fair coin n times. Let Xn be the number of heads. Let Tn be the longest 'run' of consecutive heads. That is, if n = 8 and the sequence of flips is

THTHHHHT then Tn = 4. Let Yt be the number of runs of t consecutive heads. In the example we have Y3 = 2 since a run of length 3 starts at flip 4 and at flip 5.

1) Calculate EXn and var(Xn).

2) Use Markov's inequality to prove an upper bound on Pr[Xn > 3n/4].

3) Use Chebyshev's inequality to prove a better upper bound on Pr[Xn > 3n/4].

4) Use Chebyshev's inequality to prove that Pr[|Xn n/2| > n log n] = o(1) (that is, tends to 0 as n ).

5) If Yt 1 what can you say about Tn?

6) If Yt = 0 what can you say about Tn?

7) Compute EYt .

8) Use Markov's inequality to prove that if > 0 is fixed then Pr[Tn (1+) log2 n] = o(1).

9) (Extra credit) Can you show that if > 0 is fixed then Pr[Tn (1 ) log2 n] = 1 o(1)? Hint: count only a subset of runs of length t and use Chebyshev.