Markov's inequality: Let X be a non-negative random variable. Then, for every constant 6 > 0, X be a non-negative random variable. Then, for every constant 6 > 0, 1 Pr(X 1300 2 65.00) S m This means that if you introduce a large enough 6, then probability that the actual value of X exceeds 5500 can be quite small. In the following problem, we'll see some strengths and weaknesses of the inequality. Problem 1: x = Z X,- 1. Assume i where each X,- is an indicator random variable taking values in {0: 1} as needed to indicate \"heads\" or \"tails.\" We'll see whether changing the number of ips matters. 2. Suppose that you have an unfair coin that returns \"Heads\" with probability \"A and \"Tails\" with probability 'A. What is the expected number of heads that you see in 12 ips? 3. Suppose you ip the coin 50 times. Use Markov's inequality to determine an upper bound on the probability that you see \"Tails\" more than 25 times. You'll need to gure out what 6 gives you this probability. 4. For what value of 6 does Markov's inequality give the smallest bound? What is the bound it gives for tails with n ips? When is this bound actually "good?\" (Hint: \"Good\" means that it gives you something that looks like the actual probability. You want to ask for what value of n this looks right.) So Markov's inequality allows us to not worry that much about the nuances of our probability distributions, but applying it naively can sometimes yield unnecessarily weak inequalities. The reason is that Markov's inequality includes the possibility that the outcomes of each Xi depend on some other outcome Xi. (Consider the case that X1 is a coin ip and X i>1 is just the same as whatever X1 is.) To deal with this, computer scientists often use an inequality called a Chernoff bound. The Chernoff bound is derived from Markov's inequality, but requires the additional assumption that you have a sequence of independent events {X12 X2: - - - . Xn} where each Xi E {021}. Chemoff bound: Suppose X1: X2. - - - 1 X N are independent random variables taking values X = 2X, in {0: 1}, and let i . Then, for any 5 E (0. 1],X11X21 - - - :XN are independent random variables taking values in {0: 1}. Then, for any 6 E (01 1], 593 x Pr(|X E(X)| 2 6300) s 2e