Law of large numbers

What Exactly Is the Law of Large Numbers?

Definition Formal Statement

Let $X_1, X_2, X_3, \ldots$ be independent and identically distributed (i.i.d.) random variables with finite expected value $\mu = E[X_i]$ . Define the sample mean: $\bar{X}_n = \frac{1}{n}\sum_{i=1}^{n} X_i$ Weak Law of Large Numbers (WLLN): For any $\epsilon > 0$ , $\lim_{n \to \infty} P(|\bar{X}_n - \mu| \geq \epsilon) = 0$ (The probability that the sample mean differs from $\mu$ by more than any fixed amount goes to zero)

Strong Law of Large Numbers (SLLN): $P\left(\lim_{n \to \infty} \bar{X}_n = \mu\right) = 1$ (With probability 1, the sample mean converges to $\mu$ )

Why two versions? WLLN says "the sample mean is probably close to $\mu$ for large $n$ ." SLLN says something stronger: "the sample mean will eventually settle at $\mu$ and stay there, guaranteed." For machine learning, WLLN is usually sufficient.

Derivation from First Principles

Let's prove the Weak Law using Chebyshev's inequality.

Step 1: What We Know

We have i.i.d. random variables $X_1, \ldots, X_n$ with:

Mean: $E[X_i] = \mu$
Variance: $\text{Var}(X_i) = \sigma^2$ (assumed finite)

Sample mean: $\bar{X}_n = \frac{1}{n}\sum_{i=1}^{n} X_i$

Step 2: Expected Value of Sample Mean

$E[\bar{X}_n] = E\left[\frac{1}{n}\sum_{i=1}^{n} X_i\right] = \frac{1}{n}\sum_{i=1}^{n} E[X_i] = \frac{1}{n} \cdot n\mu = \mu$

Why this step? Expectation is linear, so we can move it inside the sum. Each $X_i$ has the same mean $\mu$ .

Step 3: Variance of Sample Mean

$\text{Var}(\bar{X}_n) = \text{Var}\left(\frac{1}{n}\sum_{i=1}^{n} X_i\right)$

Since the $X_i$ are independent, variances add: $= \frac{1}{n^2} \text{Var}\left(\sum_{i=1}^{n} X_i\right) = \frac{1}{n^2}\sum_{i=1}^{n} \text{Var}(X_i)$

Why this step? When you multiply a random variable by a constant $c$ , variance scales by $c^2$ . Independence means $\text{Var}(X + Y) = \text{Var}(X) + \text{Var}(Y)$ .

$= \frac{1}{n^2} \cdot n\sigma^2 = \frac{\sigma^2}{n}$

Key insight: The variance of the sample mean decreases as $n$ increases. This is why larger samples are more reliable.

Step 4: Apply Chebyshev's Inequality

Chebyshev's inequality states that for any random variable $Y$ with mean $\mu_Y$ and variance $\sigma_Y^2$ : $P(|Y - \mu_Y| \geq \epsilon) \leq \frac{\sigma_Y^2}{\epsilon^2}$

Apply to $\bar{X}_n$ : $P(|\bar{X}_n - \mu| \geq \epsilon) \leq \frac{\text{Var}(\bar{X}_n)}{\epsilon^2} = \frac{\sigma^2}{n\epsilon^2}$

Step 5: Take the Limit

$\lim_{n \to \infty} P(|\bar{X}_n - \mu| \geq \epsilon) \leq \lim_{n \to \infty} \frac{\sigma^2}{n\epsilon^2} = 0$

Therefore: $\lim_{n \to \infty} P(|\bar{X}_n - \mu| \geq \epsilon) = 0$

Why this step? As $n \to \infty$ , the upper bound goes to zero, so the probability itself must go to zero. This proves the Weak Law.∎

Worked Examples

Worked example Example 1: Fair Coin Flips

Problem: You flip a fair coin $n$ times. Let $X_i = 1$ if heads, $0$ if tails. What's the probability that the proportion of heads differs from 0.5 by more than 0.01 when $n = 10,000$ ?

Solution: Step 1: Identify parameters

$E[X_i] = 0.5$
$\text{Var}(X_i) = E[X_i^2] - (E[X_i])^2 = 0.5 - 0.25 = 0.25$ Why? For a Bernoulli variable, $X_i^2 = X_i$ , so $E[X_i^2] = P(X_i=1) = 0.5$ . Step 2: Apply Chebyshev bound $P(|\bar{X}_n - 0.5| \geq 0.01) \leq \frac{0.25}{1000 \cdot (0.01)^2} = \frac{0.25}{1} = 0.25$ Why this step? Pluging into our formula with $\sigma^2 = 0.25$ , $n = 10000$ , $\epsilon = 0.01$ .

Interpretation: At most 25% chance of being off by more than 1%. In reality, using the Central Limit Theorem (tighter bound), the probability is about 0.046(4.6%). LN gives us a conservative guarantee.

Worked example Example 2: Estimating Average Height

Problem: A population has mean height $\mu = 170$ cm, standard deviation $\sigma = 10$ cm. How many people must you sample so that the sample mean is within 1 cm of the true mean with probability at least 95%?

Solution:

We want: $P(|\bar{X}_n - 170| < 1) \geq 0.95$ Equivalently: $P(|\bar{X}_n - 170| \geq 1) \leq 0.05$

Step 1: Use Chebyshev bound $\frac{\sigma^2}{n\epsilon^2} \leq 0.05$ $\frac{100}{n \cdot 1} \leq 0.05$ Why this step? We set the right side to 0.05 (the maximum allowed probability of error) and solve for $n$ .

Step 2: Solve for $n$ $n \geq \frac{100}{0.05} = 2000$

Answer: Sample at least 2,000 people.

Reality check: Using CLT (normal approximation), you'd need only about 385 people. Chebyshev is conservative but works for any distribution.

Worked example Example 3: Monte Carlo Integration

Problem: Estimate $\int_0^1 e^{-x^2} dx$ by sampling uniform random points and checking if they fall under the curve.

Solution:

Step 1: Set up the problem

Draw $X_i \sim \text{Uniform}(0, 1)$ and $Y_i \sim \text{Uniform}(0, 1)$
Let $Z_i = 1$ if $Y_i \leq e^{-X_i^2}$ , else $0$
The integral equals $E[Z_i] = P(Y_i \leq e^{-X_i^2})$

Step 2: Apply LN $\bar{Z}_n = \frac{1}{n}\sum_{i=1}^{n} Z_i \to E[Z_i] = \int_0^1 e^{-x^2} dx \approx 0.7468$

Why this step? By LN, the sample mean of $Z_i$ converges to the true integral value.

Step 3: Error bound

$\text{Var}(Z_i) \leq 0.25$ (variance of Bernoulli is maximized at $p=0.5$ )
Standard error: $\sigma/\sqrt{n} = 0.5/\sqrt{n}$
For error $< 0.001$ : need $n \geq (0.5/0.001)^2 = 250,000$ samples ML Connection: This is the foundation of Monte Carlo methods for high-dimensional integration in reinforcement learning and Bayesian inference.

Common Mistakes & Steel-Manning

Why This Matters for Machine Learning

Training Convergence: Stochastic gradient descent (SGD) uses LN—the gradient of a mini-batch converges to the true gradient as batch size increases.
Monte Carlo Methods: Estimating expectations (value functions in RL, posterior means in Bayesian ML) relies on LLN to guarantee accuracy.
Sample Complexity: LN tells us how many examples we need to estimate quantities to desired precision. The $O(1/n)$ variance decay is fundamental to learning theory.
Ensemble Methods: Why does averaging predictions from many models reduce error? LN! Individual model errors average out.
A/B Testing: LLN justifies using sample proportions to estimate click-through rates, conversion rates, etc.

Recall Explain to a 12-Year-Old

Imagine you're trying to figure out how tall kids in your school are on average. You measure one kid—maybe they're really tall, like 180 cm. You think, "Wow, everyone must be tall!" But then you measure another kid—150 cm. Now you're confused.

But what if you measure 10 kids? Then 50 kids? Then 200 kids? As you measure more and more, your average gets closer to the real average height of all kids in the school.

The Law of Large Numbers is like a magical promise: "If you keep collecting more data, your average will get closer and closer to the truth." It's not that randomness goes away—some kids are tall, some are short—but the average stabilizes.

This is why scientists do lots of experiments, why polls ask thousands of people, and why casinos always make money (they've played millions of games, so the average always works out in their favor).

Connections

Central Limit Theorem — LLN says where the sample mean goes; CLT says how it gets there (normal distribution)
Chebyshev Inequality — The tool we used to prove LLN; gives probability bounds for any distribution
Variance and Standard Deviation — Variance $\sigma^2/n$ controls convergence rate
Monte Carlo Methods — Direct application of LLN to estimate integrals and expectations
Confidence Intervals — LN justifies using sample statistics to estimate population parameters
Bias-Variance Tradeoff — Variance of estimates decreases with sample size per LN
Stochastic Gradient Descent — Mini-batch gradients converge to true gradient by LN
Bootstrap Sampling — Relies on LLN for resampling-based inference
Expected Value — The $\mu$ that sample means converge to
Independent and Identically Distributed — The i.i.d. assumption required for LLN

#flashcards/ai-ml

What does the Law of Large Numbers state? :: As you repeat an experiment more times, the sample mean $\bar{X}_n$ converges to the expected value $\mu$ . The probability that $|\bar{X}_n - \mu|$ exceds any fixed $\epsilon$ goes to zero as $n \to \infty$ .

What is the difference between Weak LN and Strong LLN?

Weak LLN:

P(|\bar{X}_n - \mu| \geq \epsilon) \to 0

(convergence in probability). Strong LLN:

P(\lim_{n\to\infty} \bar{X}_n = \mu) = 1

(almost sure convergence). SLN is stronger—guarantees eventual settling at

\mu

What is the variance of the sample mean

\bar{X}_n

if each

X_i

has variance

\sigma^2

\text{Var}(\bar{X}_n) = \sigma^2/n

. This decreases as

n

increases, which is why larger samples give more precise estimates.

How fast does the error in sample mean decrease with sample size?

The standard deviation of

\bar{X}_n

\sigma/\sqrt{n}

, so error decreases as

O(1/\sqrt{n})

. To halve the error, you need 4× the samples.

What assumptions are required for the Law of Large Numbers?

The random variables must be (1) independent and (2) identically distributed (i.i.d.) with (3) finite expected value

\mu

(and finite variance for WLLN via Chebyshev).

If you flip a fair coin

n

times, what does LN say about the proportion of heads?

The proportion of heads

\bar{X}_n

converges to

p = 0.5

n \to \infty

. The probability that

|\bar{X}_n - 0.5| > \epsilon

goes to zero for any

\epsilon > 0

How is LN used in Monte Carlo integration?

Sample random points; compute a function value at each point. The sample mean of these values converges to the expected value (the integral) by LLN. Error scales as

1/\sqrt{n}

Why do mini-batch gradients in SGD converge to the true gradient?

By LLN. Each mini-batch gives a noisy gradient estimate. As batch size increases, the sample mean of gradients converges to the true gradient

\nabla L

What bound does Chebyshev's inequality give for LN?

P(|\bar{X}_n - \mu| \geq \epsilon) \leq \sigma^2/(n\epsilon^2)

. This provides a distribution-free guarantee that works for any random variable with finite variance.

Why doesn't LLN mean you'll get exactly 500 heads in 1000 fair coin flips?

LN guarantees convergence in probability, not deterministic convergence. The sample mean gets arbitrarily close to 0.5, but randomness remains—you might get 498, 501503 heads. Absolute fluctuations don't vanish.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Law of Large Numbers ek bahut powerful concept hai joume bata hai ki jab hum kisi experiment kobaar-baar repeat karte hain, toh average result true expected value ke pas ata jata hai. Sochiye ek sika phenk rahe ho—pehli baar heads aya, toh ap soch sakte ho "100% heads!" Lekin jaise-jaise ap aur phenkte ho (10 baar, phir 100 baar, phir 10,000 baar), toh proportion 50% ke karib settle hone lagta hai. Yahi LN ka essence hai.

Machine learning mein yeh concept critical hai. Jab aap SGD use karte ho training ke liye, har mini-batch ek noisy gradient deta hai, lekin LLN guarantee karta hai ki average gradient true gradient ke paas converge karega as batch size badhegi. Isi tarah, Monte Carlo methods mein hum expectations ko estimate karte hain by sampling—sample mean converges to true mean by LLN. Yeh principle A/B testing, ensemble methods, aur confidence intervals ka bhi base hai.

Ek important baat: error decrease hoti hai as $1/\sqrt{n}$ rate se. Matlab agar aapko error half karni hai, toh 4 times zyada samples chahiye. Isliye ML models ko perfect banana itna expensive hota hai—last 1% accuracy ke liye exponentially zyada data aur compute chahiye. LN hume yeh mathematical guarantee deta hai ki consistent sampling se truth ke paas pahunch sakte hain, chahe individual samples random hi kyun na ho.

What Exactly Is the Law of Large Numbers?

Derivation from First Principles

Step 1: What We Know

Step 2: Expected Value of Sample Mean

Step 3: Variance of Sample Mean

Step 4: Apply Chebyshev's Inequality

Step 5: Take the Limit

Worked Examples

Common Mistakes & Steel-Manning

Why This Matters for Machine Learning

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Probability & Statistics

Connections