REFERENCE SHEET

LLN, CLT & concentration

Understand what averaging guarantees—and how much data a guarantee needs.

Before this Random variables & moments

\frac{\sqrt{n} ({\bar{X}}_{n} - μ)}{σ} \overset{d}{\to} N (0, 1)

Definitions

Convergence in probability

Xₙ→X in probability if P(|Xₙ−X|>ε)→0 for every ε>0.

Convergence in distribution

The distribution functions converge at every continuity point of the limiting distribution function.

Sample mean

X̄ₙ=(X₁+⋯+Xₙ)/n. Its behavior depends on assumptions about the sample, not just this formula.

Key theorems

Weak law of large numbers

For iid random variables with finite mean μ, X̄ₙ→μ in probability.

Classical central limit theorem

For iid variables with mean μ and finite variance 0<σ²<∞, the standardized sample mean in the display converges in distribution to a standard normal.

Chebyshev inequality

For finite variance and t>0, P(|X−E[X]|≥t)≤Var(X)/t².

Notable applications

Error bars

CLT approximations explain the common 1/√n scale of sampling error.

Simulation budgets

Concentration bounds provide finite-sample error guarantees, although they may be conservative.

Work it out

Try before revealing

01 / Bound

For iid samples of variance 4, bound P(|X̄ₙ−μ|≥0.5) using Chebyshev.

Hint

Var(X̄ₙ)=4/n.

Solution

The bound is (4/n)/0.25=16/n, or min(1,16/n). To make it at most 0.05, take n≥320.

02 / Compute

If a mean estimate has standard error 0.2 with n samples, how many samples target 0.1 under the same iid variance?

Hint

Standard error scales as n⁻¹ᐟ².