Concentration Inequalities, the Law of Large Numbers, and the Central Limit Theorem

Two inequalities that bound how much probability mass can sit far from the mean, using nothing but the mean (Markov) or the mean and variance (Chebyshev), plus the two limit theorems they enable: the law of large numbers (the sample average converges to the true mean — provable directly via Chebyshev) and the central limit theorem (properly normalized, the sample average converges in distribution to a standard normal). Chebyshev alone gives a cheap, distribution-free confidence interval for a sample average; the CLT gives a tighter one once its approximation is justified. Also covers the informal, Gaussian-approximation-heuristic version of the CLT (sums of many independent, comparably-sized random effects look Gaussian, which is why the normal approximation shows up everywhere in practice) ahead of — and as motivation for — the formal statement.

Markov inequality

TheoremMarkov inequality (Hajek §2.9)

If $Y\ge0$ and $c > 0$ , $P\{Y\ge c\}\le\frac{E[Y]}c.$ Equality holds iff $p_Y(0) + p_Y(c) = 1$ .

ProofBound each value from below

Each possible value $u_i$ is at least 0, and at least $c$ when $u_i\ge c$ . So $E[Y] = \sum_iu_ip_Y(u_i)\ge\sum_{i:\,u_i\ge c}c\,p_Y(u_i) = cP\{Y\ge c\}.$ (This is the discrete case. For continuous $Y$ , replace the sum by an integral.)

∎

ExampleBalls in buckets (Hajek)

200 balls sit in 100 buckets in some unknown way. At most how many buckets can hold 5 or more? Pick a bucket at random and let $Y$ be its ball count, so $E[Y] = 2$ . Markov gives $P\{Y\ge5\}\le\frac25$ , so at most 40 buckets. This is tight: put 5 balls in each of 40 buckets.

IntuitionOnly the mean is known

If too much mass sat far out, the mean would have to be larger. Markov is the best bound available from the mean alone, as the tight example shows.

Chebyshev inequality

TheoremChebyshev inequality

If $X$ has mean $\mu$ and variance $\sigma^2$ , then for $d > 0$ and $a > 0$ ,

P\{|X - \mu|\ge d\}\le\frac{\sigma^2}{d^2},\qquad P\{|X - \mu|\ge a\sigma\} \le\frac1{a^2}. \tag{2.12–2.13}

ProofMarkov applied to the squared deviation

Apply Markov to $Y = (X - \mu)^2$ with $c = d^2$ : $P\{|X - \mu|\ge d\} = P\{Y\ge d^2\}\le E[Y]/d^2 = \sigma^2/d^2$ . Then take $d = a\sigma$ .

∎

ImportantDistribution-free, therefore conservative

Chebyshev holds for every distribution with the given mean and variance, so for any particular one it is usually loose. At $2\sigma$ it guarantees 75%, while a normal puts about 95% within $2\sigma$ (continuous-random-variables-and-distributions).

Confidence intervals from concentration bounds

DefinitionPoint and interval estimators

To estimate a population fraction $p$ , sample $n$ at random and let $X$ be the number with the property, so $\hat p = X/n$ is a point estimator. If the population is much larger than $n$ , $X$ is approximately binomial $(n,p)$ , with $\sigma = \sqrt{np(1-p)}$ .

TheoremA Chebyshev confidence interval

For any $a > 0$ ,

P\Big\{p\in\Big(\hat p - \frac a{2\sqrt n},\ \hat p + \frac a{2\sqrt n}\Big) \Big\}\ge1 - \frac1{a^2}. \tag{2.15}

ProofChebyshev, then remove the unknown

p

Step 1: Chebyshev on $X$ . $P\{|X - np| < a\sigma\}\ge1 - 1/a^2$ . Divide by $n$ : $P\{|\hat p - p| < a\sqrt{p(1-p)/n}\}\ge1 - 1/a^2$ .

Step 2: The interval still depends on $p$ . Since $p(1-p)\le\frac14$ (discrete-random-variables-and-distributions), replacing $p(1-p)$ by $\frac14$ widens the interval to half-width $\frac a{2\sqrt n}$ , which can only raise the probability.

∎

FormulaConfidence levels

$a$	2	5	10
$1 - 1/a^2$	75%	96%	99%

WarningThe interval is random, not $p$

“96% confidence” is a statement before sampling: the random interval will cover the fixed, unknown $p$ with probability at least 96%. After you see the data and compute a particular interval, it is not true that $p$ lies in it with probability 96%.

ExampleHow many phone numbers to test? (Hajek)

To estimate the fraction of busy numbers within 0.1 with 96% confidence, take $a = 5$ . The half-width $\frac{2.5}{\sqrt n}\le0.1$ needs $n\ge(2.5/0.1)^2 = 625$ .

RemarkChebyshev versus the normal approximation

Chebyshev intervals are conservative. Intervals from the normal approximation are narrower for the same confidence (continuous-random-variables-and-distributions). The formal justification is the central limit theorem, still to be written below.

Still to write

NoteTODO — The central limit theorem and the Gaussian approximation (informal heuristic)

Absorbed from gaussian-distribution-and-clt. Needs Hajek’s informal treatment; source text not yet in sources/. The DeMoivre–Laplace special case is already in continuous-random-variables-and-distributions.

NoteTODO — Law of large numbers

Needs Ross Ch. 8 and the corresponding Hajek material. Source text not yet in sources/.

NoteTODO — Central limit theorem (formal statement)

Needs Ross Ch. 8 and the corresponding Hajek material. Source text not yet in sources/.

Quick reference

Object	Statement	Note
Markov	$P\{Y\ge c\}\le E[Y]/c$ for $Y\ge0$	tight: mass only at 0 and $c$
Chebyshev	$P\{\lvert X-\mu\rvert\ge a\sigma\}\le1/a^2$	Markov on $(X-\mu)^2$
Proportion CI	$\hat p\pm\frac a{2\sqrt n}$ with confidence $\ge1 - 1/a^2$	uses $p(1-p)\le\frac14$
Sample size	$n\ge(a/(2\epsilon))^2$ for half-width $\epsilon$	625 for $\epsilon = .1$ , 96%

Facts to keep to hand

Tail bounds from moments alone. Markov needs only the mean, Chebyshev the mean and variance. Both hold for every distribution, which makes them robust and conservative.
Confidence belongs to the procedure, not the interval. The random interval covers the fixed $p$ with the stated probability before the data are seen.
Precision costs $1/\epsilon^2$ samples. Halving the half-width quadruples the sample size, because the spread of $\hat p$ shrinks like $1/\sqrt n$ .

References

Hajek, Probability with Engineering Applications (ECE 313 notes) — chapter 2, §2.9 (LLN and CLT pending)

Related

Concentration Inequalities, the Law of Large Numbers, and the Central Limit Theorem

Markov inequality

Chebyshev inequality

Confidence intervals from concentration bounds

Still to write

Quick reference

References

Mentioned in