Foundations T13 / 27 · Probability and expectation
Probability spaces: why «random» needs axioms
Three answers to the same problem means not that math failed, but that «random» was never defined. Starting from Bertrand's paradox, this piece builds the sample space, the event collection, and the probability measure, one by one.
One-line takeaway
The probability axioms are not rigor for rigor's sake — their only reason to exist is to give everyday language like «pick a chord at random» a unique meaning, and to guarantee that limit operations never go wrong.
Reinforcement learning is full of phrases like «expected return» and «the distribution induced by the policy». If you cannot say which space these distributions live on or what the measure is, you cannot verify that a single later derivation does not quietly swap concepts. This piece introduces no RL content at all; it only levels the foundation.
Why this tool exists
In 1889 the French mathematician Bertrand posed a problem: draw a chord at random in a circle; what is the probability that its length exceeds the side of the inscribed equilateral triangle? He gave three equally «natural» solutions: the answers are 1/2, 1/3, and 1/4. All three answers used unimpeachable computations and contradict each other.
The problem is not in the computation but in the wording. «Draw a chord at random» never says what is random: the two endpoints of the chord? the chord's distance from the center? the position of the chord's midpoint inside the circle? Three readings correspond to three different random experiments, hence three different answers.
This problem forced probability theory to modernize in the 20th century: in 1933 Kolmogorov proposed that before talking about probability you must specify three things — the sample space, the event collection, and the probability measure. Together they are called a probability space. We build them one by one below, and at every step we say exactly which disease each piece guards against.
Definitions
Definition 1.1 Sample space and events (intuitive version)
The sample space Ω is the set of all possible outcomes of a random experiment. An event is a set of outcomes about which «did it happen» can be asked — a subset of Ω. Rolling a die, Ω={1,2,3,4,5,6}; «the face is even» = {2,4,6} is an event.
Definition 1.1 Sample space and events (rigorous version)
The event collection F is a family of subsets of Ω required to satisfy two closure properties: (1) if A∈F then the complement Ω\A∈F; (2) if A_1, A_2, … countably many sets all lie in F, then the union ∪A_n∈F. An F satisfying both is called a σ-algebra.
Why define it this wayClosure under complements lets you ask «did not happen»; closure under countable unions lets you ask «happens at least once in infinitely many trials» — the latter is the prerequisite for any limit discussion, such as events like «the episode never terminates». An algebra that only requires finite unions cannot do this.
Definition 1.2 Probability measure
P is a function on F taking values in [0,1] satisfying three axioms: (A1) P(A)≥0; (A2) P(Ω)=1; (A3) countable additivity — if A_1, A_2, … are pairwise disjoint, then P(∪A_n) = Σ P(A_n).
Why define it this wayA3 is the heart of the whole axiom system and its strongest clause. It governs both finite sums (set A_2=A_3=…=∅) and limit operations (see Theorem 1.3 below). Historically it cannot be downgraded to «finite additivity»; the Bertrand-style ambiguity is precisely removed by making Ω and F explicit.
Theorems and proofs
Theorem 1.1 The inclusion–exclusion formula
For any A, B∈F: P(A∪B) = P(A) + P(B) − P(A∩B).
Proof
Split A∪B into three pairwise disjoint pieces: A\B, A∩B, B\A. By the finite special case of countable additivity (axiom A3 with all remaining sets empty):
Meanwhile P(A) = P(A\B) + P(A∩B) and P(B) = P(B\A) + P(A∩B). Adding the two: P(A)+P(B) = P(A\B) + P(B\A) + 2P(A∩B).
Substitute the first line's expression and you get exactly P(A∪B) = P(A)+P(B) − P(A∩B). ∎
NoteThe proof uses only one maneuver: split into disjoint pieces and add. This trick appears in probability theory often enough to be boring — including solving the stationary distribution equations in piece 6 later.
Theorem 1.2 Monotonicity
If A⊂B, then P(A) ≤ P(B), and P(B\A) = P(B) − P(A).
Proof
B = A ∪ (B\A), with the two parts disjoint. By finite additivity: P(B) = P(A) + P(B\A).
By axiom A1, P(B\A) ≥ 0, so P(B) ≥ P(A). Rearranging gives the second identity. ∎
Note«Bigger sets have bigger probability» looks obvious intuitively, but strictly it is a corollary of A1+A3. Even the intuitively obvious parts need a provenance — that is the dividing line between the principles layer and the derivation layer.
Theorem 1.3 Continuity of probability
If A_1 ⊃ A_2 ⊃ … is decreasing and A = ∩A_n, then P(A_n) ↓ P(A). The increasing version holds symmetrically.
Proof
The key step: rewrite the decreasing sequence as a disjoint one. Let B_1 = A_1 and B_n = A_n \ An+1 (n≥2). Each B_n is the part «lost at this layer»; they are pairwise disjoint and ∪B_n = A_1.
The second equality peels off the first k terms. For n>k we have B_n ⊂ Ak+1 ⊂ A_k, and the B_n fill Ak+1\A disjointly, so Σn=k+1∞ P(B_n) = P(Ak+1) − P(A).
Rearranging gives P(A_k) = P(A_1) − [P(A_1) − P(A)]. Letting k→∞ needs Σn=k+1∞ P(B_n) → 0: this is the remainder property of a convergent positive-term series, and convergence of the series is guaranteed by P(A_1) ≤ 1 (all partial sums ≤ P(A_1) ≤ 1). Hence P(A_k) ↓ P(A). ∎
NoteNotice that the axiom actually doing the work is A3 (countable additivity) — under finite additivity alone this theorem fails; counterexamples exist. That is why the axiom is written in countable form: probability theory must handle limits, and finite additivity is not enough.
Work it by hand
Flip a fair coin repeatedly until the first heads appears. Use the axiom system to find the probability P_odd that «the number of flips is odd».
- Sample space Ω = {1, 2, 3, …} (the counts); the event «odd number» = {1, 3, 5, …}, a countable union of singletons.
- The probability that heads first appears on flip k: tails on the first k−1 flips and heads on flip k = (1/2)k-1 · (1/2) = (1/2)^k.
- «Odd number» is the union of the pairwise disjoint events {1}, {3}, {5}, … By axiom A3 (countable additivity):
- [object Object]
- Check axiom compliance: Σ over all k of (1/2)^k = 1, i.e. P(Ω)=1 (axiom A2 holds) — this check is not formalism; omitting the «never terminates» event when summing a geometric distribution is a common error, and the axioms force you to check it.
P_odd = 2/3 ≈ 0.6667. Note which axiom each step used: splitting into disjoint events used A3; summing the series used the geometric series formula; the final compliance check used A2. The RL counterpart of this problem: episode lengths are random, and every «average per episode» computation draws its legitimacy from this kind of countable decomposition.
Run the numbers
Where the numbers come from
Three solutions to Bertrand's paradox, each run for 200,000 Monte Carlo trials (circle radius 1, inscribed equilateral triangle side √3, criterion: chord length > √3):
- Solution 1 (endpoints uniform and independent on the circumference) → probability 0.3322 ≈ 1/3
- Solution 2 (the chord's distance from the center uniform on [0,1]) → probability 0.4995 ≈ 1/2
- Solution 3 (the chord's midpoint uniform in the disk) → probability 0.2505 ≈ 1/4
Where this shows up
| The object here | The counterpart in RL | Used in |
|---|---|---|
| Sample space Ω | A full trajectory τ = (s_0, a_0, r_1, s_1, a_1, …, s_T) | used in → |
| Event A ⊂ Ω | Propositions like «return exceeds a threshold» or «episode terminates within 100 steps» | — |
| Probability measure P | The trajectory distribution P_τ induced jointly by policy π and dynamics p(s'|s,a) | used in → |
| Countable additivity | Decomposing trajectories by length or by first arrival time at a state and summing | used in → |
Boundaries: where this article stops
Where this piece stops: how σ-algebras are generated (the Borel σ-algebra generated by open sets), measure extension (Carathéodory), and the existence of non-measurable sets — none covered. Probability on continuous state spaces entirely takes the «density function» route to bypass these constructions — sufficient, but be honest that this is a bypass, not that the constructions do not exist.
Self-test: 4 questions
All hand-computation and «find the flaw in this proof» questions — nothing to memorize. Stuck? Go back to the section.
01In Bertrand's paradox the three answers contradict each other — which one is wrong?
None of them. All three computations are correct; the fault is in the problem statement — «draw a chord at random» never specifies the random mechanism, and the three mechanisms correspond to three different probability spaces (Ω, F, P). The way to dissolve the contradiction is not to pick the right one but to make the space explicit.
02Why does axiom A3 require countable additivity — is finite additivity not enough?
Not enough. The proof of Theorem 1.3 (continuity of probability) uses countable additivity directly — it is the foundation for handling «infinitely many trials» problems. Under finite additivity alone, continuity has counterexamples, and in RL «the episode eventually terminates» and «the limit of the return» are all problems of this kind.
03When does P(A∪B) = P(A) + P(B) hold?
When A∩B = ∅ (mutually exclusive), as the degenerate case of the inclusion–exclusion formula. Classic interview trap: before adding the probabilities of the before and after events of a policy improvement, confirm mutual exclusivity — otherwise you must subtract P(A∩B).
04Flip a coin until the first heads; what is the probability that «the number of flips is even»? Justify with the axioms why your addition is legal.
P_even = Σj≥1 (1/2)2j = (1/4)/(1−1/4) = 1/3. Legality: the events {2},{4},… are pairwise disjoint, so axiom A3 allows adding the probabilities; check P_odd + P_even = 2/3 + 1/3 = 1 = P(Ω) (A2), nothing missed.