4.6 Deviation: Markov & Chebyshev Bounds

Implications of Expectation

Suppose \(X\) is a nonnegative integer random variable for which \(E[X]\)=5. You know nothing else about \(X\).

Complete the following statements so that they are guaranteed to be true.

  1. The probability that \(X=5\) is
    Exercise 1
    Two cases disprove all the others: \(X\) is always 5 or \(X\) is 0 or 10 with equal likelihood.

  2. With positive probability, \(X\) is
    Exercise 2
    If \(X\) were always >5, then we would have \(E[X] >\)5. So, it must be at most 5 with positive probability.

    The rest of the options (except equal to 5) are disproved by the following counterexample: Let \(X\) be the constant random variable equal to 5. Then \(E[X]\)=5, and the other statements are obviously false. Equal to 5 is disproved by the random variable that takes values 0 or 10, each with probability \(\frac{1}{2}\).


  3. \(E[X^2]\)
    Exercise 3
    \(X\) could be 20 with probability \(\frac{1}{4}\) and 0 with probability \(\frac{3}{4}\). Then its expectation would be 5, but the expectation of its square would be \(100=\frac{3}{4}\cdot 0^2 + \frac{1}{4}\cdot 20^2\). In fact, by setting \(X\) to be very large with low probability, we can make its expectation arbitrarily large. We can rule out all the other answers:
    • \(X\) could be 0 with probability \(\frac{1}{2}\) and 10 with probability \(\frac{1}{2}\). Then the expectation of \(X^2\) would be 50. So, the 1st, the third, and the fourth answers are wrong.
    • \(X\) could be 5 with probability 1. Then the expectation of \(X^2\) would be 25. So the second answer is wrong.
    • \(E[X^2]\) is at least \(E[X^2]\), since \(Var[X]=E[X^2]-E[X]^2\) and Variance is nonnegative, so we know it is not 0.

  4. The probability \(\Pr[X \geq 1000]\) is
    Exercise 4
    A direct application of Markov's Theorem. Since \(X\) is a nonnegative variable, we know that \[\Pr [X \geq a] \leq \frac{E[X]}{a}\] for any \(a\). In this case, we have \[\Pr [X \geq 1000] \leq \frac{5}{1000} = \frac{1}{200}\] On the other hand, \(X\) could be 1000 with probability \(\frac{1}{200}\) and 0 otherwise, in which case the smaller bounds would not hold. Of course if \(X\) is always 5, this probability is 0, so it's not necessarily positive.