Sampling Distributions and the Central Limit Theorem

The previous chapters computed expectations and variances from distributions we knew exactly. In practice the distribution is unknown, and all we have is a sample of data drawn from it. A number computed from a random sample is itself random, because a different sample would give a different number. The distribution of that number across all the samples we could have drawn is its sampling distribution, and it tells us how far the number is likely to be from the quantity we actually care about.

info

This chapter covers

• populations, i.i.d. samples and statistics,
• the mean, variance and standard error of the sample mean,
• the sample variance and why it divides by $n - 1$,
• the law of large numbers, and
• the central limit theorem, with a simulator to try it.

Populations and Samples

The population is the distribution we want to learn about. It might be every roll a particular d20 could produce, the returns an agent collects from a state under a fixed policy, or the final score of an RL algorithm across every random seed it could be run with.

A random sample of size $n$ is a collection $X_1, \dots, X_n$ of random variables that are independent and identically distributed (i.i.d.). Identically distributed means each $X_i$ follows the population distribution, with mean $\mu$ and variance $\sigma^2$. Independent means that the value of one doesn't change the probabilities of the others, as with separate rolls of a die or separate training runs with different seeds.

Statistics and Their Sampling Distributions

A statistic is any quantity computed from the sample. The two most common are the sample mean and the sample variance,

$$\bar{X} = \frac{1}{n} \sum_{i=1}^{n} X_i, \qquad S^2 = \frac{1}{n - 1} \sum_{i=1}^{n} (X_i - \bar{X})^2.$$

Roll a d20 ten times and average the results, and you might get $11.2$. Roll it ten more times and you might get $9.4$. Each batch of ten rolls gives a different $\bar{X}$, and the histogram of many such averages approximates the sampling distribution of $\bar{X}$ for $n = 10$.

The Sample Mean

The rules from chapter 4 give the center and spread of the sampling distribution of $\bar{X}$ without knowing anything else about the population. Linearity gives its mean,

$$\mathbb{E}[\bar{X}] = \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}[X_i] = \mu,$$

so the sample mean is centered on the population mean. Because the $X_i$ are independent, their variances add, and $\operatorname{Var}(aX) = a^2 \operatorname{Var}(X)$ gives

$$\operatorname{Var}(\bar{X}) = \frac{1}{n^2} \sum_{i=1}^{n} \operatorname{Var}(X_i) = \frac{\sigma^2}{n}.$$

The standard deviation of the sample mean is called the standard error,

$$\text{SE}(\bar{X}) = \frac{\sigma}{\sqrt{n}}.$$

The standard error shrinks with the square root of the sample size, so halving it takes four times as much data. The average of 25 d20 rolls has a standard error of $5.77 / 5 \approx 1.15$, while a single roll has a standard deviation of $5.77$.

The Sample Variance

The population variance $\sigma^2$ is usually unknown too, and the sample variance $S^2$ estimates it. The division by $n - 1$ rather than $n$ makes $\mathbb{E}[S^2] = \sigma^2$. The deviations are measured from $\bar{X}$, which is computed from the same data and so sits closer to the sample than $\mu$ does. Dividing by $n$ would therefore underestimate $\sigma^2$ on average.

Replacing $\sigma$ with $S$ gives the estimated standard error $S / \sqrt{n}$. When a paper shows a learning curve averaged over $n$ independent runs with a shaded band of plus or minus one standard error, this is the quantity behind the band.

The Law of Large Numbers

The variance of $\bar{X}$ goes to zero as $n$ grows, so the sample mean settles on the population mean. The law of large numbers states that for any tolerance $\varepsilon > 0$,

$$\Pr\big(|\bar{X}_n - \mu| > \varepsilon\big) \to 0 \quad \text{as } n \to \infty.$$

This is what justifies estimating an expectation by an average. In RL, the sample-average estimate of an action's value in a multi-armed bandit converges to the true value as the action is tried more often, and Monte Carlo methods estimate the value of a state by averaging the returns observed after visiting it.

The Central Limit Theorem

The law of large numbers says that $\bar{X}$ approaches $\mu$, and the central limit theorem (CLT) describes the shape of the remaining error. If $X_1, \dots, X_n$ are i.i.d. with mean $\mu$ and finite variance $\sigma^2 > 0$, then the standardized sample mean approaches the standard normal distribution,

$$\Pr\left( \frac{\bar{X}_n - \mu}{\sigma / \sqrt{n}} \le z \right) \to \Phi(z) \quad \text{as } n \to \infty, \text{ for every } z,$$

where $\Phi$ is the CDF of the standard normal. In practice, for large $n$,

$$\bar{X} \approx \mathcal{N}\left(\mu, \frac{\sigma^2}{n}\right).$$

What makes the theorem remarkable is that it doesn't depend on the shape of the population. The population can be discrete, skewed or lumpy, and as long as its variance is finite, the average of enough samples is approximately normal.

How large $n$ needs to be does depend on the population. The often-quoted "$n \ge 30$" is a rule of thumb, not part of the theorem. Symmetric populations like a d20 roll converge after a handful of samples, while skewed ones need many more. For a Bernoulli population, a common guideline is that both $np$ and $n(1-p)$ should be at least 10, which for the crit indicator with $p = 0.05$ means $n \ge 200$. Populations with infinite variance, such as the Cauchy distribution, don't satisfy the theorem at all.

The CLT is the reason the normal distribution is everywhere in statistics. It implies, for example, that $\bar{X}$ lands within $1.96$ standard errors of $\mu$ about 95% of the time, which is the starting point for confidence intervals.

Try It

Start with the critical-hit population and $n = 1$, then draw 1,000 samples. With one roll per sample, the "means" are just zeros and ones. Now increase $n$ to 5, 30 and 100 and draw again. The histogram becomes smoother and closer to the normal curve, but it stays visibly skewed at $n = 30$. Then switch to the d20 roll, where the bell shape already appears at $n = 5$. In every case, the readouts below the plots match $\mu$ and $\sigma / \sqrt{n}$. The right-hand plot zooms in as $n$ grows, so watch its axis to see the sample means concentrate.

Population

Sample size n1

Population distribution

Means of 0 samples of size 1

Mean of the sample means

– (population mean μ = 0.050)

Standard deviation of the sample means

– (standard error σ/√n = 0.218)

Recap

• A random sample is a set of i.i.d. draws from the population, and a statistic is any number computed from it.
• A statistic varies from sample to sample, and its distribution across samples is its sampling distribution.
• The sample mean has mean $\mu$ and standard error $\sigma / \sqrt{n}$.
• The sample variance divides by $n - 1$ so that it is centered on $\sigma^2$.
• The law of large numbers says $\bar{X}$ converges to $\mu$.
• The central limit theorem says $\bar{X}$ is approximately $\mathcal{N}(\mu, \sigma^2/n)$ for large $n$, whatever the population's shape, as long as its variance is finite.

1. $X_1, \dots, X_n$ are i.i.d. with variance $\sigma^2$. What is the variance of the sample mean $\bar{X}$?

• $\sigma^2 / n$
• $\sigma^2$
• $\sigma / \sqrt{n}$
• $n \sigma^2$

2. You report the average score of an RL agent over 10 seeds. How many seeds would you need to halve the standard error?

• 20
• 40
• It can't be reduced by adding seeds
• 100

3. What does the central limit theorem say?

• The sample mean is exactly normal whenever $n \ge 30$
• The sample variance equals the population variance for large $n$
• The sample mean is approximately normal for large $n$, as long as the population has finite variance
• Every population becomes normal once enough data is collected

What's Next

A chapter on Monte Carlo estimation is planned next. It turns these results into a general recipe for estimating expectations from samples, including how to update an average one sample at a time and how to reweight samples drawn from the wrong distribution. Both ideas are central to the RL notes, starting with the incremental action-value estimates in multi-armed bandits.