Law of Large Numbers

The problem it solves (why we need it)

Probability models talk about expected value μ = E[X]. But expectation is not something you directly observe in one experiment—you observe outcomes.

So there’s a natural question:

If I repeatedly sample from a random process, does the average of what I see approach the theoretical expectation?

LLN is the bridge between theory (μ) and data (sample averages).

The main object: the sample mean

Let X₁, X₂, … be random variables representing repeated measurements (e.g., repeated coin flips coded as 1=heads, 0=tails; or repeated customer waiting times; or repeated sensor readings).

Define the sample mean after n samples:

X̄ₙ = (1/n) ∑ᵢ₌₁ⁿ Xᵢ

This is the quantity you compute from data.

Informal statement

If X₁, X₂, … are iid (independent and identically distributed) and have a finite mean μ, then:

• •for small n, X̄ₙ can vary a lot,
• •for large n, X̄ₙ is very likely to be close to μ.

This is not because randomness “goes away,” but because positive and negative deviations tend to cancel when you average many independent samples.

Formal statement (Weak Law of Large Numbers)

The most common version used in statistics and ML is the Weak Law of Large Numbers (WLLN):

X̄ₙ → μ in probability as n → ∞.

That sentence uses a key convergence idea. Unpacking it:

For every ε > 0,

P(|X̄ₙ − μ| > ε) → 0 as n → ∞.

Interpretation: the probability that the sample mean differs from μ by more than ε becomes tiny for large n.

What LLN is not

LLN does not say:

• •“X̄ₙ equals μ for large n.” It says it becomes likely to be close.
• •“Individual samples Xᵢ become less random.” Individual draws stay just as random.
• •“Any sequence averages to its expectation.” Conditions matter (especially independence and finite mean).

A helpful intuition: averaging reduces relative noise

If each Xᵢ has typical fluctuation scale σ (standard deviation), the average X̄ₙ has fluctuation scale roughly σ/√n. That √n in the denominator is the core intuition for why averages stabilize. (This also hints at the Central Limit Theorem you’ll unlock later.)

Two versions you might hear about

There are multiple LLNs. Two common ones:

In this node we emphasize weak LLN because it connects directly to statistical guarantees and concentration-style reasoning.

Why “identically distributed” matters

“Identically distributed” means every Xᵢ comes from the same distribution:

• •same mean μ,
• •same variance σ² (if it exists),
• •same tail behavior, etc.

This ensures that when you average, you’re averaging comparable quantities. If the distribution changes over time (non-stationarity), the “target” expectation might drift, and the average may not settle.

Example of failure without identical distribution:

• •Suppose E[Xᵢ] = i (grows with i). Then X̄ₙ’s expectation also grows, and there is no single μ to converge to.

Why independence matters

Independence is the cancellation engine.

If Xᵢ are independent, deviations above μ in one sample don’t systematically force deviations above μ in others. Over many draws, positive and negative deviations tend to balance.

If they’re correlated, then errors can reinforce instead of cancel.

A quick illustration:

• •If X₁ = X₂ = … = Xₙ (perfect dependence), then X̄ₙ = X₁ for all n.
• •The average does not stabilize with n; you never “get more information” by repeating the same value.

The variance calculation that explains stabilization

Assume X₁, …, Xₙ are iid with mean μ and variance Var(Xᵢ) = σ² < ∞.

Compute Var(X̄ₙ).

Start with:

X̄ₙ = (1/n) ∑ᵢ₌₁ⁿ Xᵢ

Then:

Var(X̄ₙ)

= Var((1/n) ∑ᵢ₌₁ⁿ Xᵢ)

= (1/n²) Var(∑ᵢ₌₁ⁿ Xᵢ)

Now use independence:

Var(∑ᵢ₌₁ⁿ Xᵢ) = ∑ᵢ₌₁ⁿ Var(Xᵢ) = ∑ᵢ₌₁ⁿ σ² = nσ²

So:

Var(X̄ₙ) = (1/n²)(nσ²) = σ² / n

That is the quantitative form of “averaging reduces noise.” The standard deviation of X̄ₙ is:

SD(X̄ₙ) = √Var(X̄ₙ) = σ/√n

This is why doubling your sample size does not halve your error—it shrinks like 1/√n.

Turning variance shrinkage into a probability guarantee (Chebyshev)

To connect to “converges in probability,” we need a bound on:

P(|X̄ₙ − μ| > ε)

Chebyshev’s inequality says for any random variable Y with finite variance:

P(|Y − E[Y]| ≥ ε) ≤ Var(Y)/ε²

Apply it to Y = X̄ₙ. Note E[X̄ₙ] = μ (linearity of expectation):

P(|X̄ₙ − μ| ≥ ε)

≤ Var(X̄ₙ)/ε²

= (σ²/n)/ε²

= σ²/(nε²)

Now observe what happens as n → ∞:

σ²/(nε²) → 0

Therefore:

P(|X̄ₙ − μ| ≥ ε) → 0

This is exactly:

X̄ₙ → μ in probability.

So one clean path to LLN is:

1) independence ⇒ Var(X̄ₙ) = σ²/n

2) Chebyshev ⇒ probability of large deviation ≤ σ²/(nε²)

3) RHS → 0 ⇒ convergence in probability

What conditions are actually required?

The derivation above assumes finite variance. LLN can still hold under weaker conditions (e.g., finite mean without finite variance for strong LLN in some forms), but for many practical ML/statistics contexts, “finite variance + iid” is the standard mental model.

A practical checklist:

Why we need a new kind of “limit”

You already know limits for numbers and functions: aₙ → a means the sequence of numbers gets arbitrarily close to a.

But X̄ₙ is a random variable. For each n, X̄ₙ is not a single number—it’s a distribution over possible sample means.

So “X̄ₙ approaches μ” must mean something like:

• •the distribution of X̄ₙ concentrates near μ,
• •large deviations become unlikely.

That is exactly what convergence in probability captures.

Definition (slow and explicit)

We say Xₙ → c in probability if:

∀ ε > 0, P(|Xₙ − c| > ε) → 0 as n → ∞.

Key points:

• •ε is a tolerance you choose (0.1, 0.01, etc.).
• •The event |Xₙ − c| > ε is “we missed by more than ε.”
• •Convergence in probability says that event’s probability goes to zero.

Connecting to LLN

LLN states:

X̄ₙ → μ in probability.

Meaning:

∀ ε > 0, P(|X̄ₙ − μ| > ε) → 0.

This is the statement you use when you want to justify:

• •“With enough samples, my empirical average is reliable.”

Visual intuition: shrinking spread

Imagine the sampling distribution of X̄ₙ as n increases:

• •Center stays at μ (since E[X̄ₙ] = μ)
• •Spread shrinks like σ/√n

So the probability mass near μ grows, and the mass far away shrinks.

Even without drawing the picture, you can think: the region (μ − ε, μ + ε) captures more and more probability.

Convergence in probability vs almost sure (high-level)

Sometimes learners hear “converges almost surely” and assume it’s the same. It’s stronger.

• •In probability: for large n, it is unlikely to be far from μ.
• •Almost surely: with probability 1 over the infinite sequence of samples, the realized X̄ₙ(ω) actually approaches μ as a numerical limit.

In this node, the weak LLN is enough to support most statistical reasoning and to motivate Monte Carlo.

A practical reading: sample size as a knob

Chebyshev gave:

P(|X̄ₙ − μ| ≥ ε) ≤ σ²/(nε²)

Treat it like a design inequality. Want the failure probability ≤ δ?

Require:

σ²/(nε²) ≤ δ

Solve for n:

n ≥ σ²/(δ ε²)

This is not always tight, but it teaches a key scaling law:

• •error tolerance ε appears as 1/ε²
• •confidence (1 − δ) appears as 1/δ
• •variance σ² makes the problem harder

Even if you later use sharper inequalities (Hoeffding, Bernstein), LLN is the conceptual foundation: more samples ⇒ more reliable averages.

A note about vectors (for ML context)

Often in ML you average vectors (e.g., average gradient estimates). If Xᵢ are iid random vectors in ℝᵈ with mean μ = E[X], then a vector-valued LLN holds under similar finite-moment conditions:

X̄ₙ = (1/n) ∑ᵢ₌₁ⁿ Xᵢ → μ (in probability, componentwise).

To measure error you might use a norm like ‖X̄ₙ − μ‖.

You don’t need the full vector LLN here, but it’s worth seeing how naturally the scalar idea generalizes.

1) Statistics: why sample averages estimate expectations

Many estimators are averages:

• •sample mean estimates E[X]
• •sample proportion estimates P(event)
• •empirical risk estimates expected loss

If you define a quantity of interest as an expectation:

μ = E[g(X)]

and you can sample X₁, …, Xₙ iid, then you can estimate μ by:

μ̂ₙ = (1/n) ∑ᵢ₌₁ⁿ g(Xᵢ)

LLN says μ̂ₙ → μ in probability (under the same style of assumptions). This is the justification for “plug in the average.”

2) Monte Carlo: turning expectations into computation

Monte Carlo methods rely on the identity:

μ = E[g(X)]

When μ is hard to compute analytically (e.g., high-dimensional integrals), you estimate it with samples. LLN is the guarantee that:

(1/n) ∑ g(Xᵢ)

stabilizes as n grows.

Without LLN, Monte Carlo would be a gamble with no convergence story.

3) Central Limit Theorem: what LLN doesn’t tell you

LLN tells you convergence happens, but it doesn’t describe the shape of fluctuations.

The CLT (which you’ll unlock next) refines the picture: roughly,

√n (X̄ₙ − μ)

approaches a normal distribution with variance σ².

So you can build approximate confidence intervals, p-values, and error bars.

Relationship summary:

4) ML connection: empirical risk minimization (ERM)

In supervised learning, you often want to minimize expected loss:

R(θ) = E[L(θ; Z)]

But you only have data Z₁, …, Zₙ. You minimize empirical risk:

R̂ₙ(θ) = (1/n) ∑ᵢ₌₁ⁿ L(θ; Zᵢ)

LLN suggests that for a fixed θ, R̂ₙ(θ) → R(θ) in probability as n increases.

Caution: learning theory needs uniform convergence over θ, which is a deeper topic (VC dimension, Rademacher complexity). But LLN is the first stepping stone: averages over iid data approximate expectations.

5) Why the law is so widely applicable

Because expectations are linear and averaging is simple, LLN becomes a universal tool:

• •physics (average energy)
• •finance (average return)
• •operations (average queue time)
• •A/B testing (difference in sample means)
• •simulation (estimated probability of rare events)

Whenever you see “estimate an expectation by sampling,” LLN is the hidden backbone.