II · Probability & randomness
Concentration inequalities
What it is
Chernoff, Hoeffding, Chebyshev — bounds on how far an empirical sum strays from its expectation.
Where it lives
A/B test sample sizes, why "law of large numbers" actually converges, randomised algorithms' bounds.
The key insight
For n samples of a [0,1] variable: P(|mean − μ| > ε) ≤ 2 exp(−2nε²). The 2× factor comes from a two-sided bound.