A measure-theoretic aside
Everything so far has quietly assumed that a probability can be assigned to every set we care about. On a finite sample space that is true, and on the real line it is true for every set you will ever name — intervals, unions of intervals, the strange-looking sets a limit produces. It is not true for every subset. There exist collections of points so entangled that no assignment of probabilities can be both translation-invariant and additive, and the resolution is not to patch the assignment but to restrict the domain: a probability is defined on a chosen family of events, closed under the operations we actually perform. This part explains that restriction, builds the machinery of filtrations that lets us talk about information arriving over time, and closes with the Borel–Cantelli lemmas, the sharpest statement in the volume about whether an event happens infinitely often.
The question
The domain of a probability
The three axioms of Part 1 described a function P on "events", and we treated an event as any subset of the sample space. For finite spaces that is harmless: if the space has n outcomes, there are 2^n subsets and we can assign each a probability. Even for a continuous space like the unit interval the naive rule "probability equals length" works on intervals, and extends to anything you can build from intervals by countable unions, intersections and complements. That family is enormous; it contains every set you have ever met.
It does not contain every set, and no extension to every set can satisfy the axioms while also respecting the geometry of length. The obstruction is a construction, not an oversight: one can partition the unit circle into countably many pieces that are rigid rotations of one another, and if each piece had a length, all the lengths would be equal and they would have to sum to the circumference. An infinite sum of equal positive numbers diverges; an infinite sum of zeros is zero. Neither equals the total, so some piece must have no length at all. Such a set exists, is perfectly well defined, and simply cannot be assigned a probability.
The response of measure theory is to make the domain part of the definition. A probability space is a triple $(\Omega,\mathcal{F},P)$: a sample space, a family $\mathcal{F}$ of subsets called events, and a function P on that family. The family is required to be a σ-algebra — closed under complement and countable union — so that the operations the axioms talk about never leave the family. The remaining sets are not "improbable"; they are not events at all. Nothing in this volume's practical work ever bumps into them, which is why the caveat can be stated once and set aside.
Sets without a probability
A construction, not an accident
Put the sample space on a circle of circumference one and define two points to be equivalent when one is a rational rotation of the other — that is, when their difference is a rational fraction of the circumference. Each equivalence class is a countable set of points spread densely around the circle. The axiom of choice lets us pick exactly one representative from each class; call the resulting set V. This is the Vitali set, and the argument against assigning it a length runs as follows.
Take all rational rotations of V by the fractions q in [0,1). There are countably many of them, they are pairwise disjoint, and together they cover the whole circle — because every point is in some class and differs from that class's chosen representative by a rational rotation. Rotation preserves length, so if V had a length $\ell$, every translate would have length $\ell$ too. Countable additivity would then force the total, one, to equal the sum of countably many copies of $\ell$. If $\ell>0$ the sum is infinite; if $\ell=0$ it is zero. Neither is one. So V has no length, and no consistent extension of length to all subsets exists.
One equivalence class on the circle (oranges) and one chosen representative (ringed). The button rotates the whole class by successive rational steps; the class fills the circle ever more densely but never overlaps itself.
The lesson is not that the construction is exotic but that measurability is a real hypothesis. Every function and set in the rest of this guide is measurable, and the classes of sets that matter — intervals on the line, rectangles in the plane, cylinder sets on a sequence space — generate σ-algebras large enough for every limit the theory needs. The Borel sets, the smallest σ-algebra containing the open sets, are the default: big enough to be closed under every countable operation, small enough to avoid the pathology above.
σ-algebras as questions
A family of yes/no questions
A cleaner way to read a σ-algebra is as the set of yes/no questions an observer is allowed to ask about the outcome. On a finite space, if the observer can only distinguish the outcomes within certain groups, then the questions they can answer form exactly a σ-algebra, and every such algebra arises from a partition: you are told which block of the partition the outcome landed in, and nothing finer.
The smallest σ-algebra is $\{\varnothing,\Omega\}$ — the partition with one block, no information at all. The largest is the power set — every block a singleton, full information. Between them sit all the partitions, and the size of the algebra is 2^k where k is the number of blocks. A random variable is said to be measurable with respect to an algebra when its value is constant on each block: you can determine it from the answers the algebra allows.
Each cell is a subset of $\Omega=\{1,2,3,4\}$. Highlighted cells are the events the chosen algebra can express; the rest are questions you are not allowed to ask.
This is why the definition of a random variable is phrased as a measurability condition rather than a table of values. A random variable is a function whose level sets are events: you can ask "is $X\le x$?" for every x, and the answer is an event in $\mathcal{F}$. Conditional expectation is the same idea run backwards: $\mathbb{E}[X\mid\mathcal{G}]$ is the best approximation to X that is measurable with respect to the coarser algebra $\mathcal{G}$, and it is constant on each of $\mathcal{G}$'s blocks.
Filtrations and information
Knowledge that grows with time
A filtration is an increasing sequence of σ-algebras $\mathcal{F}_0\subseteq\mathcal{F}_1\subseteq\mathcal{F}_2\subseteq\cdots$, one per time step, where $\mathcal{F}_t$ contains every question answerable from the information available at time t. It is the formal counterpart of "what do I know now", and it is the object every sequential method in this guide implicitly uses: the state estimate in a filter is measurable with respect to the flips and measurements seen so far, and nothing else. A stopping time is a random time whose occurrence you can recognise from the filtration — you know it has happened the moment it happens, without peeking ahead. Optional stopping in Part 9 of the companion volume is a statement about stopping times.
Reveal the flips one at a time. Rows are the possible prefixes; the number in each row is $\mathbb{E}[X\mid\mathcal{F}_t]$, the expected total number of heads given the prefix so far.
Watch how the conditional expectation behaves as information arrives. Before any flip it is the overall mean 5p. After each reveal it jumps, because the revealed flips are now known and the remaining ones still carry expectation p each. This is a martingale: the expected value tomorrow, given everything known today, is today's value. The running estimate of a fair coin's bias in the companion volume is the same object, and the fact that it does not drift is what makes optional stopping work.
Borel–Cantelli
Happening infinitely often
Write $\{A_n\text{ i.o.}\}$ for the event that infinitely many of the events A_n occur. The two Borel–Cantelli lemmas bracket this event using only the sum of the probabilities. If $\sum_n P(A_n)<\infty$ then almost surely only finitely many occur, so $P(A_n\text{ i.o.})=0$, and no independence is needed. If the A_n are independent and $\sum_n P(A_n)=\infty$, then almost surely infinitely many occur, and the probability is one.
The 1/$n^\alpha$ family is the cleanest illustration. With $P(A_n)=n^{-\alpha}$, the sum converges when $\alpha>1$ and diverges when $\alpha\le 1$, so the threshold between finitely many and infinitely many occurrences sits exactly at one. Independence is essential for the converse direction: infinitely many occurrences of events each of probability 1/n can still fail if the events are nested, which is why the first lemma needs no independence and the second does.
The bars are the individual $P(A_n)=n^{-\alpha}$; the curve is their running sum. Simulate the independent events and count how many occur.
Where this shows up
The hypotheses under the theorems
The law of large numbers
The almost-sure statement in Part 17 is a statement about a limit of random variables, and both sides must be measurable with respect to the same σ-algebra for the statement to even parse. Filtrations are what make the running average a well-defined process rather than a sequence of unrelated questions.
Recursive estimation
Every filter in the companion volume conditions on the history of measurements: the belief at time t is the conditional distribution given $\mathcal{F}_t$. The odometry recursion is the Markov assumption — that $\mathcal{F}_t$ can be summarised by the current state — written as a probabilistic model.
Almost-sure guarantees
Concentration results behind generalisation bounds are tail statements of the kind Borel–Cantelli upgrades to a statement about all but finitely many training runs — the difference between "unlikely this time" and "eventually never". The scaling discussion in LLM Training leans on those tail estimates.
Integration
The integral that gives a continuous probability its meaning is the Lebesgue integral, defined by partitioning the range rather than the domain. It is the construction that makes every density in Part 10 and Part 11 an honest average, and it is why measurability is a hypothesis rather than a formality.
Cheat sheet
Every formula in one place
| Idea | Statement | Reading |
|---|---|---|
| Probability space | $(\Omega,\mathcal{F},P)$ | Outcomes, allowed events, and the measure on them. |
| σ-algebra | $\Omega\in\mathcal{F}$; closed under complement and countable union | The questions you may ask about the outcome. |
| Generated algebra | $\sigma(\mathcal{C})$ is the smallest σ-algebra containing $\mathcal{C}$ | Everything forced by the sets you started with. |
| Borel sets | smallest σ-algebra containing the open sets | The default domain on $\mathbb{R}^n$. |
| Measurable function | $\{X\le x\}\in\mathcal{F}$ for all x | A random variable: a question whose answers are events. |
| Conditional expectation | $\mathbb{E}[X\mid\mathcal{G}]$ is $\mathcal{G}$-measurable | Best guess using only the coarser information. |
| Filtration | $\mathcal{F}_0\subseteq\mathcal{F}_1\subseteq\cdots$ | What is known at each time. |
| Stopping time | $\{\tau\le t\}\in\mathcal{F}_t$ | A random time you can recognise on arrival. |
| Martingale | $\mathbb{E}[X_{t+1}\mid\mathcal{F}_t]=X_t$ | A fair game: no expected drift. |
| Borel–Cantelli I | $\sum P(A_n)<\infty\Rightarrow P(A_n\ \text{i.o.})=0$ | Summable probabilities happen finitely often. |
| Borel–Cantelli II | $\sum P(A_n)=\infty$ and independent $\Rightarrow P(A_n\ \text{i.o.})=1$ | Divergent independent probabilities happen forever. |
Further reading
Where to go deeper
- Andrey Kolmogorov, Foundations of the Theory of Probability, 1933 — the measure-theoretic axioms in their original form.
- Patrick Billingsley, Probability and Measure, 3rd edition — the standard reference; the Vitali argument and Borel–Cantelli are in the early chapters.
- David Williams, Probability with Martingales, 1991 — filtrations, conditional expectation and martingales developed exactly as this part sketches them.
- Rick Durrett, Probability: Theory and Examples, chapter 2 — Borel–Cantelli with a large collection of worked examples and counterexamples.
- Terence Tao, "Lebesgue measure", 2010 — lecture notes that build the non-measurable set carefully.