Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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 E[X2]<∞\E[X^2]<\infty and a sub-σ-algebra G⊆F\mathcal G\subseteq\mathcal F (what you know, e.g. generated by an observation YY), the conditional expectation E[X∣G]\E[X\mid\mathcal G] is the orthogonal projection of XX onto the closed subspace of G\mathcal G-measurable variables in L2(P)L^2(P). It is characterized by E[(X−E[X∣G])Z]=0\E\big[(X-\E[X\mid\mathcal G])Z\big]=0 for every bounded G\mathcal G-measurable ZZ, and it is the best predictor of XX from that information in mean squared error. The tower rule E[E[X∣G]]=E[X]\E\big[\E[X\mid\mathcal G]\big]=\E[X] and the law of total variance follow:

Var⁡(X)=E[Var⁡(X∣Y)]+Var⁡(E[X∣Y]).\Var(X)=\E\big[\Var(X\mid Y)\big]+\Var\big(\E[X\mid Y]\big).

This is why regression with squared loss estimates the conditional mean E[Y∣X]\E[Y\mid X].

For a binary hypothesis HH and evidence E1,…,EkE_1,\dots,E_k that is conditionally independent given HH and given ¬H\neg H, Bayes' rule is cleanest in log-odds, where each piece of evidence adds its log-likelihood ratio:

log⁡P(H∣E1:k)P(¬H∣E1:k)=log⁡P(H)P(¬H)+∑j=1klog⁡P(Ej∣H)P(Ej∣¬H).\log\frac{P(H\mid E_{1:k})}{P(\neg H\mid E_{1:k})}=\log\frac{P(H)}{P(\neg H)}+\sum_{j=1}^k\log\frac{P(E_j\mid H)}{P(E_j\mid\neg H)}.

Under HH, the expected log-likelihood ratio of one observation is a KL divergence, DKL(PE∣H ∥ PE∣¬H)\KL\big(P_{E\mid H}\,\|\,P_{E\mid\neg H}\big). 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 X≥0X\ge0 and a>0a>0, P(X≥a)≤E[X]/aP(X\ge a)\le\E[X]/a, because a1{X≥a}≤Xa\mathbf 1\{X\ge a\}\le X. Chebyshev: apply Markov to (X−μ)2(X-\mu)^2, so P(∣X−μ∣≥t)≤Var⁡(X)/t2P(\abs{X-\mu}\ge t)\le\Var(X)/t^2. Chernoff: apply Markov to eλXe^{\lambda X} and optimize over λ>0\lambda>0,

P(X≥t)≤inf⁡λ>0e−λt E eλX.P(X\ge t)\le\inf_{\lambda>0}e^{-\lambda t}\,\E\,e^{\lambda X}.

For a sum of independent variables the moment generating function factorizes, so the tail decays exponentially in nn instead of like 1/n1/n.

DerivationProof sketch
  1. E eλY≤exp⁡(λ2(b−a)28)\E\,e^{\lambda Y}\le\exp\Big(\frac{\lambda^2(b-a)^2}{8}\Big)

    Hoeffding's lemma. If Y∈[a,b]Y\in[a,b] and EY=0\E Y=0, then for all λ∈R\lambda\in\R the bound below holds. Bound eλye^{\lambda y} by its chord through (a,eλa)(a,e^{\lambda a}) and (b,eλb)(b,e^{\lambda b}), take expectations, and check that the logarithm of the result, as a function of u=λ(b−a)u=\lambda(b-a), vanishes with its first derivative at u=0u=0 and has second derivative at most 14\tfrac14.

  2. P(Sn−ESn≥t)≤e−λt∏i=1nE eλ(Xi−EXi)≤exp⁡(−λt+λ28∑i=1n(bi−ai)2)P\big(S_n-\E S_n\ge t\big)\le e^{-\lambda t}\prod_{i=1}^n\E\,e^{\lambda(X_i-\E X_i)}\le\exp\Big(-\lambda t+\frac{\lambda^2}{8}\sum_{i=1}^n(b_i-a_i)^2\Big)

    Chernoff step. Apply Markov's inequality to eλ(Sn−ESn)e^{\lambda(S_n-\E S_n)} and use independence to factor the expectation:

  3. P(∣Xˉn−μ∣≥ε)≤2exp⁡(−2nε2(b−a)2)P\big(\abs{\bar X_n-\mu}\ge\varepsilon\big)\le2\exp\Big(-\frac{2n\varepsilon^2}{(b-a)^2}\Big)

    Optimize. The exponent is smallest at λ=4t/∑i(bi−ai)2\lambda=4t/\sum_i(b_i-a_i)^2, where it equals −2t2/∑i(bi−ai)2-2t^2/\sum_i(b_i-a_i)^2. For the mean, take t=nεt=n\varepsilon, and apply the result to −Xi-X_i for the lower tail:

A centered variable is σ\sigma-sub-Gaussian if EeλY≤eλ2σ2/2\E e^{\lambda Y}\le e^{\lambda^2\sigma^2/2} for all λ\lambda; Hoeffding's lemma says a bounded variable is sub-Gaussian with σ=(b−a)/2\sigma=(b-a)/2. Hoeffding ignores the variance, which is wasteful for rare events. Bernstein's inequality fixes that: if ∣Xi−μ∣≤M\abs{X_i-\mu}\le M and Var⁡(Xi)=σ2\Var(X_i)=\sigma^2, then P(Xˉn−μ≥ε)≤exp⁡(−nε2/(2σ2+2Mε/3))P(\bar X_n-\mu\ge\varepsilon)\le\exp\big(-n\varepsilon^2/(2\sigma^2+2M\varepsilon/3)\big). McDiarmid's inequality extends Hoeffding from sums to any function ff of independent inputs that changes by at most cic_i when input ii changes: P(f−Ef≥t)≤e−2t2/∑ici2P(f-\E f\ge t)\le e^{-2t^2/\sum_ic_i^2}.

Predict before you look

You estimate a classifier's error rate on nn fresh test examples (0/1 losses). By Hoeffding's inequality, how many examples guarantee an estimate within ±0.05\pm0.05 of the true error with probability at least 95%?

Show the answer

738 examples

Solve 2e−2nε2≤δ2e^{-2n\varepsilon^2}\le\delta: n≥ln⁡(2/δ)/(2ε2)=ln⁡40/(2⋅0.052)≈737.8n\ge\ln(2/\delta)/(2\varepsilon^2)=\ln40/(2\cdot0.05^2)\approx737.8, so n=738n=738. Chebyshev with the worst-case variance 14\tfrac14 needs 1/(4nε2)≤δ1/(4n\varepsilon^2)\le\delta, i.e. n≥2,000n\ge2{,}000. The gap widens as δ\delta shrinks: Hoeffding's nn grows like log⁡(1/δ)\log(1/\delta), Chebyshev's like 1/δ1/\delta.

Limit theorems and their rates

Asymptotic theory answers a different question. The weak law of large numbers says Xˉn→μ\bar X_n\to\mu 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 E∣X1∣<∞\E\abs{X_1}<\infty (Kolmogorov; Etemadi's 1981 proof needs only pairwise independence). The central limit theorem describes the fluctuations: if Var⁡(X1)=σ2∈(0,∞)\Var(X_1)=\sigma^2\in(0,\infty), then n(Xˉn−μ)/σ\sqrt n(\bar X_n-\mu)/\sigma converges in distribution to N(0,1)\mathcal N(0,1).

ResultStatement for the sample meanAssumptionsCharacter
ChebyshevP(∣Xˉn−μ∣≥ε)≤σ2/(nε2)P(\abs{\bar X_n-\mu}\ge\varepsilon)\le\sigma^2/(n\varepsilon^2)finite varianceholds at every nn; polynomial tail
Hoeffding≤2e−2nε2/(b−a)2\le2e^{-2n\varepsilon^2/(b-a)^2}independent, values in [a,b][a,b]holds at every nn; ignores the variance
Bernstein≤2e−nε2/(2σ2+2Mε/3)\le2e^{-n\varepsilon^2/(2\sigma^2+2M\varepsilon/3)}independent, ∣Xi−μ∣≤M\abs{X_i-\mu}\le Mholds at every nn; adapts to small variance
CLT≈2Φ(−n ε/σ)\approx2\Phi(-\sqrt n\,\varepsilon/\sigma)i.i.d., finite variancesharp shape, but only in the limit
Berry–EsseenCDF error ≤Cρ/(σ3n)\le C\rho/(\sigma^3\sqrt n)i.i.d., finite third momentquantifies the CLT, additively
Non-asymptotic bounds hold at the sample size you have; asymptotic results describe the shape of the fluctuations.

Uniform convergence: from one hypothesis to many

Hoeffding controls the test error of one hypothesis fixed in advance. Learning instead picks h^\hat h from a class H\mathcal H after seeing the training sample, and that selection biases its training error downward. The cure is a bound that holds for every h∈Hh\in\mathcal H at once. Write R(h)=E[ℓ(h;Z)]R(h)=\E[\ell(h;Z)] for the true risk and R^(h)=1n∑iℓ(h;Zi)\hat R(h)=\frac1n\sum_i\ell(h;Z_i) for the empirical risk on an i.i.d. sample Z1,…,ZnZ_1,\dots,Z_n.

DerivationProof
  1. P(∣R(h)−R^(h)∣>ε)≤2e−2nε2P\big(\abs{R(h)-\hat R(h)}>\varepsilon\big)\le2e^{-2n\varepsilon^2}

    For a fixed hh, R^(h)\hat R(h) is a mean of nn independent losses in [0,1][0,1] with mean R(h)R(h), so Hoeffding gives

  2. P(∃ h∈H: ∣R(h)−R^(h)∣>ε)≤2∣H∣ e−2nε2P\big(\exists\,h\in\mathcal H:\ \abs{R(h)-\hat R(h)}>\varepsilon\big)\le2\abs{\mathcal H}\,e^{-2n\varepsilon^2}

    The union bound P(⋃jAj)≤∑jP(Aj)P\big(\bigcup_jA_j\big)\le\sum_jP(A_j) needs no independence between the events:

  3. εn=ln⁡(2∣H∣/δ)2n\varepsilon_n=\sqrt{\frac{\ln(2\abs{\mathcal H}/\delta)}{2n}}

    Set the right-hand side equal to δ\delta and solve for ε\varepsilon:

  4. R(h^)≤R^(h^)+εn≤R^(h⋆)+εn≤R(h⋆)+2εnR(\hat h)\le\hat R(\hat h)+\varepsilon_n\le\hat R(h^\star)+\varepsilon_n\le R(h^\star)+2\varepsilon_n

    On this event, for h⋆∈arg min⁡hR(h)h^\star\in\argmin_hR(h), use the bound twice and the fact that h^\hat h minimizes R^\hat R:

Complexity enters only through ln⁡∣H∣\ln\abs{\mathcal H}. A class whose members can be described in kk bits has ∣H∣≤2k\abs{\mathcal H}\le2^k, so εn≈kln⁡2/(2n)\varepsilon_n\approx\sqrt{k\ln2/(2n)}: an Occam's-razor bound. Infinite classes need another measure of size. The VC dimension (Vapnik & Chervonenkis, 1971) or the Rademacher complexity replaces ln⁡∣H∣\ln\abs{\mathcal H}, 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.

Check your understanding

A finite class has ∣H∣=106\abs{\mathcal H}=10^6 hypotheses, and you have n=10,000n=10{,}000 i.i.d. examples. With δ=0.05\delta=0.05, about how large is the uniform deviation εn=ln⁡(2∣H∣/δ)/(2n)\varepsilon_n=\sqrt{\ln(2\abs{\mathcal H}/\delta)/(2n)}?

  1. 0.00030.0003
  2. 0.0030.003
  3. 0.030.03
  4. 0.30.3
Show the answer

C. 0.030.03

ln⁡(4×107)≈17.5\ln(4\times10^7)\approx17.5, so εn≈17.5/20,000≈0.030\varepsilon_n\approx\sqrt{17.5/20{,}000}\approx0.030. A million hypotheses cost little because ∣H∣\abs{\mathcal H} enters through its logarithm: multiplying the class size by 1,000 adds only ln⁡1000≈6.9\ln1000\approx6.9 under the square root, while halving εn\varepsilon_n takes four times the data.

Key takeaways

  • Conditional expectation E[X∣G]\E[X\mid\mathcal G] is the L2L^2 projection onto what you know, so squared-loss regression estimates E[Y∣X]\E[Y\mid X].
  • 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: P(∣Xˉn−μ∣≥ε)≤2e−2nε2/(b−a)2P(\abs{\bar X_n-\mu}\ge\varepsilon)\le2e^{-2n\varepsilon^2/(b-a)^2}, so n≈ln⁡(2/δ)/(2ε2)n\approx\ln(2/\delta)/(2\varepsilon^2) samples suffice.
  • The CLT describes the shape of fluctuations only as n→∞n\to\infty (Berry–Esseen error O(1/n)\order{1/\sqrt n}); non-asymptotic bounds hold at the nn you have.
  • Hoeffding plus the union bound gives uniform convergence over a finite class at rate ln⁡(∣H∣/δ)/n\sqrt{\ln(\abs{\mathcal H}/\delta)/n}, 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.

Question 1

Over all measurable functions ff, which predictor minimizes the expected squared error E[(Y−f(X))2]\E\big[(Y-f(X))^2\big]?

  1. f(X)=E[Y∣X]f(X)=\E[Y\mid X]
  2. The conditional median of YY given XX
  3. The conditional mode of YY given XX
  4. The best linear least-squares fit
Show the answer

A. f(X)=E[Y∣X]f(X)=\E[Y\mid X]

Conditional expectation is the L2L^2 projection onto functions of XX, so E[(Y−f(X))2]=E[(Y−E[Y∣X])2]+E[(E[Y∣X]−f(X))2]\E[(Y-f(X))^2]=\E[(Y-\E[Y\mid X])^2]+\E[(\E[Y\mid X]-f(X))^2], which is minimized by f=E[Y∣X]f=\E[Y\mid X].

Question 2

A nonnegative random variable has mean 2. What is the smallest upper bound on P(X≥10)P(X\ge10) that holds for every such distribution?

  1. 0.020.02
  2. e−5≈0.007e^{-5}\approx0.007
  3. 0.20.2
  4. No bound is possible without the variance
Show the answer

C. 0.20.2

Markov gives P(X≥10)≤EX/10=0.2P(X\ge10)\le\E X/10=0.2, and the two-point distribution with X=10X=10 with probability 0.20.2 and X=0X=0 otherwise attains it. Without further assumptions no smaller bound holds.

Question 3

At fixed accuracy ε\varepsilon, you want the failure probability of a Hoeffding guarantee to drop from δ=0.05\delta=0.05 to δ=0.0005\delta=0.0005. The required sample size...

  1. grows by a factor of about 100
  2. grows by a factor of about 2.2
  3. stays the same
  4. grows by a factor of 10
Show the answer

B. grows by a factor of about 2.2

n≥ln⁡(2/δ)/(2ε2)n\ge\ln(2/\delta)/(2\varepsilon^2) depends on δ\delta only through ln⁡(2/δ)\ln(2/\delta), and ln⁡4000/ln⁡40≈8.29/3.69≈2.25\ln4000/\ln40\approx8.29/3.69\approx2.25. Confidence is cheap; accuracy is expensive (n∝1/ε2n\propto1/\varepsilon^2).

Question 4

Why can't you bound the true risk of the empirical risk minimizer h^\hat h by applying Hoeffding's inequality to its training error?

  1. Because the losses are not bounded
  2. Because Hoeffding's inequality requires Gaussian data
  3. Because the training error of h^\hat h is always zero
  4. Because h^\hat h was chosen using the same sample, so its training losses are not an independent sample from a fixed hypothesis
Show the answer

D. Because h^\hat h 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 h^\hat h for its low training error biases that error downward, so you need a bound that holds uniformly over H\mathcal H: 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).