Probability, Expectation, and Concentration Bounds

Purpose

A reference for concentration arguments, so they do not have to be re-derived ad hoc. It fixes definitions for expectation, variance, covariance, and conditional expectation, then builds the inequality chain Markov, Chebyshev, Chernoff, Hoeffding, each one a strictly stronger use of information about the random variable. The payoff is quantitative: how many samples you need before an empirical average can be trusted, which is the question underneath A/B tests, offline recommender metrics, and benchmark noise.

Random variables and expectation

A random variable $X$ is a function from outcomes to numbers; we describe it by its distribution. Expectation is the probability-weighted average (Pishro-Nik ch. 6):

The single most used fact is linearity: $\mathbb{E}[aX+bY]=a\mathbb{E}[X]+b\mathbb{E}[Y]$ with no independence assumption. Independence is only needed for products: if $X\perp Y$ then $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$.

Variance measures spread, covariance measures co-movement:

Variance is not linear: $\mathrm{Var}(aX)=a^2\mathrm{Var}(X)$, and $\mathrm{Var}(X+Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)+2\mathrm{Cov}(X,Y)$, which collapses to a plain sum for independent (or merely uncorrelated) variables. That collapse is the reason averaging works: for iid $X_1,\dots ,X_n$ with mean $\mu$ and variance ${\sigma }^2$, the empirical mean ${\hat{\mu }}_n=\frac{1}{n}{\sum }_i{X}_i$ has

Conditional expectation $\mathbb{E}[X\mid Y]$ is the best guess of $X$ given $Y$, itself a random variable, and the tower property $\mathbb{E}[X]=\mathbb{E}[\mathbb{E}[X\mid Y]]$ lets you compute expectations by conditioning on whatever makes the problem factor (Pishro-Nik §6.3-6.4). The ML framing in Cornell CS 4780’s notation note is a direct application: data are iid draws from an unknown $P$, the test error is an expectation over $P$, and everything you compute from a sample is an estimator of some expectation.

The inequality chain

Each inequality below uses one more piece of structure and buys an exponentially better tail.

The ladder: pay more structure, get a better tail

Bound	Requires	Tail decay
Markov	$X\ge 0$, a mean	$1/a$
Chebyshev	a variance	$1/{ϵ}^2$, and $1/n$ for averages
Chernoff	a moment generating function	$e^{-cn}$, exponential in $n$
Hoeffding	bounded range $[a_i,b_i]$	$2e^{-2n{ϵ}^2}$, explicit constants

Every rung is Markov applied to a transformed variable: Chebyshev is Markov on $(X-\mu {)}^2$, Chernoff is Markov on $e^{tX}$ with $t$ optimized. Climb only as high as your assumptions allow, a heavy-tailed variable with no MGF stops at Chebyshev, but for bounded iid samples go straight to Hoeffding and read off the sample size.

Markov (needs: nonnegativity and a mean). For $X\ge 0$ and $a>0$:

Proof in one line: $\mathbb{E}[X]\ge \mathbb{E}[X\cdot 1\{X\ge a\}]\ge a\mathrm{Pr}[X\ge a]$. The bound decays only like $1/a$, but it is the engine for everything else.

Chebyshev (needs: a variance). Apply Markov to the nonnegative variable $(X-\mu {)}^2$ with threshold ${ϵ}^2$:

Combined with $\mathrm{Var}({\hat{\mu }}_n)={\sigma }^2/n$ this already proves the weak law of large numbers: the empirical mean converges to $\mu$ in probability. The decay in $n$ is only polynomial, $O(1/n{ϵ}^2)$.

Chernoff (needs: a moment generating function). Apply Markov to $e^{tX}$, then optimize the free parameter $t>0$:

Because the MGF of a sum of independent variables factors into a product, the exponent scales linearly in $n$ and the tail decays exponentially. For a sum $S_n$ of independent Bernoullis with mean $\mu =\mathbb{E}[S_n]$, the multiplicative form is $\mathrm{Pr}[S_n\ge (1+\delta )\mu ]\le \exp (-\mu [(1+\delta )\ln (1+\delta )-\delta ])$.

Hoeffding (needs: bounded ranges). For independent $X_i\in [a_i,b_i]$ (Aldous’s handout):

For iid $X_i\in [0,1]$ and the empirical mean, this specializes to the form worth memorizing:

Sample sizes, A/B tests, and measurement noise

Invert the Hoeffding bound. To estimate a $[0,1]$-bounded mean within $\pm ϵ$ with probability $1-\delta$, set $2e^{-2n{ϵ}^2}\le \delta$ and solve:

The shape of this formula explains a lot of practice. Precision is expensive, $n$ grows as $1/{ϵ}^2$, so halving the error bar quadruples the sample size. Confidence is cheap, $\delta$ sits inside a log, so going from 95% to 99.9% confidence costs a small constant factor. Concretely, $ϵ=0.01$ and $\delta =0.05$ needs $n\ge \ln (40)/0.0002\approx 18,445$ samples. An A/B test comparing click-through rates is estimating two such means, and detecting a difference of a fraction of a percent forces the $1/{ϵ}^2$ price. The same arithmetic bounds how many queries an offline recommender evaluation needs before a metric delta is signal rather than sampling noise, and how many benchmark iterations to run before comparing two systems, the concern in the OS benchmarks notes. Hoeffding assumes independent samples; correlated benchmark iterations (warm caches, interference) violate that and make the bound optimistic.

Simulation check

Hoeffding is a worst-case bound, and a simulation shows both that it holds and how much slack it has:

import numpy as np
 
rng = np.random.default_rng(0)
n, eps, trials = 500, 0.05, 200_000
X = rng.random((trials, n))          # iid Uniform[0,1], mu = 0.5
dev = np.abs(X.mean(axis=1) - 0.5)
empirical = (dev >= eps).mean()
hoeffding = 2 * np.exp(-2 * n * eps**2)
print(empirical, hoeffding)          # 8e-05 vs 0.1642

The measured tail probability is $8\times 10^{-5}$ against a Hoeffding bound of 0.164, three orders of magnitude of slack for uniform variables. The gap is expected: Hoeffding only uses the range $[0,1]$ and must cover the worst distribution with that range (Bernoulli at the endpoints), while Uniform[0,1] has variance $1/12$, a third of Bernoulli’s $1/4$. A quick sanity check against the CLT explains the measured number: the empirical mean has standard deviation $\sqrt{1/(12\cdot 500)}\approx 0.0129$, so $ϵ=0.05$ is a 3.9-sigma deviation, and the two-sided normal tail at 3.9 sigma is about $1\times 10^{-4}$, matching the simulation. Variance-aware bounds like Bernstein’s capture this; the ones here are the standard first tools.

Sources

• Pishro-Nik, Introduction to Probability, Statistics, and Random Processes, chapters 6-7
• Aldous, Hoeffding’s inequality, course handout
• Cornell CS 4780 (2018), lecture note 2, ML setup and notation

Related notes

• Bias, Marketplace Effects, and Counterfactual Evaluation
• OS Benchmarks
• Matrix Theory