Probability Essentials
Random variables, Bayes’ rule, expectations and concentration.
Everyone knows that the average of a thousand coin flips lands near one half. Concentration inequalities say how near, with what probability, at the sample size you actually have, and assuming little more than boundedness. They are the quiet engine behind test-set error bars, A/B tests, bandit algorithms and generalization bounds.
What you’ll learn
- Define probability spaces, random variables and conditional expectation precisely, and use Bayes' rule in log-odds form.
- Derive the Markov, Chebyshev and Chernoff bounds, and prove Hoeffding's inequality via Hoeffding's lemma.
- Contrast non-asymptotic tail bounds with the laws of large numbers, the central limit theorem and the Berry–Esseen rate.
- Combine Hoeffding's inequality with the union bound into a uniform generalization bound for finite hypothesis classes.
Probability spaces and conditioning, precisely
Conditioning on information is a projection. For and a sub-σ-algebra (what you know, e.g. generated by an observation ), the conditional expectation is the orthogonal projection of onto the closed subspace of -measurable variables in . It is characterized by for every bounded -measurable , and it is the best predictor of from that information in mean squared error. The tower rule and the law of total variance follow:
This is why regression with squared loss estimates the conditional mean .
For a binary hypothesis and evidence that is conditionally independent given and given , Bayes' rule is cleanest in log-odds, where each piece of evidence adds its log-likelihood ratio:
Under , the expected log-likelihood ratio of one observation is a KL divergence, . KL is the rate at which evidence accumulates, a fact that Wald's sequential test and the Chernoff–Stein lemma make precise.
Tail bounds: from Markov to Hoeffding
Three moves produce every classical tail bound. Markov: for and , , because . Chebyshev: apply Markov to , so . Chernoff: apply Markov to and optimize over ,
For a sum of independent variables the moment generating function factorizes, so the tail decays exponentially in instead of like .
Hoeffding's lemma. If and , then for all the bound below holds. Bound by its chord through and , take expectations, and check that the logarithm of the result, as a function of , vanishes with its first derivative at and has second derivative at most .
Chernoff step. Apply Markov's inequality to and use independence to factor the expectation:
Optimize. The exponent is smallest at , where it equals . For the mean, take , and apply the result to for the lower tail:
A centered variable is -sub-Gaussian if for all ; Hoeffding's lemma says a bounded variable is sub-Gaussian with . Hoeffding ignores the variance, which is wasteful for rare events. Bernstein's inequality fixes that: if and , then . McDiarmid's inequality extends Hoeffding from sums to any function of independent inputs that changes by at most when input changes: .
You estimate a classifier's error rate on fresh test examples (0/1 losses). By Hoeffding's inequality, how many examples guarantee an estimate within of the true error with probability at least 95%?
Show the answer
738 examples
Solve : , so . Chebyshev with the worst-case variance needs , i.e. . The gap widens as shrinks: Hoeffding's grows like , Chebyshev's like .
Limit theorems and their rates
Asymptotic theory answers a different question. The weak law of large numbers says in probability for i.i.d. variables with finite mean; with finite variance it is one line of Chebyshev. The strong law upgrades this to almost-sure convergence, and for i.i.d. sequences it holds if and only if (Kolmogorov; Etemadi's 1981 proof needs only pairwise independence). The central limit theorem describes the fluctuations: if , then converges in distribution to .
| Result | Statement for the sample mean | Assumptions | Character |
|---|---|---|---|
| Chebyshev | finite variance | holds at every ; polynomial tail | |
| Hoeffding | independent, values in | holds at every ; ignores the variance | |
| Bernstein | independent, | holds at every ; adapts to small variance | |
| CLT | i.i.d., finite variance | sharp shape, but only in the limit | |
| Berry–Esseen | CDF error | i.i.d., finite third moment | quantifies the CLT, additively |
Uniform convergence: from one hypothesis to many
Hoeffding controls the test error of one hypothesis fixed in advance. Learning instead picks from a class after seeing the training sample, and that selection biases its training error downward. The cure is a bound that holds for every at once. Write for the true risk and for the empirical risk on an i.i.d. sample .
For a fixed , is a mean of independent losses in with mean , so Hoeffding gives
The union bound needs no independence between the events:
Set the right-hand side equal to and solve for :
On this event, for , use the bound twice and the fact that minimizes :
Complexity enters only through . A class whose members can be described in bits has , so : an Occam's-razor bound. Infinite classes need another measure of size. The VC dimension (Vapnik & Chervonenkis, 1971) or the Rademacher complexity replaces , and PAC learning (Valiant, 1984) asks when such bounds make learning possible from polynomially many samples, as the Deep Layer lesson PAC Learning & VC Dimension develops.
A finite class has hypotheses, and you have i.i.d. examples. With , about how large is the uniform deviation ?
Show the answer
C.
, so . A million hypotheses cost little because enters through its logarithm: multiplying the class size by 1,000 adds only under the square root, while halving takes four times the data.
Key takeaways
- Conditional expectation is the projection onto what you know, so squared-loss regression estimates .
- With conditionally independent evidence, Bayes' rule adds log-likelihood ratios to the prior log-odds; the expected log-likelihood ratio is a KL divergence.
- Markov, then Chebyshev, then Chernoff: bounding the moment generating function gives exponential tails. Hoeffding: , so samples suffice.
- The CLT describes the shape of fluctuations only as (Berry–Esseen error ); non-asymptotic bounds hold at the you have.
- Hoeffding plus the union bound gives uniform convergence over a finite class at rate , and empirical risk minimization lands within twice that of the best hypothesis.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Over all measurable functions , which predictor minimizes the expected squared error ?
- The conditional median of given
- The conditional mode of given
- The best linear least-squares fit
Show the answer
A.
Conditional expectation is the projection onto functions of , so , which is minimized by .
A nonnegative random variable has mean 2. What is the smallest upper bound on that holds for every such distribution?
- No bound is possible without the variance
Show the answer
C.
Markov gives , and the two-point distribution with with probability and otherwise attains it. Without further assumptions no smaller bound holds.
At fixed accuracy , you want the failure probability of a Hoeffding guarantee to drop from to . The required sample size...
- grows by a factor of about 100
- grows by a factor of about 2.2
- stays the same
- grows by a factor of 10
Show the answer
B. grows by a factor of about 2.2
depends on only through , and . Confidence is cheap; accuracy is expensive ().
Why can't you bound the true risk of the empirical risk minimizer by applying Hoeffding's inequality to its training error?
- Because the losses are not bounded
- Because Hoeffding's inequality requires Gaussian data
- Because the training error of is always zero
- Because was chosen using the same sample, so its training losses are not an independent sample from a fixed hypothesis
Show the answer
D. Because was chosen using the same sample, so its training losses are not an independent sample from a fixed hypothesis
Hoeffding applies to a hypothesis fixed before the data are drawn. Choosing for its low training error biases that error downward, so you need a bound that holds uniformly over : the union bound for finite classes, VC or Rademacher arguments for infinite ones.
Further reading
- W. Hoeffding, "Probability inequalities for sums of bounded random variables," Journal of the American Statistical Association 58 (1963), 13–30.
- S. Boucheron, G. Lugosi & P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence (Oxford University Press, 2013).
- R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science (Cambridge University Press, 2018).
- S. Shalev-Shwartz & S. Ben-David, Understanding Machine Learning: From Theory to Algorithms (Cambridge University Press, 2014), chapters 2–4.
- C. Zhang, S. Bengio, M. Hardt, B. Recht & O. Vinyals, "Understanding deep learning requires rethinking generalization," ICLR (2017).