Content Bb 20813713 Homework Help - Q&A from Or X C learn-us-east-1-prod-fleet02-xythos.content.blackboardcdn.com/5cc71db6522fe/20813713?X-Blackboard-Expiration=1634245200000&X-Blackboard-Signature=ASF... To E 20813713 1 / 1 | - 100% + Show your calculations and explain your answers where needed. (1) 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]. 1 3) Use Chebyshev's inequality to prove a better upper bound on Pr[X, > 3n/4]. 4) Use Chebyshev's inequality to prove that Pr[|Xn - n/2| > vnlogn] = o(1) (that is, tends to 0 as n - co). 5) If Yt 2 1 what can you say about In? 6) If Yt = 0 what can you say about In? 7) Compute EYt 3) Use Markov's inequality to prove that if e > 0 is fixed then Pr[T, 2 (1+E) log2 n] = o( 1 ) . 9) (Extra credit) Can you show that if E > 0 is fixed then Pr[Tn 2 (1 - () log2 n] = 1 - o(1)? Hint: count only a subset of runs of length t and use Chebyshev