Appendix B: Probability and Statistics for Evaluation

June 2026 (3465 Words, 20 Minutes)

1. Introduction

Lecture 8 leans on a small pile of probability and statistics — Bernoulli trials, expectation, variance, the binomial distribution, convexity, Jensen’s inequality, estimator bias, and the bootstrap. The lecture introduces each one at the moment it is needed, in a sentence or two, because that is the right dose for the argument it is making. This appendix is the other dose: the same ideas, slowed down, from the ground up, for anyone who met them long ago or never quite met them at all.

It exists because this course has a wide spread of mathematical backgrounds. Some of you have a full probability sequence behind you and can skim or skip this entirely. Others last saw a standard deviation in school. Lecture 8’s chapter 5 is the most mathematical stretch of Act 3, and it is meant to be understood, not survived — so if a symbol there ever felt like it was doing more work than you could follow, the unpacked version is here.

A promise in the same spirit as Appendix A: none of this is mandatory, and none of it is on any exam. The exam asks you to read a benchmark number critically — to know which questions to ask and why a reported “Pass@1” can be underdefined. This appendix is the scaffolding behind that skill; once the skill is yours, the scaffolding can come down. It also pays forward: the same machinery returns in Lecture 9, where uncertainty meets cost, and in the course finale, where the metric of interest flips from pass@k to its mirror.

We build these ideas up in dependency order, one chapter at a time, then put them together on the one example the whole of chapter 5 is about — pass@k — and close with a one-page cheat-sheet keyed back to where each symbol appears in the lecture.

2. Randomness: A Sample Is Not a Property

Start with the single idea the rest of the appendix decorates. When you run a model on a task and it either passes or fails, you have not measured a fixed property of the model — you have observed one outcome of a random experiment. Run it again and the outcome can flip.

The clean abstraction for “an experiment with two outcomes” is the Bernoulli trial: a single yes/no draw that comes up “success” with probability \(p\) and “failure” with probability \(1-p\). For a fixed model, a fixed task, and a fixed sampling configuration, “does one sampled attempt pass the tests?” is exactly a Bernoulli trial, and the per-task success probability \(p\) is the thing you actually care about:

The number \(p\) is a property of the model–task–configuration triple. A single run is a sample from it. The two are different kinds of object — one is a fixed (unknown) constant, the other is a coin flip whose bias is that constant — and the original sin of benchmark reading, as Lecture 8 §3.1 puts it, is confusing the two. Everything below is machinery for recovering the property \(p\) (and functions of it) from a finite handful of samples, with honesty about how much the handful actually tells you.

We call the unknown-but-fixed quantity a parameter (here \(p\)) and any number we compute from the observed samples a statistic (for example, the fraction that passed). Statistics estimate parameters; the whole subject is the relationship between the two.

3. Expectation: The Average, in Two Senses

The expectation (or expected value, or mean) of a random quantity is its long-run average over many independent repetitions, weighting each possible value by how probable it is. For a quantity \(X\) that takes value \(v\) with probability \(\Pr[X = v]\),

For a Bernoulli trial scored as 1 (pass) or 0 (fail), this is just \(\mathbb{E}[X] = 1 \cdot p + 0 \cdot (1-p) = p\). The expected value of a single pass/fail is the success probability itself — which is why “average the pass/fails” is a sensible way to estimate \(p\).

The one property of expectation you must keep is linearity: for any quantities \(X\) and \(Y\) and constants \(a, b\),

and crucially this holds whether or not \(X\) and \(Y\) are independent. Averages of sums are sums of averages, always. (Variance, the next chapter, is the opposite: it only adds nicely when the parts are independent.)

3.1 The trap: two different averages wear the same symbol

Here is the distinction that trips people in Lecture 8 §5.3, and it is worth meeting slowly. The symbol \(\mathbb{E}\) gets used for two genuinely different operations:

1. Expectation over randomness. Average over the possible outcomes of an experiment you could re-run — for example, over all the ways \(n\) sampled completions could turn out. This is the \(\mathbb{E}\) in “the estimator is unbiased”: it is a statement about what happens on average across hypothetical repeats of the sampling.
2. Average over a fixed set. The plain arithmetic mean of numbers you already hold — for example, the per-task scores across the \(N\) tasks of a benchmark. Nothing random is left; you are just adding and dividing.

When Lecture 8 writes \(\mathbb{E}_{\text{tasks}}[\,\cdot\,]\), the subscript is telling you it means sense (2): the average over the benchmark’s tasks. Given the data, that quantity is fully deterministic — it is literally

for the per-task numbers \(g_1, \dots, g_N\). The randomness — and the word unbiased — lives one level down, inside how each \(g_i\) was computed from its task’s random samples. Keep the two senses on separate shelves and chapter 5 stops being slippery: the bias arguments are about sense (1), per task; the final benchmark score is sense (2), an average over tasks.

4. Variance, Standard Deviation, and Standard Error

Expectation says where a random quantity sits on average. Variance says how far it typically strays from there. It is the expected squared distance from the mean:

Its square root, the standard deviation \(\sigma = \sqrt{\operatorname{Var}(X)}\), is back in the original units and is the everyday “give or take” of the quantity. For a Bernoulli trial with success probability \(p\), a short calculation gives

which is largest at \(p = 0.5\) (a fair coin is the least predictable) and shrinks to zero as \(p\) approaches 0 or 1 (a near-certain outcome barely varies).

4.1 Averaging shrinks the wobble: the standard error

Now the fact that powers all of Lecture 8 §5.4. When you average \(N\) independent draws, the average is far steadier than any single draw. For independent draws, variances add, so the variance of the sum of \(N\) draws is \(N\) times one draw’s variance; the average divides by \(N\), and variance scales by the square of a constant (multiply a quantity by \(a\) and its variance multiplies by \(a^2\)), so the average’s variance is \(\operatorname{Var}(X)/N\). Taking the square root gives the standard error — the standard deviation of an average:

Read that formula slowly, because it is the whole reason small benchmarks are noisy. The error shrinks only as \(\sqrt{N}\): to halve your uncertainty you need four times the tasks. At a 60-task benchmark near \(p = 0.5\), \(\text{SE} \approx \sqrt{0.25/60} \approx 0.065\) — about 6.5 percentage points of wobble in the headline number from sampling alone. Two models reported five points apart on such a benchmark can be statistically indistinguishable. And no number of extra samples per task fixes this: that tightens each per-task estimate, but the across-task term is fixed by \(N\), the count of tasks.

4.2 Comparing two scores adds two noises

A leaderboard’s real claim is “A beats B” — a statement about a difference. For two independent scores the variance of the difference is the sum of the variances, so its standard error is

A gap needs to clear roughly \(\sqrt{2}\) times the single-score error before it means anything. (When both models are graded on the same tasks their scores are positively correlated, which makes the honest difference-error smaller than \(\sqrt{2}\,\text{SE}\) — so treat \(\sqrt{2}\,\text{SE}\) as a conservative ceiling and reach for a paired test when a ranking truly hangs on it.)

5. The Binomial Distribution

Run \(n\) independent Bernoulli trials, each with success probability \(p\), and count how many succeed. That count \(c\) is a binomial random variable. Its distribution answers “what is the chance of exactly \(c\) successes out of \(n\)?”:

Three pieces, each worth naming. The \(p^{c}(1-p)^{n-c}\) is the probability of one particular sequence with \(c\) successes and \(n-c\) failures. The binomial coefficient

counts how many such sequences there are — the number of ways to choose which \(c\) of the \(n\) trials were the successes. Multiply “how many arrangements” by “probability of each” and you have the total. The binomial’s mean is \(np\) and its variance is \(np(1-p)\) — exactly \(n\) copies of the single-trial mean and variance, as linearity and independent-variance-addition promise.

The binomial coefficient is also a pure counting tool, divorced from probability, and that is the guise it wears in Lecture 8 §5.3’s unbiased pass@k estimator. There, \(\binom{n}{k}\) counts the ways to choose \(k\) samples out of your \(n\), and \(\binom{n-c}{k}\) counts the ways to choose \(k\) of them entirely from the \(n-c\) failures; the ratio is the probability that a random \(k\)-subset misses every correct sample. Same coefficient, used to count subsets rather than sequences.

6. Convexity and Jensen’s Inequality

A function \(f\) is convex if its graph bends upward — formally, the straight chord joining any two points on the graph lies on or above the graph between them. \(x^2\), \(e^{x}\), and \((1-x)^k\) for \(k > 1\) are convex; a straight line is the boundary case (convex and concave, with chord equal to graph); \(\sqrt{x}\) and \(\log x\) bend the other way and are concave.

Convexity has a probabilistic consequence that does a lot of work in Lecture 8 §5.2. Jensen’s inequality says that for a convex \(f\) and any random \(X\),

The picture is the whole proof. The mean \(\mathbb{E}[X]\) sits somewhere in the spread of \(X\)’s values; running each value through the upward-bending \(f\) and then averaging lands you on a chord, which sits above the curve; while \(f(\mathbb{E}[X])\) is the point on the curve directly above the mean. Chord above curve: \(\mathbb{E}[f(X)] \ge f(\mathbb{E}[X])\). The gap between the two sides is the bias that curvature manufactures out of spread — and it is roughly \(\tfrac{1}{2} f’’(\mathbb{E}[X])\operatorname{Var}(X)\): the more the function bends (\(f’’\)) and the more \(X\) wobbles (\(\operatorname{Var}\)), the larger the gap. For a straight line \(f’’ = 0\) and there is no gap at all, which is why the bias in chapter 5 vanishes at \(k = 1\), where the estimator is linear.

This is the engine behind “noise in, bias out”: push a noisy-but-fair estimate through a curved function and the output is no longer fair — it is systematically pulled to one side, and which side is decided by which way the function bends.

7. Estimators: Bias, Variance, and Unbiasedness

An estimator is a recipe that turns observed data into a guess at an unknown parameter. The fraction that passed, \(\hat{p} = c/n\), is an estimator of \(p\). The hat is the convention for “an estimate of the thing under the hat.” Estimators are themselves random — feed them a different random sample and they return a different number — so they have a distribution, with a mean and a variance, and we judge them by two separate questions.

Bias asks: on average, does it land on the truth? The bias of an estimator \(\hat\theta\) of a parameter \(\theta\) is \(\mathbb{E}[\hat\theta] - \theta\), the expectation taken over repeated sampling. An estimator is unbiased when that gap is zero — it is centred on the truth, even if any single estimate misses. Variance asks the other question: how much does it bounce around from sample to sample? These are independent virtues. An estimator can be unbiased but wildly noisy, or low-variance but reliably wrong; the dream is both.

\(\hat{p} = c/n\) is unbiased for \(p\): since \(c\) is binomial with mean \(np\), \(\mathbb{E}[\hat{p}] = np/n = p\). The trouble in Lecture 8 §5.2 is that pass@k does not report \(\hat{p}\) — it reports a curved function of it, \(1 - (1-\hat{p})^k\). Even though \(\hat{p}\) is unbiased, Jensen guarantees the curved function is not, and the previous chapter’s gap formula says by how much. This is the plug-in (or naive) estimator: estimate the parameter, then shove the estimate through the formula you wanted. Plug-in is fine for linear formulas and biased for curved ones.

7.1 The fix, and why it is “without replacement”

The Codex paper’s unbiased pass@k estimator (Lecture 8 §5.3) sidesteps the curve entirely by asking the pass@k question directly of the samples. Among your \(n\) samples, look at all \(\binom{n}{k}\) ways to pick a \(k\)-subset; the fraction of those subsets that are all-failures is an exact, unbiased estimate of “all \(k\) tries miss.” The subtle point is with vs. without replacement. The naive formula \((1-\hat p)^k\) implicitly imagines drawing \(k\) samples with replacement — as if each of the \(k\) attempts were an independent fresh coin flip at rate \(\hat p\). But your \(k\) real attempts would be \(k\) distinct samples drawn without replacement from a finite pool. Counting \(k\)-subsets honours that distinctness, and honouring it is exactly what removes the bias.

7.2 The delta method, in one line

When you cannot avoid pushing a noisy estimate through a function \(g\), the delta method estimates the damage. A second-order Taylor expansion around the true value gives, to leading order,

so the bias is about \(\tfrac{1}{2} g’’(\theta)\operatorname{Var}(\hat\theta)\) — curvature times wobble, the same product Jensen described. For pass@2, \(g(x) = 1-(1-x)^2\) has \(g’’ = -2\), and the bias works out to exactly \(-\operatorname{Var}(\hat p) = -p(1-p)/n\): the naive estimate sits below the truth by precisely the variance of \(\hat p\). That is the exact number Lecture 8 §5.2 quotes, now with its derivation.

8. From One Number to a Range: CLT, Confidence Intervals, the Bootstrap

A point estimate without an uncertainty is half a measurement. Three tools turn a single number into an honest range.

8.1 The central limit theorem

The central limit theorem (CLT) is the reason the normal “bell curve” is everywhere. It says that the average of many independent draws — whatever their individual distribution — is approximately normally distributed, centred on the true mean, with standard deviation equal to the standard error from earlier. A benchmark score is an average of \(N\) pass/fail outcomes, so for a decently sized \(N\) the score is approximately normal around the true pass rate with spread \(\text{SE} = \sqrt{p(1-p)/N}\). The CLT is what lets us attach a familiar “\(\pm\) so much” to a score at all.

8.2 Confidence intervals

A confidence interval is the “\(\pm\)” made precise. Leaning on the CLT, an approximate 95% interval for a proportion is

where 1.96 is the number of standard errors that brackets the central 95% of a normal curve. The honest reading of “95% confidence” is procedural, not psychological: if you repeated the whole experiment many times and built such an interval each time, about 95% of those intervals would contain the true \(p\). It is a statement about the reliability of the recipe, not the probability that this one interval is right. (Near \(p = 0\) or \(p = 1\), or at tiny \(N\), this normal approximation frays, and intervals like Wilson’s or Clopper–Pearson behave better — worth knowing the names exist.)

8.3 The bootstrap

When the quantity you care about is not a clean proportion — a difference, a ratio like “cost per solved task,” a pass@k estimate — the textbook interval formula may not exist. The bootstrap sidesteps the algebra with brute force: treat your sample as a stand-in for the population, resample it with replacement many times, recompute the statistic on each resample, and read the spread of those recomputed values directly off their histogram. A few lines make it concrete:

import numpy as np

# observed per-task pass/fail for one model on N tasks (1 = pass, 0 = fail)
results = np.array([1, 0, 1, 1, 0, 0, 1, 1, 1, 0, ...])  # length N
N = len(results)

boot_scores = []
for _ in range(10_000):
    resample = np.random.choice(results, size=N, replace=True)  # resample tasks
    boot_scores.append(resample.mean())                         # recompute the score

lo, hi = np.percentile(boot_scores, [2.5, 97.5])   # 95% bootstrap interval
print(f"score = {results.mean():.3f}, 95% CI = [{lo:.3f}, {hi:.3f}]")

The width of [lo, hi] is your error bar, obtained without a single formula — and it widens, visibly and correctly, as the task count \(N\) shrinks. Resampling tasks (not samples within a task) is the right move when the question is “how would this score move on a different draw of tasks from the same distribution,” which is usually the question a leaderboard’s ranking silently depends on.

9. Worked Thread: pass@k from the Ground Up

Everything above converges on the one object Lecture 8 chapter 5 dissects. Trace it once with the vocabulary now in hand.

1. A run is a Bernoulli trial. One sampled completion on one task passes with probability \(p\) — a parameter, not a property you can read off a single run.
2. \(n\) runs give a binomial count. Draw \(n\) completions, count \(c\) passes; \(c\) is binomial\((n, p)\), and \(\hat{p} = c/n\) is an unbiased estimate of \(p\) with standard error \(\sqrt{p(1-p)/n}\).
3. pass@k is a curved function of \(p\). The quantity of interest, \(1 - (1-p)^k\), bends; by Jensen the plug-in \(1 - (1-\hat p)^k\) is biased low, by about \(\lvert\tfrac{1}{2} g’‘\operatorname{Var}(\hat p)\rvert\) — exactly \(p(1-p)/n\) at \(k = 2\).
4. The combinatorial estimator is unbiased. Counting all-failure \(k\)-subsets, \(1 - \binom{n-c}{k}/\binom{n}{k}\), asks the pass@k question of the samples directly and draws without replacement, which removes the bias.
5. The benchmark score averages over tasks. \(\mathbb{E}_{\text{tasks}}[\,\cdot\,] = \tfrac{1}{N}\sum_i\) — sense (2) from the expectation chapter, deterministic given the data.
6. The score has an error bar. Across \(N\) tasks the standard error is \(\sqrt{p(1-p)/N}\) (or a bootstrap interval), and a model-to-model gap carries up to \(\sqrt{2}\) times that.

The homework notebook 08-notebook-passk-estimators walks this thread on simulated tasks where the true \(p\) is known — the one luxury a real benchmark never has — so you can watch the naive estimator drift off a known line while the unbiased one sits on it, and watch a bootstrap interval widen as you cut the task count. Reading this appendix and running that notebook are the two halves of the same lesson.

10. Cheat-Sheet: Symbols and Where They Appear

One page to keep beside Lecture 8 chapter 5.

That is the toolkit. With it, Lecture 8 §5.7’s four reviewer questions — which estimator, what sampling configuration, what standard error, what happens to a ratio as the denominator approaches zero — stop being statistics jargon and become a checklist you can actually run.