Markov's Inequality

Probability · Axiom Academy

Fundamental bound on tail probabilities using only the mean of a non-negative random variable 1. Statement of Markov's Inequality For a non-negative random variable X (i.e., X ≥ 0 almost surely) and any constant a > 0: Intuitively: if the average is small, then X cannot be large too often. The bound gets tighter as a increases. 2. Proof of Markov's Inequality The proof uses a simple but clever idea: bound X from below by the indicator function I X ≥ a : Since X ≥ 0, we have X ≥ a·I X ≥ a (equals a when X ≥ a, equals 0 otherwise). Taking expectations of both sides and using E[I X ≥ a ] = P(X ≥ a) completes the proof. Suppose X represents the number of customers arriving at a store in one hour, with E[X] = 10. What can we say about P(X ≥ 50)? Markov's inequality tells us P(X ≥ 50) ≤ 10/50 = 0.2. So at most 20% of the time will we see 50 or more customers, given an average of 10. The actual probability might be much smaller, but we're guaranteed it's at most 20%. 4. Applications and Extensions Markov's inequality serves as the basis for stronger results: By applying Markov to different transformations of X, we obtain increasingly powerful concentration results. 5. Limitations and When It's Tight Markov's inequality can be quite loose. It becomes tight (achieves equality) for specific distributions:

This is the written version of the interactive lesson above. See the full Probability course.