Concentration Inequalities
Concentration inequalities provide probabilistic bounds on how far a random variable is likely to be from some central value without requiring full knowledge of the distribution:
The Markov inequality provides a bound on the probability that a nonnegative random variable takes a value significantly larger than its mean. Let and . Then for any ,
The Chebyshev inequality strengthens this by incorporating variance, yielding a bound on the probability that a random variable deviates from its mean from above or below by more than a specified amount. For any with and , it follows that
By applying Markov’s Inequality to the nonnegative random variable , Chebyshev’s bound follows immediately.
Finally, the Chernoff bound provides an exponentially decreasing bound on the tail probabilities of a random variable using its moment generating function. For any with , and for any , it directly follows from the Markov inequality that
Intuition
The proof for Markov’s Inequality is derived directly from the definition of expectation:
\mathbb{E}[X] &= \sum^{}_{x \in \mathcal{X}}x \cdot \mathbb{P}(X=x) \\ &\ge \sum^{}_{x \ge c}x \cdot \mathbb{P}(X=x) \\ &\ge \sum^{}_{x \ge c}c \cdot \mathbb{P}(X = x) \\ &= c \sum^{}_{x \ge c} \mathbb{P}(X = x) \\ &= c \cdot \mathbb{P}(X \ge c), \end{align}$$ where the second line follows from the fact that $X$ is nonnegative. As previously mentioned, Chebyshev's Inequality is a direct consequence of centering $X$ around its mean. Define $Y=(X-\mathbb{E}[X])^2$. Then, $$\begin{align} P((X-E[X])^2 \ge c^2)&=P(| X-E[X] | \ge c) \\ &\ge \frac{\mathbb{E}[(X-\mathbb{E}[X])^2]}{c^2} = \frac{\operatorname{Var}(X)}{c^2}. \end{align}$$ We now derive the Chernoff bound by making use of MGFs: # Examples >[!example] >