Kolmogorov's axioms

Counting gives probabilities only when the outcomes are equally likely and finitely many. A loaded die breaks the first condition, a random point on a segment the second, and the time until the first head in a run of coin flips has infinitely many outcomes that are not equally likely. In 1933 Kolmogorov replaced the definition by three axioms: a probability is any function on events that obeys them. Counting is one example; every other rule of the course is a consequence. This note states the axioms, derives the rules that the counting note used without proof, and explains the one technical point, which sets of outcomes count as events.

Notation. $\Omega$ is the sample space, $\mathcal F$ the collection of events (subsets of $\Omega$ that get a probability), $P$ the probability. Events $A_1, A_2, \dots$ are disjoint if no two of them can happen together, $A_i \cap A_j = \varnothing$ for $i \ne j$. $A \setminus B$ is ”$A$ but not $B$”.

Three axioms#

A probability space is a triple $(\Omega, \mathcal F, P)$ in which $P$ assigns a number to every event and

1. $P(A) \ge 0$ for every event $A$;
2. $P(\Omega) = 1$;
3. for disjoint events $A_1, A_2, \dots$, finitely or countably many,

$$P\Big(\bigcup_i A_i\Big) = \sum_i P(A_i) .$$

The axioms say nothing about what a probability means. A share of equally likely outcomes, a long-run frequency and a degree of belief all satisfy them, which is why one calculus serves all three readings of the opening note.

On a finite or countable $\Omega$ the axioms reduce to one recipe: give each outcome a weight $p_\omega \ge 0$ with $\sum_\omega p_\omega = 1$ and set $P(A) = \sum_{\omega \in A} p_\omega$. A loaded die is the weights $(0.1, 0.1, 0.1, 0.1, 0.1, 0.5)$; the classical model is the special case of equal weights. Flip a fair coin until the first head: the head comes at flip $k$ with probability $2^{-k}$, and the weights $\frac12 + \frac14 + \frac18 + \dots$ add up to 1. The probability that the first head comes at an even flip is

$$\frac14 + \frac1{16} + \frac1{64} + \dots = \frac{1/4}{1 - 1/4} = \frac13 .$$

The event “even flip” is a union of infinitely many disjoint outcomes, and only countable additivity, the third axiom applied to infinitely many events, turns the sum of their probabilities into the probability of the union.

The rules that follow#

• Complement. $A$ and $A^c$ are disjoint and make up $\Omega$, so $P(A^c) = 1 - P(A)$, and $P(\varnothing) = 0$.
• Monotonicity. If $A \subseteq B$, then $B$ is $A$ plus the disjoint piece $B \setminus A$, so $P(A) \le P(B)$ and every probability is at most 1.
• Union of two events. $A \cup B$ splits into $A$ and $B \setminus A$, and $B$ into $A \cap B$ and $B \setminus A$; subtracting gives

$$P(A \cup B) = P(A) + P(B) - P(A \cap B) .$$

• Union bound. Dropping the last term, $P(A \cup B) \le P(A) + P(B)$, and by induction $P(A_1 \cup \dots \cup A_n) \le \sum_i P(A_i)$, for any events, dependent or not.
• Continuity. If $A_1 \subseteq A_2 \subseteq \dots$, then $P(\bigcup_n A_n) = \lim_n P(A_n)$: write the union as the disjoint rings $A_n \setminus A_{n-1}$. The probability of getting a head at some point is the limit of $P(\text{a head in } n \text{ flips}) = 1 - 2^{-n}$, which is 1.

The complement rule is the most used shortcut in the course. In the 17th century the Chevalier de Méré noticed that betting on at least one six in 4 rolls of a die won, and betting on at least one double six in 24 rolls of two dice lost, although $4/6 = 24/36$. Through the complement:

$$1 - \left(\tfrac56\right)^4 = 0.5177, \qquad 1 - \left(\tfrac{35}{36}\right)^{24} = 0.4914 .$$

The product of the probabilities of “no six” on each roll uses independence, which the next note defines; the complement turns “at least one”, a union of many overlapping events, into “none”, a single intersection.

Inclusion–exclusion#

For three events the union formula picks up one more correction:

$$P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A \cap B) - P(A \cap C) - P(B \cap C) + P(A \cap B \cap C) .$$

The figure shows why each term is there: after each step, the number in a region says how many times its probability has been counted.

Figure

Inclusion–exclusion for three events

For $n$ events the pattern continues with alternating signs: add the single events, subtract all pairwise intersections, add all triple intersections, and so on. A point that lies in exactly $m$ of the events is counted $\binom m1 - \binom m2 + \binom m3 - \dots = 1$ time.

Nobody draws their own name. $n$ people put their names in a hat and each draws one at random (a Secret Santa). What is the probability that nobody draws their own name? Let $A_i$ be “person $i$ draws their own name”. Any $k$ given people all draw their own names in $(n-k)!$ of the $n!$ equally likely orders, and there are $\binom nk$ ways to choose the $k$ people, so the $k$-th term of inclusion–exclusion is $\binom nk \frac{(n-k)!}{n!} = \frac1{k!}$:

$$P(\text{nobody}) = 1 - P\Big(\bigcup_i A_i\Big) = 1 - 1 + \frac1{2!} - \frac1{3!} + \dots \pm \frac1{n!} .$$

For 4 people this is $9/24 = 0.375$, and by 10 people it is $0.3679$ to four digits, the value of the limit $1/e$: the answer barely depends on the size of the group.

The union bound in practice#

The union bound is crude, but it needs no knowledge of how the events depend on each other, and that makes it the workhorse of guarantees. An A/B test reports 20 metrics, each tested so that a metric with no real effect raises a false alarm with probability 0.05. If the 20 tests were independent, the probability of at least one false alarm would be $1 - 0.95^{20} = 0.64$. Testing each metric at level $0.05/20 = 0.0025$ instead (the Bonferroni correction) guarantees by the union bound that the probability of any false alarm is at most $20 \cdot 0.0025 = 0.05$, however the metrics are correlated. The same argument, applied to the events “hypothesis $h$ looks good on the training data but is bad”, gives the first generalization bound of the concentration note.

Infinitely many outcomes#

Pick a point uniformly at random in $[0, 1]$. The natural probability of an interval is its length, $P([a, b]) = b - a$. Then every single point has probability 0, since $\{x\}$ lies in intervals of every small length, and still the point lands somewhere. Probability 0 does not mean impossible; it means that the event carries no weight. Countable additivity adds up countably many zeros: the set of rational numbers in $[0, 1]$ is countable, so a random point is rational with probability 0. The interval itself is uncountable, and the third axiom says nothing about uncountable unions, so there is no contradiction with $P([0, 1]) = 1$.

That a probability with $P([a, b]) = b - a$ exists at all, consistent with the axioms on every set built from intervals, is a theorem (the construction of the Lebesgue measure), not an obvious fact.

Why not every set is an event#

It would be convenient to give every subset of $[0, 1]$ a probability. For the uniform distribution it is impossible: there are sets so irregular that no value is consistent with the axioms and with the fact that shifting a set does not change its uniform probability. One is constructed below, for readers who want to see it.

The axioms therefore assign probabilities only to a family $\mathcal F$ of events, a σ-algebra: it contains $\Omega$, and it is closed under complements and countable unions, so that every event built from events by “not”, “or” and “and”, countably many times, is again an event. On $\mathbb R$ the standard choice is the Borel σ-algebra, the smallest one that contains all intervals. Every set that appears in practice, from a half-line to the set where a continuous function is positive, is a Borel set; sets like the one below need the axiom of choice to construct. The rest of the course keeps $\mathcal F$ implicit: every set it uses is an event.

A set with no probability#

Optional depth: the construction of a set that cannot be an event. The rest of the note does not depend on it.

Work on $[0, 1)$ and add modulo 1, so that a shift wraps around like a turn of a circle; a uniform probability does not change under such a shift. Call two numbers equivalent if their difference is rational, and build a set $V$ by picking one number from each equivalence class. For each rational $q \in [0, 1)$ let $V_q = \{(v + q) \bmod 1 : v \in V\}$. A point $x \in [0, 1)$ lies in exactly one copy: if $v$ is the representative of its class, then $x \in V_q$ only for $q = (x - v) \bmod 1$. So the countably many copies $V_q$ are disjoint and together cover $[0, 1)$, which has probability 1. A uniform probability must give every copy the same value $P(V)$, and countable additivity then makes $1 = P(V) + P(V) + \dots$, which is impossible whether $P(V)$ is zero or positive. So $V$ cannot be an event.

“At random” needs a model#

The axioms tell how probabilities combine, not which probabilities to assign, and an innocent phrase such as “a random chord” does not fix them. Bertrand asked in 1889: what is the probability that a random chord of a circle is longer than the side of the inscribed equilateral triangle? Three reasonable readings of “random” give three answers:

Figure

Bertrand's paradox: three ways to draw a "random chord"

Each answer is correct for its own probability space. The paradox is not a flaw in the axioms; it is the reason a model has to say how the randomness is generated. Jaynes later argued that only the answer $1/2$ is unchanged when the circle is moved or rescaled, which makes it the natural choice when nothing else is known, but that is an extra modelling principle, not a consequence of the axioms.

What changed#

	Counting	Kolmogorov’s axioms
Outcomes	finitely many, equally likely	any set $\Omega$
Probability of an event	$\lvert A \rvert / \lvert \Omega \rvert$	any $P$ with $P \ge 0$, $P(\Omega) = 1$, countable additivity
Loaded die, first head at flip $k$	not covered	weights $p_\omega$ summing to 1
Random point in $[0, 1]$	not covered	length of intervals; single points have probability 0
Which sets have a probability	all	the events of a σ-algebra

Limitations#

• The axioms do not choose the probabilities. Bertrand’s three answers all satisfy them; assigning probabilities to a real situation is a modelling decision.
• Countable additivity is an assumption. It is what makes limits work, and the whole course relies on it. De Finetti argued for requiring only finite additivity; then, for example, a “uniform distribution on the integers” exists, but limits of probabilities no longer behave.
• σ-algebras are bookkeeping in applied work. They matter for the construction of continuous distributions and of random processes; in the rest of the course every set that appears is an event.

What you should remember#

• A probability is any function on events with $P(A) \ge 0$, $P(\Omega) = 1$ and additivity over countably many disjoint events.
• Complement: $P(A^c) = 1 - P(A)$. Union: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$. Union bound: $P(\bigcup A_i) \le \sum P(A_i)$, for any dependence.
• Inclusion–exclusion alternates signs over intersections of 1, 2, 3, … events; the probability that nobody in a Secret Santa draws their own name tends to $1/e \approx 0.368$.
• With infinitely many outcomes single outcomes can have probability 0, and only the sets of a σ-algebra get probabilities.
• “At random” is not a model: Bertrand’s chord has probability $1/3$, $1/2$ or $1/4$ of being long, depending on how it is drawn.

Code#

Bertrand’s three chords, the Secret Santa problem and the other numbers of the note, in NumPy:

import numpy as np, math, itertools

rng = np.random.default_rng(0)
n = 100_000

# Bertrand's paradox: a chord of the unit circle is long if it is longer than sqrt(3)
t1, t2 = rng.uniform(0, 2 * np.pi, (2, n))
endpoints = 2 * np.abs(np.sin((t1 - t2) / 2))     # (a) both endpoints uniform on the circle
d = rng.uniform(0, 1, n)
radius = 2 * np.sqrt(1 - d**2)                    # (b) a uniform distance along a random radius
r = np.sqrt(rng.uniform(0, 1, n))
midpoint = 2 * np.sqrt(1 - r**2)                  # (c) the midpoint uniform in the disk
print([round(float((L > np.sqrt(3)).mean()), 3) for L in (endpoints, radius, midpoint)])   # [0.332, 0.501, 0.251]

# nobody draws their own name: inclusion-exclusion, enumeration, simulation
for k in [4, 10]:
    print(k, round(sum((-1)**j / math.factorial(j) for j in range(k + 1)), 4))           # 4 0.375, 10 0.3679
print(sum(all(p[i] != i for i in range(4)) for p in itertools.permutations(range(4))))  # 9 of 24 orders
perm = np.argsort(rng.random((n, 10)), axis=1)
print(round(float((perm != np.arange(10)).all(axis=1).mean()), 4))                      # 0.3707

print(round(1 - (5/6)**4, 4), round(1 - (35/36)**24, 4))          # 0.5177 0.4914  (de Mere)
print(round(1 - 0.95**20, 4), round(1 - (1 - 0.05/20)**20, 4))    # 0.6415 0.0488  (20 tests; Bonferroni)
print(sum(0.5**k for k in range(2, 100, 2)))                      # 0.3333333333333333  (first head at an even flip)

Next#

The axioms fix the probabilities of all events at once. In practice information arrives: a test comes back positive, the first card dealt is an ace, a user has already clicked. The next note defines the probability of an event given another one, derives Bayes’ formula from it, and makes the base-rate calculation of the opening note a two-line computation.

References#

• A. N. Kolmogorov. Grundbegriffe der Wahrscheinlichkeitsrechnung. Springer, 1933. English translation: Foundations of the Theory of Probability, Chelsea, 1956. Chapter I (the axioms), Chapter II (infinite probability fields).
• J. K. Blitzstein, J. Hwang. Introduction to Probability, 2nd ed. CRC Press, 2019. Chapter 1 (the general definition of probability, inclusion–exclusion, de Montmort’s matching problem).
• A. N. Shiryaev. Probability-1, 3rd ed. Springer, 2016. Chapter 2, §1–3 (Kolmogorov’s axioms, σ-algebras, measures on the real line).
• P. Billingsley. Probability and Measure, 3rd ed. Wiley, 1995. Chapter 1 (probability spaces, σ-fields, a nonmeasurable set).
• J. Bertrand. Calcul des probabilités. Gauthier-Villars, 1889. The random chord.
• E. T. Jaynes. The Well-Posed Problem. Foundations of Physics, 3(4), 1973.