Bernstein's Inequality

If you flip a fair coin a thousand times, common sense says the number of heads should land close to 500 — Bernstein's inequality is one of the tools that makes "close to" mathematically precise, and does a better job of it than a cruder bound like Chebyshev's inequality when the individual variables are well-behaved (bounded and not too spread out).

For independent, mean-zero random variables $X_1, \dots, X_n$, each bounded by $|X_i| \le M$, and with total variance $\sigma^2 = \sum_i \mathrm{Var}(X_i)$, Bernstein's inequality bounds the chance the sum strays past a threshold $t$:

$$P\left(\sum_{i=1}^n X_i > t\right) \le \exp\left(-\frac{t^2/2}{\sigma^2 + Mt/3}\right).$$

In plain English: for small deviations $t$ relative to $\sigma^2$, the bound behaves like a Gaussian tail (decaying as $e^{-t^2}$), but as $t$ grows large the $Mt/3$ term takes over and the decay softens to $e^{-t}$ — a compromise between the fast Gaussian-like decay you'd hope for and the slower decay that a single large, bounded term can actually produce.

For 1,000 independent $1-or-$0 bets with a 50% edge each ($\sigma^2 = 250$, $M=1$), the inequality bounds the probability the total sum exceeds its mean by more than 100: plugging in $t=100$ gives an exponent of roughly $-10000/2 / (250 + 33) \approx -35.3$, an astronomically small probability — confirming that large deviations from a well-diversified sum of small, bounded bets are genuinely rare.