Lecture 19: Weak Law of Large Numbers

What this lecture covers

This lecture opens the course's unit on limit theorems, which studies what happens to sums and averages of many random variables. It asks a concrete question: if you estimate a population's expected value by averaging a random sample, does that sample mean actually get close to the true expected value as the sample grows? Answering this requires two building blocks developed here: an inequality relating probabilities to expected values, and a formal notion of convergence for random variables.

The lecture sits at the start of a two-part sequence; it proves the weak law of large numbers and previews the central limit theorem, which the next lecture develops fully. After watching, you should be able to derive and apply the Markov and Chebyshev inequalities, explain what "convergence in probability" means, and use it to justify why sample averages estimate a population mean, including how to size a sample for a poll.

Key ideas

• Sample mean vs. expected value: the sample mean is a random variable computed from a finite, random sample; the expected value is a fixed number defined over the entire population.
• Markov inequality: for a non-negative random variable X, P(X >= a) <= E[X]/a, which turns a bound on an expected value into a bound on a tail probability.
• Chebyshev inequality: applying Markov's inequality to (X - mu)^2 gives P(|X - mu| >= c) <= Var(X)/c^2, relating variance directly to how far a random variable can stray from its mean.
• Convergence in probability: a sequence of random variables Y_n converges to a number a if, for every band around a, the probability of falling outside that band goes to 0 as n grows.
• Convergence in probability is limited: a sequence can converge in probability to 0 while its expected value or higher moments do not, because a shrinking tail probability can still carry a disproportionately large value.
• Weak law of large numbers: the sample mean of independent, identically distributed random variables with finite mean and variance converges in probability to the true mean.
• Sample size and polling: Chebyshev's inequality can be used to compute how large a sample must be to guarantee a desired accuracy with a desired confidence, though the bound it gives is conservative.
• Scaling sums differently: dividing a sum of i.i.d. variables by n collapses it to a point (the weak law); dividing by sqrt(n) after centering keeps the variance constant and leads toward the central limit theorem.

Walkthrough

Motivation: estimating a mean from a sample (0:02)

Using an example of estimating average penguin height from a random sample, the lecture distinguishes the sample mean (random, based on a finite sample) from the expected value (a fixed population parameter). It frames the central question of limit theorems: does the sample mean get closer to the true mean as sample size grows, and in what sense?

The Markov inequality (5:04)

For a non-negative random variable, the lecture shows that restricting a sum over probabilities to only the region where X >= a can only decrease the value of E[X], giving E[X] >= a * P(X >= a). This is the Markov inequality, which translates a small expected value into a small tail probability.

The Chebyshev inequality (8:08)

Applying the Markov inequality to (X - mu)^2 yields P(|X - mu| >= c) <= Var(X)/c^2. The lecture re-derives this directly by integration for a continuous variable, then rewrites it in terms of standard deviations (k sigma), showing, for example, that at most 1/9 of a distribution can lie 3 standard deviations or more from the mean.

Convergence of sequences and random variables (14:16)

The lecture reviews the epsilon-band definition of convergence for ordinary number sequences, then extends it to random variables: Y_n converges in probability to a if the probability that Y_n falls outside any fixed band around a goes to 0 as n -> infinity. A worked example shows a distribution converging to 0 in probability while its expected value and second moment diverge, illustrating that convergence in probability doesn't control moments.

Proving the weak law of large numbers (24:30)

For i.i.d. X_i with mean mu and variance sigma^2, the lecture computes E[M_n] = mu and Var(M_n) = sigma^2/n. Applying Chebyshev's inequality to the sample mean gives P(|M_n - mu| >= epsilon) <= sigma^2/(n*epsilon^2), which goes to 0 as n grows for any fixed epsilon. This is exactly convergence in probability, proving the weak law of large numbers.

Applying it to polling and sample size (30:36)

Using the example of estimating the fraction of people preferring one product over another, the lecture shows how to translate an accuracy requirement and a confidence level into a required sample size via Chebyshev's inequality, using the worst-case variance of a Bernoulli variable (1/4). The calculation yields a sample size of 50,000, much larger than the roughly 1,000 used in real polls, because Chebyshev's bound is not tight.

Toward the central limit theorem (39:46)

The lecture explains why real polls use smaller samples: a sharper limit theorem gives tighter bounds. It contrasts scaling a sum of i.i.d. variables by n (which collapses the distribution to a point, the weak law) with dividing by sqrt(n) after centering (which keeps the variance constant), setting up the standardized variable Z_n that the central limit theorem addresses next.

Before you watch

• Review discrete and continuous expectation and variance, and the formula for the variance of a sum of independent random variables.
• Be comfortable with basic probability mass and density functions and cumulative distribution functions.

Check your understanding

1. How is the Chebyshev inequality derived from the Markov inequality?
2. What does it mean for a sequence of random variables to converge in probability, and how does this differ from convergence of their expected values?
3. Using Chebyshev's inequality, how would you compute the sample size needed to estimate a proportion within a given accuracy and confidence?
4. Why does dividing a sum of i.i.d. random variables by sqrt(n) (after centering) keep its variance constant as n grows, unlike dividing by n or not scaling at all?