4.6 Deviation: Markov & Chebyshev Bounds

Flipping Coins


Suppose you flip a fair coin 100 times. The coin flips are all mutually independent.

  1. What is the expected number of heads?

    Let \(X\) denote the number of heads. Let \(X_i\) be the indicator variable that is 1 when the \(i^{th}\) coin flip is heads. Then \[ X = X_1+X_2+\ldots +X_{100}.\] Hence, by linearity of expectation, \[E[X] = E[X_1+X_2+\ldots+X_{100}] = E[X_1]+\ldots+E[X_{100}]\] and we need to find the expectation of each individual indicator. We compute: \[E[X_i]= 1 \cdot \Pr[\text{flip head}] + 0 \cdot \Pr[\text{flip tail}] = \frac{1}{2}.\] Putting everything together, we conclude that \(E[X] = 100 \cdot \frac{1}{2} = 50\).

  2. What is an upper bound on the probability that the number of heads is at least 70 according to Markov's Theorem? Please answer as a fraction in the form x/y.

    The expected number of heads is 50. So the probability that the number of heads is at least 70 is at most \(\frac{50}{70} = \frac{5}{7}\).

  3. What is the variance of the number of heads?

    Let \(X\) and \(X_i\) be as in Question 1. Then, by the independence of the \(X_i\), we know \[Var[X] = Var[X_1 +\ldots+ X_{100}] = Var[X_1]+ \ldots + Var[X_{100}]\] and we need to find the variance of each indicator. We compute: \[Var[X_i] = E[X^2] - E[X]^2 =\frac{1}{2} - \left(\frac{1}{2}\right)^2 = \frac{1}{4}.\] Putting everything together, we have \( Var[X] = 100\cdot \frac{1}{4} = 25 \).

  4. What is an upper bound on the probability that the number of heads is less than 30 or greater than 70 according to Chebyshev's Theorem? Please answer as a fraction in the form x/y.

    The mean is 50. So, the variable is less than 30 and more than 70 iff it deviates from its mean by \(20=|30-50|=|70-50|\) or more. How big is this deviation in comparison to the standard deviation? Since the variance of the number of heads is 25, its standard deviation is 5. So, deviation by 20 is 4 times the standard one.

    Now, Chebyshev's Theorem says that the probability of the number of heads deviating from its mean by 4 times the standard deviation is \(\leq \frac{1}{4^2} = \frac{1}{16}\).