Concentration inequalities

Markov's inequality

For $X\geq0$ and $a>0$:

$$ P(X\geq a) \leq \frac{\mathbb{E}[X]}{a}. $$

Proof, in one line: since $X\geq0$,

$$ \mathbb{E}[X] \ \geq\ \mathbb{E}\big[X\cdot\mathbb{1}[X\geq a]\big] \ \geq\ \mathbb{E}\big[a\cdot\mathbb{1}[X\geq a]\big] = a\,P(X\geq a). $$

Divide by $a$.

Intuition: a non-negative variable can't put much mass far out past $a$ without dragging its own average up past where it actually sits; this needs only non-negativity and a mean, nothing else.

Chebyshev's inequality

Apply Markov to the non-negative variable $(X-\mu)^2$, with threshold $k^2$, for $X$ with mean $\mu$ and variance $\sigma^2$:

$$ P\big((X-\mu)^2\geq k^2\big) \leq \frac{\mathbb{E}[(X-\mu)^2]}{k^2} = \frac{\sigma^2}{k^2}. $$

$(X-\mu)^2\geq k^2 \iff |X-\mu|\geq k$ for $k>0$, so:

$$ P(|X-\mu|\geq k) \leq \frac{\sigma^2}{k^2}. $$

Take $X=\bar x_n=\tfrac1n\sum_ix_i$, the mean of $n$ i.i.d. copies of a variable with variance $\sigma^2$. Independence lets variance distribute over the sum, and $\operatorname{Var}(cY)=c^2\operatorname{Var}(Y)$ handles the $\tfrac1n$:

$$ \operatorname{Var}(\bar x_n) = \frac{1}{n^2}\sum_{i=1}^n\operatorname{Var}(x_i) = \frac{n\sigma^2}{n^2} = \frac{\sigma^2}{n}. $$

Plugging this into Chebyshev's inequality above gives $P(|\bar x_n-\mu|\geq k)\leq\sigma^2/(nk^2)\to0$ for every fixed $k$: this is exactly the mechanism behind the law of large numbers (Law of large numbers and the central limit theorem).

Intuition: knowing the variance, not just the mean, lets the same one-line Markov argument say something about spread on both sides of $\mu$, not just about staying below one far-off threshold.

Chernoff bound

Apply Markov to $e^{tX}$, non-negative for any real $t$, then optimize over $t>0$:

$$ P(X\geq a) = P\big(e^{tX}\geq e^{ta}\big) \leq \frac{\mathbb{E}[e^{tX}]}{e^{ta}} = e^{-ta}\,M_X(t), \qquad M_X(t):=\mathbb{E}[e^{tX}] \ \text{(moment generating function)}. $$

Minimizing the right side over $t>0$ gives the tightest bound this route can produce. Because $M_X(t)$ encodes every moment of $X$, not just the first two, the resulting bound decays exponentially in the deviation, not polynomially like Chebyshev's $1/k^2$.

Intuition: each inequality so far is the same one-line Markov argument, applied to a cleverer non-negative function of $X$; using more of the distribution's structure (here, its entire moment generating function) buys a sharper tail.

Hoeffding's inequality

Specialize the Chernoff bound to a sum of independent, bounded variables, $x_i\in[a_i,b_i]$, which is exactly the sample-mean setting:

$$ P\big(|\bar x_n-\mu|\geq t\big) \ \leq\ 2\exp\!\left(-\frac{2n^2t^2}{\sum_i(b_i-a_i)^2}\right). $$

For i.i.d. $x_i\in[a,b]$, this reads $P(|\bar x_n-\mu|\geq t)\leq2\exp\!\big(-2nt^2/(b-a)^2\big)$: exponential in $n$, where Chebyshev applied to the same quantity only gives polynomial decay, $O(\sigma^2/(nt^2))$.

Intuition: boundedness is a strong assumption, and it is repaid with the strongest bound in this post, decaying exponentially fast in the sample size rather than just inversely in it.

The pattern

$$ \underbrace{\text{Markov}}_{X\geq0,\ \mathbb{E}[X]}: \ O\!\left(\frac1a\right) \quad\Rightarrow\quad \underbrace{\text{Chebyshev}}_{+\ \operatorname{Var}(X)}: \ O\!\left(\frac1{k^2}\right) \quad\Rightarrow\quad \underbrace{\text{Hoeffding}}_{+\ \text{bounded, independent}}: \ O\!\left(e^{-cnt^2}\right). $$

Each bound is the same Markov argument in disguise, applied to a more informative non-negative function of $X$; each extra assumption buys a strictly sharper tail. This is also why concentration bounds, not just the limit statements of the law of large numbers, are the tool used for finite-sample guarantees: confidence intervals, A/B tests, and generalization bounds in learning theory all ultimately quote a bound of this shape.