• Overview
• Details
• Exercises

Concentration inequalities quantify how a random variable deviates from its expectation. They underlie probabilistic analyses in algorithms, learning theory, randomized constructions, and tail-risk control. Classic results include Markov/Chebyshev, Chernoff/Hoeffding, Bernstein/Bennett, Azuma–Hoeffding (martingales), and McDiarmid’s bounded difference inequality.

• Moment and mgf methods: Markov and Chebyshev as baselines; mgf and Chernoff’s technique for sums of independent RVs.
• Hoeffding/Chernoff bounds: Sub-Gaussian tails for bounded/0-1 variables; multiplicative and additive forms.
• Bernstein/Bennett: Variance-sensitive bounds; tighter than Hoeffding when variance is small.
• Sub-Gaussian/Sub-exponential: Orlicz norms, tail behavior, and closure under sums.
• Martingale inequalities: Azuma–Hoeffding for bounded differences; Freedman for variance-adaptivity.
• McDiarmid’s inequality: Bounded differences for functions of independent variables.
• Applications: Coupon collector tails (sketch), randomized algorithms error control, generalization guarantees in learning (VC/Rademacher overview).

1. Use Chernoff bounds to show that the sum of n independent Bernoulli(p) deviates from its mean by more than εnp with probability at most 2exp(-Ω(ε^2 np)). State constants.
2. Apply Hoeffding’s inequality to bound the deviation of the sample mean of bounded variables in [0,1].
3. Prove McDiarmid’s inequality for a Lipschitz function f(X_1,...,X_n) with bounded differences c_i, and apply it to a simple empirical risk function.