Markov's Inequality

Markov's inequality gives you a tail bound using nothing but the mean. If $X \geq 0$ and $a > 0$: $$P(X \geq a) \leq \frac{E[X]}{a}$$ Intuition: Think of it as a "fairness" argument. If the average income in a room is \$50k, then at most half the people can earn \$100k or more — otherwise the average would be pulled above \$50k. More generally, the fraction of people earning $\geq a$ can't exceed (mean)$/a$. Proof (one line): $E[X] = \sum_{x} x \cdot P(X=x) \geq \sum_{x \geq a} x \cdot P(X=x) \geq a \cdot P(X \geq a)$. Concrete example: A factory produces widgets with mean weight 10g. What fraction can weigh $\geq 50$g? By Markov: $P(X \geq 50) \leq$$\frac{10}{50}$ = 0.2. At most 20%. When to use: When you only know $E[X]$ and need a quick upper bound on $P(X \geq a)$. It's crude — but it's the weakest assumption you can make, so it's always valid. In interviews, Markov is often the first step before tightening to Chebyshev. Alternative approach: If you also know the variance, Chebyshev's inequality gives a tighter bound. Markov is the foundation that Chebyshev is built on.