Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 36 · Random Variables Review

Law of Large Numbers and the Central Limit Theorem

See why averages settle down and sums look normal: Markov and Chebyshev bounds, the law of large numbers and the central limit theorem, tested in Python.

Two theorems explain why probability works in the long run. The law of large numbers says averages settle down to the true mean. The central limit theorem says the leftover fluctuation is shaped like a bell curve. Both are used constantly for processes: the first justifies long-run averages of Markov chains, the second sizes the random wobble around them.

Two simple inequalities

Before the theorems, two bounds that need almost no assumptions.

Markov's inequality. If X >= 0 and a > 0, then P(X >= a) <= E[X] / a.

Why: the average E[X] is at least a times the probability of being above a.

Chebyshev's inequality. For any variable with mean μ and variance σ², and k > 0,

Text
P(|X - μ| >= k) <= σ² / k²

It follows by applying Markov's inequality to (X - μ)². Both bounds are crude, but they hold for every distribution.

Python How crude is Chebyshev's bound?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The actual probabilities are much smaller than the bound. Chebyshev's value lies in its generality.

The law of large numbers (LLN)

Let X_1, X_2, ... be independent with the same mean μ and variance σ². The sample mean is X̄_n = (X_1 + ... + X_n) / n. It has

Text
E[X̄_n] = μ        Var(X̄_n) = σ² / n

By Chebyshev, P(|X̄_n - μ| >= ε) <= σ² / (n ε²), which goes to 0 as n grows. This is the weak law of large numbers: the sample mean is almost surely close to μ for large n. The strong law says more: with probability 1, the sequence X̄_n converges to μ along the whole path. (The strong law holds even if only the mean exists.)

Python Running averages converge

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For processes, an LLN for Markov chains (Chapter 4) says the long-run fraction of time in a state converges to its stationary probability.

The central limit theorem (CLT)

The LLN says X̄_n approaches μ. The CLT describes the shape of the error. Standardize:

Text
Z_n = (X_1 + ... + X_n - nμ) / (σ √n)

Then, for large n, Z_n is approximately standard normal, whatever the distribution of the X_i (provided variance σ² is finite). In symbols, P(Z_n <= z) → Φ(z) as n → ∞, where Φ is the standard normal CDF.

So a sum of many independent pieces behaves like a normal variable with mean nμ and variance nσ². This is the reason the normal distribution appears everywhere, and the reason a random walk after n steps has typical size √n.

Python CLT with a very non-normal start: exponential variables

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The agreement is good in the middle at n = 50, but the skewness of the exponential still shows in the tails (the lower tail is too light, the upper tail slightly heavy). Heavier skew or smaller n needs more terms before the sum looks normal.

When the theorems fail

  • Infinite variance. The Cauchy distribution has no mean, and the average of Cauchy samples does not settle down at all. Averaging gives no gain.
  • Strong dependence. The LLN and CLT need independence or a weak enough dependence. For Markov chains and other processes, we use versions that account for the dependence.

The LLN does not say that losses "balance out". After a run of heads, the next flip is still 50/50. The proportion of heads converges, but the difference between heads and tails does not shrink; it typically grows like √n.

flowchart LR
    A["Sum of n i.i.d. terms"] --> B["Average X̄_n → μ<br/>(LLN)"]
    A --> C["Fluctuation of size σ √n<br/>~ Normal (CLT)"]

Two views of the same sum: where it goes and how it wobbles.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Chebyshev's inequality bounds P(|X - μ| >= k) by...

    P(|X - μ| >= k) <= Var(X) / k².
  2. 2. What is Var of the sample mean of n independent variables with variance σ²?

    Var(sum) = n σ², and dividing by n multiplies the variance by 1/n², leaving σ²/n.
  3. 3. The CLT says that the standardized sum of many i.i.d. finite-variance variables is approximately...

    That is the central limit theorem, regardless of the shape of the individual distribution.
  4. 4. After 10 heads in a row, a fair coin is 'due' for tails.

    The LLN is about proportions in the long run, not about correcting earlier results.

Summary

  • Markov and Chebyshev inequalities bound tail probabilities using only the mean and variance.
  • The LLN: the sample mean converges to μ; its variance is σ²/n.
  • The CLT: standardized sums are approximately normal, with typical fluctuation σ√n.
  • Both theorems assume independence (or weak dependence) and finite variance.

Next: The Markov Property and Transition Matrices