Law of Large Numbers

Цели урока

• Build intuition for the law of large numbers through examples
• Understand why the sample mean stabilizes as the sample grows
• Distinguish the weak and strong LLN
• Understand the connection to the frequentist definition of probability
• See the LLN in action: casinos, insurance, ML

Предварительные знания

• Expected value E[X]
• Variance Var[X]
• Independent random variables
• Chebyshev's inequality

• Expected Value
• Variance

**1940, a wartime internment camp in Denmark.** South African mathematician John Kerrich, stuck with nothing better to do, ran an experiment. He flipped a coin **10,000 times** and recorded every result. After 10 flips, the heads fraction was 40%. After 100, 44%. After 1,000, 50.2%. After 10,000, 50.67%. The coin was "converging" to fair. This was the Law of Large Numbers in action.

• Casinos: why "the house always wins"
• Insurance: predictability with millions of policies
• Polls: why 1,000 people can represent millions
• A/B tests: how long to wait for a significant result
• ML: why mini-batch gradient descent works

The golden theorem: 20 years of work

Jacob Bernoulli spent **20 years** proving what seems intuitive today. He called the result his "golden theorem," and it was published posthumously in *Ars Conjectandi* (1713). This was the first rigorous link between **theory** (probability) and **practice** (frequency). Bernoulli's point: even a fool sees this intuitively, but proving it is another matter entirely.

Law of Large Numbers

Flip a coin once - heads or tails, huge spread. Flip it 10,000 times - the share of heads will be very close to 0.5. The fact is intuitive but requires a rigorous formulation: the **Law of Large Numbers** (LLN) is one of the founding results of probability theory.

Formally: for i.i.d. random variables $X_1, X_2, \dots$ with finite $\mathbb{E}[X]=\mu$, the sample mean $\bar{X}_n = \frac{1}{n}\sum X_i$ converges to $\mu$ as $n\to\infty$. This is the **weak LLN** (convergence in probability) or the **strong LLN** (almost-sure convergence).

The LLN is the theoretical justification of Monte Carlo methods in ML, empirical risk in supervised learning, and gradient estimation in SGD. Without it we could not justify the leap from 'sample' to 'population'.

1. Intuition: what happens as the sample grows?

1. Intuition: what happens as the sample grows?

Suppose we flip a fair coin and track the heads fraction:

See the pattern? The deviation **decreases** approximately as $1/\sqrt{n}$.

**Key insight:** when the sample grows by a factor of 100, the deviation decreases by about a factor of 10 (by $\sqrt{100}$).

2. Formal statement

2. Formal statement

Let $X_1, X_2, X_3, \ldots$ be **independent identically distributed** (i.i.d.) random variables with:

• $E[X_i] = \mu$ (finite expected value)
• $Var[X_i] = \sigma^2 < \infty$ (finite variance, needed for the Chebyshev proof below; the strong LLN actually goes through with just $E[|X_i|] < \infty$)

**Sample mean:**

**Law of Large Numbers:** as $n \to \infty$, the sample mean converges to the expected value:

Weak vs. Strong LLN

There are two versions of the theorem; they differ in the **type of convergence**:

**The difference:** the weak version says the probability of a large deviation goes to 0. The strong version says the entire sample path of X̄ₙ almost surely converges to μ. In practice the difference rarely matters.

3. Why does it work? The math behind the intuition

3. Why does it work? The math behind the intuition

Compute the moments of the sample mean:

Expected value of X̄ₙ

The sample mean is an **unbiased** estimator of μ: on average, it hits μ exactly.

Variance of X̄ₙ: the key to the LLN

The variance of the sample mean **decreases as 1/n**. That is the heart of the LLN.

**Standard error of the mean:** $SE = \frac{\sigma}{\sqrt{n}}$ It decreases as $1/\sqrt{n}$. To cut the error in half, four times as many observations are required.

Proof of the weak LLN (via Chebyshev)

By Chebyshev's inequality:

The probability of a large deviation goes to zero as $n \to \infty$. ∎

4. Connection to the frequentist definition of probability

4. Connection to the frequentist definition of probability

The LLN **justifies** the frequentist definition of probability!

If event A has probability p, then its relative frequency in n independent trials:

This is a special case of the LLN: let $X_i = 1$ if A occurred, 0 otherwise. Then $E[X_i] = p$ and $\bar{X}_n$ is the relative frequency of A.

The frequency stabilizes around 0.5, but not monotonically.

5. The main error: "The Law of Averages"

5. The main error: "The Law of Averages"

**Gambler's Fallacy:** the belief that past outcomes affect future ones in independent trials. The coin **does not remember** what came before!

Practice

Practice

LLN: the foundation of statistics

The law of large numbers underlies almost every statistical method.

• CLT — The next step: not just convergence, but the shape of the distribution
• Parameter estimation — Consistency of estimators is based on the LLN
• Monte Carlo method — Estimating integrals through random sampling
• ML: SGD — Mini-batch gradient converges to the full gradient by the LLN
• Insurance — Predictability with a large number of policies

Итоги

• **LLN:** $\bar{X}_n \to \mu$ as $n \to \infty$
• **Why it works:** $Var[\bar{X}_n] = \sigma^2/n \to 0$
• **Standard error:** $SE = \sigma/\sqrt{n}$ - decreases as $1/\sqrt{n}$
• **Frequency converges to probability:** the justification for the frequentist interpretation
• **Not compensation:** the past is diluted, not corrected

Вопросы для размышления

• Back to Kerrich: why was his experiment important for science, even though the LLN had already been proven theoretically?
• An insurance company pays an average of $10,000 per policy, but individual payouts range from $0 to $1 million. Why is the company confident in its calculations?
• If the LLN speaks of convergence as n → ∞, how is it applied in practice with a finite n?
• Why does cutting the error in half require four times as many observations, not just twice as many?

Связанные уроки

• aie-36-fine-tuning
• stat-02-estimation
• stat-01-sampling