Expectation, variance and why averages work

How many test questions do you need before a model's benchmark score means anything? Why does a minibatch of 512 examples give a usable gradient for a dataset of billions? Both questions have the same answer: averages of independent quantities concentrate around their expectation, at a rate you can calculate.

Expectation and variance

A random variable $X$ attaches a number to each outcome. Its expectation is the probability-weighted average of its values:

For a single test question scored 1 if correct and 0 if not, $\mathbb{E}[X] = P(\text{correct}) = p$. Expectation is linear: $\mathbb{E}[aX + bY] = a\,\mathbb{E}[X] + b\,\mathbb{E}[Y]$ for any $X, Y$, dependent or not. That property alone makes most calculations tractable.

Variance measures spread around the mean:

and the standard deviation $\sigma = \sqrt{\operatorname{Var}(X)}$ is in the same units as $X$. For the 0/1 score, $\mathbb{E}[X^2] = p$, so $\operatorname{Var}(X) = p(1-p)$, largest at $p = 0.5$.

Variance is not linear, but it has one crucial property. Scaling gives $\operatorname{Var}(aX) = a^2 \operatorname{Var}(X)$, and if $X$ and $Y$ are independent (more generally, uncorrelated),

Variances add; standard deviations do not.

The average of $n$ samples

Let $X_1, \dots, X_n$ be independent with mean $\mu$ and variance $\sigma^2$, and let $\bar X = \frac{1}{n}\sum_i X_i$. By linearity $\mathbb{E}[\bar X] = \mu$. By additivity and scaling,

This $1/\sqrt n$ law is the reason averages work, and also the reason they work slowly: quadrupling the sample halves the error.

That the average converges to $\mu$ is the law of large numbers. Jacob Bernoulli proved the first version, for the frequency of successes in repeated trials, in Ars Conjectandi, published in 1713, eight years after his death.^[1] Chebyshev's 1867 paper gave the inequality that now provides a two-line proof:^[2]

Applied to $\bar X$, whose standard deviation is $\sigma/\sqrt n$, the probability of any fixed deviation shrinks to zero as $n$ grows.

Chebyshev's bound uses only the variance, so it is loose. If each $X_i$ lies in $[0, 1]$, Hoeffding's inequality (1963) gives an exponentially small tail:^[3]

The central limit theorem says more: for large $n$, $\bar X$ is approximately normal with mean $\mu$ and standard deviation $\sigma/\sqrt n$, whatever the shape of the individual $X_i$, provided their variance is finite.

Worked example: how big must a benchmark be?

You want to estimate a model's accuracy to within $\pm 3$ percentage points with 95% confidence. Each question is a 0/1 variable with variance $p(1-p) \le 1/4$. The three tools give three answers:

Chebyshev and Hoeffding are guarantees; the normal approximation is an estimate that is accurate for sample sizes like these. All three make the same practical point: a few hundred questions cannot resolve differences of a couple of points. On a 500-question benchmark with accuracy near 70%, the standard error is $\sqrt{0.7 \times 0.3 / 500} \approx 0.020$, so the 95% interval is roughly $\pm 4$ points. Two models 2 points apart on such a benchmark are not distinguishable from that result alone. The reading AI results lesson returns to this.

Where concentration shows up in deep learning

Minibatch gradients. The full training loss is an average over examples, so its gradient is an average of per-example gradients. A gradient computed on a random minibatch of $B$ examples is an unbiased estimate of the full gradient, with noise that shrinks as $1/\sqrt B$. Robbins and Monro's 1951 stochastic approximation method established that iterating with noisy but unbiased estimates, under suitable step-size conditions, still converges.^[4] Stochastic gradient descent is that idea at scale (see Stochastic optimization).

Scaling in attention. A transformer compares a query $q$ and key $k$ by their dot product, $q \cdot k = \sum_{i=1}^{d} q_i k_i$. If the components are independent with mean 0 and variance 1, each term $q_i k_i$ has mean 0 and variance 1, so by additivity the sum has variance $d$ and standard deviation $\sqrt d$. Vaswani and colleagues used this argument to justify dividing scores by $\sqrt{d_k}$: without it, large dot products push the softmax into regions where its gradients are very small.^[5]

Initialisation. The same additivity governs signals passing through a layer: each output is a sum over $n$ inputs, so its variance grows with $n$ unless the weights' variance shrinks as $1/n$. Glorot and Bengio's 2010 analysis of activation and gradient variances across layers led to the widely used initialisation that scales weight variance by layer width.^[6]

When averages fail

The guarantees above rest on two assumptions, and both fail in practice.

Independence. If benchmark questions come in clusters of near-duplicates, or a model's errors are correlated across items, the effective sample size is smaller than $n$ and the true error bars are wider than $\sigma/\sqrt n$.

Finite variance and light tails. The law of large numbers needs a finite mean, and the $\sigma/\sqrt n$ rate needs finite variance. The average of $n$ independent standard Cauchy variables is itself standard Cauchy: it does not concentrate at all, however large $n$ is. Less extreme heavy tails converge, but the normal approximation then badly misjudges rare events. The lab's Thurstone bounds Best-of-N applies exactly this caution to verifier scores. With Gaussian score noise, the chance a wrong candidate outscores a right one is $\Phi(-\text{gap}/(\sigma\sqrt 2))$, where the $\sqrt 2$ comes from adding the variances of two independent scores. With Cauchy noise the Gaussian formula under-predicts that rate by more than an order of magnitude in the paper's tests, so the paper recommends checking the tail (for instance, with excess kurtosis) before trusting any Gaussian fit.^[7]

Key takeaways

• Expectation is linear; variance adds over independent terms. Together they give $\operatorname{sd}(\bar X) = \sigma/\sqrt n$, the $1/\sqrt n$ law behind every error bar.
• Chebyshev (variance only) and Hoeffding (bounded variables) turn this into guarantees; the central limit theorem gives the usual normal-approximation intervals.
• A few hundred evaluation items give error bars of several percentage points. Small benchmark gaps are often noise.
• Minibatch SGD, the $1/\sqrt{d_k}$ in attention, and width-scaled initialisation are all applications of variance additivity.
• Correlated samples and heavy tails break these guarantees; check both before trusting an average.

Sources