Probability Spaces and Kolmogorov's Axioms: Probability as a Measure of Total Mass One

0. Key points

• Probability is nothing but a measure whose total mass is $1$. The triple $(\Omega, \mathcal{F}, P)$ consisting of a sample space $\Omega$, a family of events $\mathcal{F}$, and a probability measure $P$ is the starting point of all of probability theory.
• The family of events $\mathcal{F}$ cannot always be taken to be the collection of all subsets of $\Omega$. Vitali’s non-measurable set is the reason (see the Appendix). We must therefore restrict in advance the objects to which probabilities are assigned.
• There are only $3$ axioms (nonnegativity, total probability $1$, countable additivity). Monotonicity, the addition formula, subadditivity, and continuity from below and from above can all be proved from these $3$.
• Countable additivity is equivalent to “finite additivity $+$ continuity at the empty set”. This is the condition that allows us to speak of statements involving $n \to \infty$; with finite additivity alone no limit theorem can even be formulated.
• The conditional probability $P(\,\cdot \mid B)$ is itself a probability measure. Consequently every property we prove for probability measures is available for conditional probabilities as well, and Bayes’ theorem becomes a two-line computation on top of that fact.
• Independence is defined through products. For $3$ or more events, pairwise independence and independence of the family are different notions.

1. Motivation: why probability has to be a measure

Probability theory is usually dated to the $1654$ correspondence between Pascal and Fermat. The topic was the problem of points. Two players are betting, the agreement being that the first to win $3$ rounds takes the whole stake, but the game is interrupted at $2$ to $1$. How should the stake be divided? The two arrived at the solution of enumerating all possible continuations of the remaining rounds and dividing in proportion to the number of ways each player wins. Huygens set this idea down in $1657$ in On Reasoning in Games of Chance, and Jacob Bernoulli, in Ars Conjectandi ($1713$), reached the behaviour as the number of trials grows, that is, the first form of the law of large numbers.

Laplace’s classical definition generalizes such computations. If among $N$ “equally likely” cases the event $A$ occurs in $N_A$ of them, one sets

$$P(A) = \frac{N_A}{N}.$$

This definition breaks down in $2$ places.

First, it is circular. The phrase “equally likely” contains the word “likely”: probability is being used to define probability.

Second, and fatally, it is unusable when the number of cases is infinite. Consider the operation “pick a point at random from $[0,1]$”. Here $N = \infty$ and $N_A = 1$ for every single point, so the ratio loses its meaning.

1.1. Bertrand’s paradox

Bertrand showed in $1889$, in a strikingly clear way, what happens in the infinite case. Draw a chord “at random” in a circle of radius $1$. What is the probability that its length exceeds $\sqrt{3}$, the side of the inscribed equilateral triangle?

Measuring by the endpoints. Fix one endpoint of the chord and describe the position of the other endpoint by the central angle $\theta \in (0, 2\pi)$, chosen uniformly. The length of the chord is then $2\sin(\theta/2)$, so $2\sin(\theta/2) > \sqrt{3} \iff \sin(\theta/2) > \sqrt{3}/2 \iff \theta/2 \in (\pi/3, 2\pi/3) \iff \theta \in (2\pi/3, 4\pi/3)$. The ratio of interval lengths is $(2\pi/3)/(2\pi) = 1/3$.

Measuring by the radial position of the midpoint. Choose the distance $d$ from the centre to the midpoint of the chord uniformly on $[0,1]$. The length of the chord is $2\sqrt{1-d^2}$, so $2\sqrt{1-d^2} > \sqrt{3} \iff 1 - d^2 > 3/4 \iff d < 1/2$. The probability is $1/2$.

Measuring by the position of the midpoint in the plane. Choose the midpoint of the chord uniformly on the disc. The condition is again $d < 1/2$, but now we measure area, so the answer is $\pi (1/2)^2 / (\pi \cdot 1^2) = 1/4$.

One question, three answers: $1/3$, $1/2$, $1/4$. This is not a contradiction. It merely shows that the English phrase “draw a chord at random” can denote $3$ different mathematical operations. The lesson is plain: before speaking of probability we must specify to which sets, and with what weights, probability is assigned. The family of sets that receives the assignment, and the assignment itself, have to be set up as independent mathematical objects.

1.2. Infinitely many coin tosses

There is a second, decisive example: tossing a coin infinitely often. The set of outcomes is the uncountable set $\Omega = \{0,1\}^{\mathbb{N}} = \{\omega = (\omega_1, \omega_2, \ldots) : \omega_n \in \{0,1\}\}$. Each individual sequence $\omega$ must have probability $0$ (the probability that the first $n$ entries agree is $2^{-n}$, which tends to $0$ as $n \to \infty$). Yet the whole space has probability $1$. This situation — more than countably many outcomes of probability $0$ combining to probability $1$ — cannot be handled by adding up pointwise weights.

Moreover, what we really want to ask about this experiment concerns events involving limits, such as “the proportion of heads converges to $1/2$”. To handle those, the family of events must be closed under countable operations, and probability must be additive over countable unions (countable additivity). As we shall see, countable additivity is equivalent to interchanging probability with limits (Theorem 4.3), and this is exactly what bridges finitary probability computations and limit theorems.

1.3. Kolmogorov’s answer

In his sixth problem of $1900$, Hilbert called for an axiomatization of physics, probability theory included. After the work of Borel ($1909$, the theorem on normal numbers) and Lebesgue ($1902$, the theory of measure), the answer Kolmogorov gave in Grundbegriffe der Wahrscheinlichkeitsrechnung ($1933$) looks, in retrospect, almost anticlimactically brief.

Probability is a measure whose total mass is $1$.

That is, probability theory is a branch of measure theory, and its only proper axiom is the single requirement that the total measure be $1$. We now state this precisely.

flowchart TB
Q["Real question: what is the probability that two dice sum to 7?"] --> W["Sample space Ω — all possible outcomes"]
W --> F["σ-algebra F — the events that receive a probability"]
F --> P["Probability measure P — nonnegativity, total probability 1, countable additivity"]
P --> R["Derived basic properties — monotonicity, addition formula, subadditivity, continuity"]
R --> L["Limit theorems — law of large numbers, central limit theorem"]

Kolmogorov's framework: from a real-world question to the limit theorems

2. Preliminaries: sample spaces and the dictionary for events

For a single experiment, the nonempty set $\Omega$ of all possible outcomes is called the sample space, and its elements $\omega \in \Omega$ are called sample points (elementary outcomes). Subsets of $\Omega$ are the candidates for “events”. The choice of $\Omega$ is a modelling decision made problem by problem; mathematics does not make it for us. For two dice we take $\Omega = \{1,\dots,6\}^2$, for infinitely many coin tosses $\Omega = \{0,1\}^{\mathbb{N}}$, and so on: we choose $\Omega$ so that everything we want to ask about can be written as a subset of it.

The language of sets and the language of probability correspond as follows. Because of this dictionary, every discussion of events reduces to set operations.

Language of sets	Language of probability
$\Omega$	the sure event (always occurs)
$\emptyset$	the impossible event (never occurs)
$\omega \in A$	$A$ occurs when the outcome is $\omega$
$A \cup B$	$A$ or $B$ occurs
$A \cap B$	$A$ and $B$ occur
$A^{c} = \Omega \setminus A$	$A$ does not occur
$A \subset B$	if $A$ occurs then so does $B$
$A \cap B = \emptyset$	$A$ and $B$ are mutually exclusive

For a sequence of events $(A_n)_{n \ge 1}$ the following $2$ sets appear constantly.

$$\limsup_{n \to \infty} A_n := \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k, \qquad \liminf_{n \to \infty} A_n := \bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k .$$

Let us check what they mean. That $\omega \in \limsup_n A_n$ says: for every $n$ there is some $k \ge n$ with $\omega \in A_k$, that is, $\omega$ belongs to infinitely many of the $A_k$. So $\limsup_n A_n$ is the event ”$A_n$ occurs infinitely often”, also written $\{A_n \text{ i.o.}\}$. On the other hand $\omega \in \liminf_n A_n$ says: there is an $n$ such that $\omega \in A_k$ for all $k \ge n$, that is, $\omega$ belongs to all but finitely many of the $A_k$. Directly from the definitions, $\liminf_n A_n \subset \limsup_n A_n$ (if something happens in all but finitely many trials, it certainly happens infinitely often).

3. σ-algebras: the family of events that receive a probability

The lesson of Bertrand’s paradox was: state explicitly what receives the assignment. What conditions should that family satisfy? If we can speak of the probability of $A$, we want to speak of the probability that $A$ fails. If we can speak of the probabilities of $A_1, A_2, \ldots$, we want to speak of the probability that at least one of them occurs. We require only these $2$ closure properties, together with the requirement that the whole space belong to the family.

Definition 3.1（σ-algebra and measurable space）

Let $\Omega$ be a nonempty set. A family $\mathcal{F}$ of subsets of $\Omega$ is called a $\sigma$-algebra on $\Omega$ if it satisfies the following $3$ conditions.

1. $\Omega \in \mathcal{F}$.
2. If $A \in \mathcal{F}$ then $A^{c} \in \mathcal{F}$.
3. If $A_1, A_2, A_3, \ldots \in \mathcal{F}$ (countably many) then $\bigcup_{n=1}^{\infty} A_n \in \mathcal{F}$.

The pair $(\Omega, \mathcal{F})$ is then called a measurable space, and the elements of $\mathcal{F}$ are called events.

Note that condition 3 requires closure under countably many sets. The choice of countably many — neither finitely many nor arbitrarily many — determines everything that follows. With finitely many we cannot handle limits, and if we allow uncountably many then (as the Appendix shows) no measure exists at all.

Proposition 3.2（Operations under which a σ-algebra is closed）

Let $\mathcal{F}$ be a $\sigma$-algebra on $\Omega$. Then the following hold.

1. $\emptyset \in \mathcal{F}$.
2. If $A_1, \ldots, A_n \in \mathcal{F}$ then $\bigcup_{k=1}^{n} A_k \in \mathcal{F}$.
3. If $A_1, A_2, \ldots \in \mathcal{F}$ then $\bigcap_{n=1}^{\infty} A_n \in \mathcal{F}$, and likewise for finite intersections.
4. If $A, B \in \mathcal{F}$ then $A \setminus B \in \mathcal{F}$.
5. If $A_1, A_2, \ldots \in \mathcal{F}$ then $\limsup_n A_n \in \mathcal{F}$ and $\liminf_n A_n \in \mathcal{F}$.

Proof（Proposition 3.2）

1. By condition 1 of Definition 3.1 we have $\Omega \in \mathcal{F}$; applying condition 2 with $A = \Omega$ gives $\emptyset = \Omega^{c} \in \mathcal{F}$.

2. Set $A_k := \emptyset$ for $k > n$. By (1) each $A_k \in \mathcal{F}$, so condition 3 applies and $\bigcup_{k=1}^{\infty} A_k \in \mathcal{F}$. Adjoining empty sets does not change the union, so $\bigcup_{k=1}^{\infty} A_k = \bigcup_{k=1}^{n} A_k$, and this belongs to $\mathcal{F}$.

3. By De Morgan’s law,

$$\bigcap_{n=1}^{\infty} A_n = \Bigl( \bigcup_{n=1}^{\infty} A_n^{c} \Bigr)^{c}.$$

Each $A_n^{c} \in \mathcal{F}$ (condition 2), their countable union lies in $\mathcal{F}$ (condition 3), and so does its complement (condition 2). The finite case follows by the same trick as in (2), assigning $A_k := \Omega$ to the leftover indices.

4. We have $A \setminus B = A \cap B^{c}$ with $B^{c} \in \mathcal{F}$ (condition 2), so this is the case of finite intersections in (3).

5. The sets $B_n := \bigcup_{k=n}^{\infty} A_k$ lie in $\mathcal{F}$ by condition 3, and $\limsup_n A_n = \bigcap_{n=1}^{\infty} B_n \in \mathcal{F}$ by (3). For $\liminf$, put $C_n := \bigcap_{k=n}^{\infty} A_k \in \mathcal{F}$ (by (3)); then $\liminf_n A_n = \bigcup_{n=1}^{\infty} C_n \in \mathcal{F}$ by condition 3.

∎

Part (5) of this proposition is the practical reason for using $\sigma$-algebras: the event ”$A_n$ occurs infinitely often”, which can only be written in the language of limits, is automatically admitted as an event.

Example 3.3（Examples and a non-example of σ-algebras）

Let $\Omega$ be a nonempty set.

(a) The trivial $\sigma$-algebra $\mathcal{F} = \{\emptyset, \Omega\}$. All $3$ conditions are verified directly. This is the family that carries no information at all.

(b) The power set $\mathcal{F} = 2^{\Omega}$ (all subsets of $\Omega$). The $3$ conditions clearly hold. When $\Omega$ is countable we may simply use this, and the notion of a $\sigma$-algebra looks superfluous. The Appendix shows why this is impossible in the uncountable case.

(c) The family generated by one event. For $A \subset \Omega$ put $\mathcal{F} = \{\emptyset, A, A^{c}, \Omega\}$. Complementation permutes these $4$ sets among themselves, and unions again stay inside them (for instance $A \cup A^{c} = \Omega$).

(d) The countable–cocountable family $\mathcal{F} = \{A \subset \Omega : A \text{ is countable, or } A^{c} \text{ is countable}\}$. Condition 1 holds because $\Omega^{c} = \emptyset$ is countable. Condition 2 holds because the definition is symmetric in $A$ and $A^{c}$. For condition 3, let $A_1, A_2, \ldots \in \mathcal{F}$ and put $A := \bigcup_n A_n$. If every $A_n$ is countable, then $A$ is countable, since a countable union of countable sets is countable. Otherwise $A_{n_0}^{c}$ is countable for some $n_0$, and $A^{c} = \bigcap_n A_n^{c} \subset A_{n_0}^{c}$, so $A^{c}$ is countable too. In either case $A \in \mathcal{F}$.

(e) A non-example. Let $\Omega = \mathbb{N}$ and let $\mathcal{F}$ consist of all finite sets together with all sets whose complement is finite. This family is closed under finite unions but not under countable ones: indeed $A_n = \{2n\}$ is finite, whereas $\bigcup_n A_n$ is the set of all even numbers, which is infinite and has infinite complement. So this is not a $\sigma$-algebra (it is an algebra of sets).

3.1. Generated σ-algebras

In practice one cannot write down a $\sigma$-algebra by listing its elements. Instead one starts from a family of sets that one wants to assign probabilities to, and enlarges it by the minimum amount necessary.

Proposition 3.4（Existence and minimality of the generated σ-algebra）

Let $\mathcal{C}$ be an arbitrary family of subsets of $\Omega$. Then there exists a unique smallest $\sigma$-algebra containing $\mathcal{C}$. That is, there is a $\sigma$-algebra $\sigma(\mathcal{C})$ with $\mathcal{C} \subset \sigma(\mathcal{C})$ such that $\sigma(\mathcal{C}) \subset \mathcal{G}$ for every $\sigma$-algebra $\mathcal{G}$ containing $\mathcal{C}$.

Proof（Proposition 3.4）

Put $\Sigma := \{\mathcal{G} : \mathcal{G} \text{ is a } \sigma\text{-algebra on } \Omega \text{ with } \mathcal{C} \subset \mathcal{G}\}$. By Example 3.3 (b) we have $2^{\Omega} \in \Sigma$, so $\Sigma \neq \emptyset$ and the following definition is meaningful:

$$\sigma(\mathcal{C}) := \bigcap_{\mathcal{G} \in \Sigma} \mathcal{G} = \{A \subset \Omega : A \in \mathcal{G} \text{ for every } \mathcal{G} \in \Sigma\}.$$

We verify the $3$ conditions of Definition 3.1 for this family.

1. Each $\mathcal{G} \in \Sigma$ is a $\sigma$-algebra, so $\Omega \in \mathcal{G}$. Since this holds for every $\mathcal{G}$, we get $\Omega \in \sigma(\mathcal{C})$.
2. Let $A \in \sigma(\mathcal{C})$. For any $\mathcal{G} \in \Sigma$ we have $A \in \mathcal{G}$, and $\mathcal{G}$ is closed under complements, so $A^{c} \in \mathcal{G}$. As this holds for every $\mathcal{G}$, we get $A^{c} \in \sigma(\mathcal{C})$.
3. Let $A_1, A_2, \ldots \in \sigma(\mathcal{C})$. For any $\mathcal{G} \in \Sigma$ we have $A_n \in \mathcal{G}$ for all $n$, hence $\bigcup_n A_n \in \mathcal{G}$. Therefore $\bigcup_n A_n \in \sigma(\mathcal{C})$.

That $\mathcal{C}$ is contained in it: every $\mathcal{G} \in \Sigma$ contains $\mathcal{C}$, hence so does their intersection. Minimality: if $\mathcal{G}$ is a $\sigma$-algebra containing $\mathcal{C}$ then $\mathcal{G} \in \Sigma$, and an intersection is contained in each of its terms, so $\sigma(\mathcal{C}) \subset \mathcal{G}$. Uniqueness follows because two families both having the minimality property contain each other.

∎

Definition 3.5（Generated σ-algebra and the Borel σ-algebra）

The family $\sigma(\mathcal{C})$ of Proposition 3.4 is called the $\sigma$-algebra generated by $\mathcal{C}$. In particular, the $\sigma$-algebra generated by all open subsets of $\mathbb{R}^{d}$ is called the Borel $\sigma$-algebra, written $\mathcal{B}(\mathbb{R}^{d})$, and its elements are called Borel sets.

The family $\mathcal{B}(\mathbb{R})$ contains open intervals, closed intervals, half-lines $(-\infty, a]$, singletons, countable sets, and everything obtainable from these by countably many unions, intersections and complements. In fact one can show that $\mathcal{B}(\mathbb{R}) = \sigma(\{(-\infty, a] : a \in \mathbb{Q}\})$. The Borel $\sigma$-algebra and the construction of Lebesgue measure are treated in Measurable Sets and Lebesgue Measure (Definition 4.5［可測集合とルベーグ測度］).

Example 3.6（The probability space of infinitely many coin tosses）

Let $\Omega = \{0,1\}^{\mathbb{N}}$ (with $1$ meaning heads). For $n \ge 1$ and $\varepsilon_1, \ldots, \varepsilon_n \in \{0,1\}$ the set

$$C(\varepsilon_1, \ldots, \varepsilon_n) := \{\omega \in \Omega : \omega_1 = \varepsilon_1, \ldots, \omega_n = \varepsilon_n\}$$

is called a cylinder set. It is the event “the first $n$ tosses came out as prescribed”, which can be decided by finitely many observations. Let $\mathcal{C}$ be the collection of all cylinder sets and put $\mathcal{F} := \sigma(\mathcal{C})$. For a fair coin we want to set $P(C(\varepsilon_1,\ldots,\varepsilon_n)) = 2^{-n}$. That this prescribed value extends in exactly one way to a probability measure on all of $\mathcal{F}$ follows from Carathéodory’s extension theorem (or from Kolmogorov’s extension theorem). We do not prove it here, but take the existence for granted and proceed.

Then $A_n := \{\omega : \omega_n = 1\}$ (heads on the $n$-th toss) is a finite union of cylinder sets, hence lies in $\mathcal{F}$, and by Proposition 3.2 (5) the set

$$\limsup_{n \to \infty} A_n = \{\omega : \omega_n = 1 \text{ for infinitely many } n\} = \{\text{heads occurs infinitely often}\}$$

is an event as well. Being able to speak of the probability of this event, which no finite number of observations can ever decide, is the payoff for introducing $\sigma$-algebras.

4. Probability measures and Kolmogorov’s axioms

Definition 4.1（Probability measure and probability space (Kolmogorov's axioms)）

Let $(\Omega, \mathcal{F})$ be a measurable space. A map $P : \mathcal{F} \to \mathbb{R}$ satisfying the following $3$ conditions is called a probability measure on $(\Omega,\mathcal{F})$.

• (P1) Nonnegativity. $P(A) \ge 0$ for every $A \in \mathcal{F}$.
• (P2) Total probability. $P(\Omega) = 1$.
• (P3) Countable additivity ($\sigma$-additivity). If $A_1, A_2, \ldots \in \mathcal{F}$ are pairwise disjoint ($A_i \cap A_j = \emptyset$ whenever $i \neq j$), then

$$P\Bigl( \bigcup_{n=1}^{\infty} A_n \Bigr) = \sum_{n=1}^{\infty} P(A_n).$$

The triple $(\Omega, \mathcal{F}, P)$ is called a probability space.

The right-hand side of (P3) is a series with nonnegative terms, so its value is unchanged by rearrangement (commutativity of nonnegative series). The left-hand side is the probability of a set, which does not depend on how the $A_n$ are enumerated, so this consistency is needed. Also, since the left-hand side is a real number, (P3) simultaneously asserts that the series converges.

Theorem 4.2（Basic properties of a probability measure）

Let $(\Omega, \mathcal{F}, P)$ be a probability space. For $A, B \in \mathcal{F}$, $A_1, \ldots, A_n \in \mathcal{F}$ and $(A_n)_{n \ge 1} \subset \mathcal{F}$ the following hold.

1. $P(\emptyset) = 0$.
2. (Finite additivity) If $A_1, \ldots, A_n$ are pairwise disjoint then $P\bigl(\bigcup_{k=1}^{n} A_k\bigr) = \sum_{k=1}^{n} P(A_k)$.
3. $P(A^{c}) = 1 - P(A)$.
4. (Monotonicity) If $A \subset B$ then $P(B \setminus A) = P(B) - P(A)$; in particular $P(A) \le P(B)$.
5. $0 \le P(A) \le 1$.
6. (Addition formula) $P(A \cup B) = P(A) + P(B) - P(A \cap B)$.
7. (Countable subadditivity) $P\bigl(\bigcup_{n=1}^{\infty} A_n\bigr) \le \sum_{n=1}^{\infty} P(A_n)$, with no disjointness assumed.

Proof（Theorem 4.2）

(1) Take $A_n := \emptyset$ for every $n$. Since $\emptyset \cap \emptyset = \emptyset$, this sequence is pairwise disjoint, so (P3) applies and gives $P(\emptyset) = \sum_{n=1}^{\infty} P(\emptyset)$. Put $c := P(\emptyset)$; by (P1) we have $c \ge 0$. If $c > 0$ the right-hand series diverges to $+\infty$, contradicting the fact that the left-hand side is a real number. Hence $c = 0$.

(2) Set $A_k := \emptyset$ for $k > n$. Since $\emptyset$ is disjoint from every set, $(A_k)_{k \ge 1}$ is pairwise disjoint, and (P3) together with (1) gives

$$P\Bigl(\bigcup_{k=1}^{n} A_k\Bigr) = P\Bigl(\bigcup_{k=1}^{\infty} A_k\Bigr) = \sum_{k=1}^{\infty} P(A_k) = \sum_{k=1}^{n} P(A_k) + \sum_{k>n} 0 = \sum_{k=1}^{n} P(A_k).$$

(3) Since $A \cup A^{c} = \Omega$ and $A \cap A^{c} = \emptyset$, applying (2) with $n=2$ gives $P(A) + P(A^{c}) = P(\Omega)$, and the right-hand side equals $1$ by (P2).

(4) If $A \subset B$ then $B = A \cup (B \setminus A)$ with $A \cap (B \setminus A) = \emptyset$; that $B \setminus A \in \mathcal{F}$ is Proposition 3.2 (4). By (2), $P(B) = P(A) + P(B \setminus A)$, and rearranging gives $P(B \setminus A) = P(B) - P(A)$. Moreover $P(B \setminus A) \ge 0$ by (P1), so $P(A) \le P(B)$.

(5) Apply the second half of (4) twice to $\emptyset \subset A \subset \Omega$ and use (1) and (P2): $0 = P(\emptyset) \le P(A) \le P(\Omega) = 1$.

(6) We have $A \cup B = A \cup (B \setminus A)$, and these $2$ sets are disjoint. Also $B = (A \cap B) \cup (B \setminus A)$, and these $2$ are disjoint as well (the first is contained in $A$, the second does not meet $A$). Applying (2) to each,

$$P(A \cup B) = P(A) + P(B\setminus A), \qquad P(B) = P(A \cap B) + P(B \setminus A).$$

The second identity gives $P(B \setminus A) = P(B) - P(A \cap B)$; substituting into the first yields the claim.

(7) Replace the given sequence by a disjoint one (disjointification):

$$B_1 := A_1, \qquad B_n := A_n \setminus (A_1 \cup \cdots \cup A_{n-1}) \quad (n \ge 2).$$

By Proposition 3.2 (2) and (4), $B_n \in \mathcal{F}$. For $m < n$ we have $B_n \cap A_m = \emptyset$ and $B_m \subset A_m$, hence $B_n \cap B_m = \emptyset$: the $(B_n)$ are pairwise disjoint. Moreover $B_n \subset A_n$, and induction gives $\bigcup_{k \le N} B_k = \bigcup_{k \le N} A_k$ for every $N$, hence $\bigcup_{n} B_n = \bigcup_{n} A_n$. Combining this with (P3) and (4),

$$P\Bigl(\bigcup_{n=1}^{\infty} A_n\Bigr) = P\Bigl(\bigcup_{n=1}^{\infty} B_n\Bigr) = \sum_{n=1}^{\infty} P(B_n) \le \sum_{n=1}^{\infty} P(A_n).$$∎

These properties support almost every everyday probability computation. The addition formula (6) is precisely the counting principle “subtract what was counted twice”, while the subadditivity (7) says that “the probability that at least one bad thing happens is at most the sum of the individual probabilities” — the union bound, used again and again as a probabilistic error estimate in the theory of machine learning.

4.1. What countable additivity buys: continuity of measures

Theorem 4.3（Continuity of measures and a characterization of σ-additivity）

Let $(\Omega, \mathcal{F})$ be a measurable space.

1. (Continuity from below) Let $P$ be a probability measure and let $(A_n)_{n\ge1} \subset \mathcal{F}$ satisfy $A_1 \subset A_2 \subset \cdots$. Then the sequence $(P(A_n))$ converges and

$$P\Bigl( \bigcup_{n=1}^{\infty} A_n \Bigr) = \lim_{n \to \infty} P(A_n).$$

2. (Continuity from above) Let $P$ be a probability measure and let $(A_n)_{n\ge1} \subset \mathcal{F}$ satisfy $A_1 \supset A_2 \supset \cdots$. Then

$$P\Bigl( \bigcap_{n=1}^{\infty} A_n \Bigr) = \lim_{n \to \infty} P(A_n).$$

3. (Converse) If a map $P : \mathcal{F} \to \mathbb{R}$ satisfies (P1), (P2) and finite additivity (the property in Theorem 4.2 (2)), and in addition satisfies ”$B_1 \supset B_2 \supset \cdots$ with $\bigcap_n B_n = \emptyset$ implies $\lim_n P(B_n) = 0$”, then $P$ satisfies (P3); that is, $P$ is a probability measure.

Proof（Theorem 4.3）

(1) First we check convergence. From $A_n \subset A_{n+1}$ and Theorem 4.2 (4) we get $P(A_n) \le P(A_{n+1})$, and (5) of the same theorem gives $P(A_n) \le 1$. A real sequence that is increasing and bounded above converges (see the Completeness of the Real Numbers and Cauchy Sequences, the completeness axiom（Axiom 3.1）［Completeness of the Real Numbers and Cauchy Sequences］).

Now we compute the value. Put $B_1 := A_1$ and $B_n := A_n \setminus A_{n-1}$ for $n \ge 2$. If $m < n$ then $B_m \subset A_m \subset A_{n-1}$ while $B_n \cap A_{n-1} = \emptyset$, so the $(B_n)$ are pairwise disjoint. That $\bigcup_{k=1}^{n} B_k = A_n$ follows by induction (the case $n=1$ is the definition, and $\bigcup_{k \le n} B_k = A_{n-1} \cup (A_n \setminus A_{n-1}) = A_n$, the last equality because $A_{n-1} \subset A_n$). Hence $\bigcup_{k=1}^{\infty} B_k = \bigcup_{n=1}^{\infty} A_n$, and by (P3) together with finite additivity,

$$P\Bigl(\bigcup_{n} A_n\Bigr) = \sum_{k=1}^{\infty} P(B_k) = \lim_{n \to \infty} \sum_{k=1}^{n} P(B_k) = \lim_{n \to \infty} P\Bigl(\bigcup_{k=1}^{n} B_k\Bigr) = \lim_{n \to \infty} P(A_n).$$

(2) The sets $A_n^{c}$ form an increasing sequence, and by De Morgan $\bigcup_n A_n^{c} = (\bigcap_n A_n)^{c}$. Applying (1) to $(A_n^{c})$ gives $P\bigl((\bigcap_n A_n)^{c}\bigr) = \lim_n P(A_n^{c})$. Using Theorem 4.2 (3) on both sides, $1 - P(\bigcap_n A_n) = \lim_n (1 - P(A_n)) = 1 - \lim_n P(A_n)$, and rearranging gives the claim.

(3) Let $(A_n)_{n \ge 1} \subset \mathcal{F}$ be pairwise disjoint and put $A := \bigcup_{n=1}^{\infty} A_n \in \mathcal{F}$. Set $R_n := A \setminus \bigcup_{k=1}^{n} A_k = \bigcup_{k > n} A_k$; by Proposition 3.2 we have $R_n \in \mathcal{F}$, and $R_1 \supset R_2 \supset \cdots$. Moreover $\bigcap_n R_n = \emptyset$: if $\omega \in \bigcap_n R_n$ then for every $n$ there is a $k > n$ with $\omega \in A_k$, so $\omega$ would belong to infinitely many $A_k$; but the $(A_k)$ are pairwise disjoint, so $\omega$ lies in at most $1$ of them — a contradiction.

Since $A = \bigl(\bigcup_{k=1}^{n} A_k\bigr) \cup R_n$ is a disjoint union, finite additivity gives

$$P(A) = \sum_{k=1}^{n} P(A_k) + P(R_n).$$

By hypothesis $P(R_n) \to 0$ as $n \to \infty$, so the first term on the right converges as $n \to \infty$ and $P(A) = \sum_{k=1}^{\infty} P(A_k)$. This is (P3).

∎

Remark 4.4（Why we demand countable additivity）

Part (3) of Theorem 4.3 shows that countable additivity is equivalent to “finite additivity $+$ continuity at the empty event”. In other words, imposing (P3) is exactly granting permission to interchange probability with limiting operations. It is thanks to this equivalence that the probability of an event involving a limit, such as $\lim_{n} S_n/n = p$, can be computed as a limit of quantities determined by finitely many observations. The proofs in The Law of Large Numbers and the Central Limit Theorem all rest on this.

“Finitely additive probabilities”, satisfying finite additivity only, do exist mathematically. For instance, on $\Omega = \mathbb{N}$ one can construct a finitely additive $P$ assigning $0$ to every finite set and $1$ to the whole space (using a non-principal ultrafilter). But such a $P$ does not satisfy (P3): the sets $A_n := \{n\}$ are pairwise disjoint with $\bigcup_n A_n = \mathbb{N}$, yet $\sum_n P(A_n) = 0 \ne 1 = P(\mathbb{N})$. Over such a $P$, $A_n \uparrow A$ does not imply $P(A_n) \to P(A)$, and no limit theorem can be stated at all.

Example 4.5（Discrete probability spaces and a computation with two dice）

When $\Omega$ is at most countable we may take $\mathcal{F} = 2^{\Omega}$. If $p : \Omega \to [0,1]$ satisfies $\sum_{\omega \in \Omega} p(\omega) = 1$, then

$$P(A) := \sum_{\omega \in A} p(\omega) \qquad (A \subset \Omega)$$

is a probability measure. Indeed (P1) holds because it is a sum of nonnegative terms, (P2) follows from the hypothesis, and (P3) holds because, when the $(A_n)$ are pairwise disjoint, each $\omega \in \bigcup_n A_n$ lies in exactly $1$ of the $A_n$, so the identity is the termwise summation of a nonnegative double series. In particular, when $\Omega$ is finite and $p(\omega) = 1/|\Omega|$ we get $P(A) = |A|/|\Omega|$, so Laplace’s classical probability is recovered as a special case.

Let us carry one concrete example through to the end. Model the experiment of rolling $2$ dice by $\Omega = \{1,\ldots,6\}^2$ with $|\Omega| = 36$ and the uniform distribution. Put $A := \{\text{the sum is } 7\}$ and $B := \{\text{at least one die shows } 6\}$.

Since $A = \{(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)\}$ we get $P(A) = 6/36 = 1/6$. The complement $B^{c}$ consists of the outcomes in which neither die is $6$, so $|B^{c}| = 5^2 = 25$ and hence $P(B) = 1 - 25/36 = 11/36$ by Theorem 4.2 (3). Also $A \cap B = \{(1,6),(6,1)\}$, so $P(A \cap B) = 2/36 = 1/18$. The addition formula Theorem 4.2 (6) gives

$$P(A \cup B) = \frac{6}{36} + \frac{11}{36} - \frac{2}{36} = \frac{15}{36} = \frac{5}{12}.$$

Checking directly by counting: $A \cup B$ consists of the $6$ elements of $A$ together with the $9$ elements of $B$ that are not in $A$, making $15$ in all — indeed $15/36$.

Remark 4.6（Probability 0 does not mean impossible）

It is perfectly possible to have $P(A) = 0$ with $A \neq \emptyset$. Take $\Omega = [0,1]$, $\mathcal{F} = \mathcal{B}([0,1])$, and let $P$ be the restriction of Lebesgue measure (the uniform distribution on $[0,1]$). Then $P(\{x\}) = 0$ for every $x \in [0,1]$. That nevertheless $P([0,1]) = 1$ is no contradiction with (P3): since $[0,1]$ is uncountable, it cannot be written as a countable union of singletons, so (P3) simply does not apply. This is where the restriction to countably many sets does its work.

An event with $P(A) = 1$ is said to occur almost surely (a.s.). Holding with probability $1$ and holding for every $\omega$ are different things. This distinction becomes essential from Random Variables and Expectation onwards. Almost sure convergence (Definition 3.1［The Law of Large Numbers and the Central Limit Theorem］), for example, is built precisely on this phrase “with probability $1$”.

5. Conditional probability and Bayes’ theorem

Probabilities change when information arrives. If we are told “the die shows at least $3$” and then ask for the probability that it is even, the answer is not $1/2$ but $2/4 = 1/2$ — in this example the two happen to agree, but in general they do not. Let us define this “probability after being informed”.

The shape of the definition becomes visible in the language of frequencies. Repeat the experiment $N$ times, let $N_B$ be the number of times $B$ occurred and $N_{A \cap B}$ the number of times both $A$ and $B$ occurred. Then “the proportion of the $B$-trials in which $A$ also occurred” should behave as

$$\frac{N_{A \cap B}}{N_B} = \frac{N_{A \cap B}/N}{N_B/N} \longrightarrow \frac{P(A \cap B)}{P(B)} .$$

Accordingly we make the following definition.

Definition 5.1（Conditional probability）

Let $(\Omega, \mathcal{F}, P)$ be a probability space and let $B \in \mathcal{F}$ be an event with $P(B) > 0$. For $A \in \mathcal{F}$ the quantity

$$P(A \mid B) := \frac{P(A \cap B)}{P(B)}$$

is called the conditional probability of $A$ given that $B$ has occurred.

This definition is unusable when $P(B) = 0$. For continuous distributions, conditioning on "$X = x$" is exactly this situation, and handling it requires a different framework. The definition of Conditional Expectation via $\sigma$-algebras (Definition 3.1［条件付き期待値］) is that generalization.

Proposition 5.2（Conditional probability is a probability measure）

Let $(\Omega, \mathcal{F}, P)$ be a probability space and let $B \in \mathcal{F}$ with $P(B) > 0$. Define $P_B : \mathcal{F} \to \mathbb{R}$ by $P_B(A) := P(A \mid B)$. Then $P_B$ is a probability measure on $(\Omega, \mathcal{F})$. Moreover $P_B(B) = 1$, and $P_B(A) = 0$ whenever $A \cap B = \emptyset$.

Proof（Proposition 5.2）

(P1) For $A \in \mathcal{F}$ we have $A \cap B \in \mathcal{F}$ (Proposition 3.2 (3)) with $P(A \cap B) \ge 0$ (by (P1)) and $P(B) > 0$, so $P_B(A) \ge 0$.

(P2) Since $\Omega \cap B = B$, we get $P_B(\Omega) = P(B)/P(B) = 1$.

(P3) Let $(A_n)_{n \ge 1} \subset \mathcal{F}$ be pairwise disjoint. Then $(A_n \cap B)$ is pairwise disjoint as well (since $(A_i \cap B) \cap (A_j \cap B) \subset A_i \cap A_j = \emptyset$), and by distributivity $\bigl(\bigcup_n A_n\bigr) \cap B = \bigcup_n (A_n \cap B)$. Using (P3) for $P$,

$$P_B\Bigl(\bigcup_{n} A_n\Bigr) = \frac{1}{P(B)} P\Bigl(\bigcup_{n} (A_n \cap B)\Bigr) = \frac{1}{P(B)}\sum_{n=1}^{\infty} P(A_n \cap B) = \sum_{n=1}^{\infty} P_B(A_n).$$

In the third equality we used that a convergent series may be multiplied by the constant $1/P(B)$.

The last $2$ claims: $P_B(B) = P(B \cap B)/P(B) = 1$, and if $A \cap B = \emptyset$ then $P_B(A) = P(\emptyset)/P(B) = 0$ (Theorem 4.2 (1)).

∎

This proposition matters more than it looks. Everything proved in Theorem 4.2 and Theorem 4.3 holds for any probability measure, hence automatically for $P_B$. For instance $P(A^{c} \mid B) = 1 - P(A \mid B)$ and $P(A_1 \cup A_2 \mid B) = P(A_1\mid B) + P(A_2 \mid B) - P(A_1 \cap A_2 \mid B)$ need no separate proof.

Theorem 5.3（Multiplication rule, law of total probability, and Bayes' theorem）

Let $(\Omega, \mathcal{F}, P)$ be a probability space.

1. (Multiplication rule) If $A_1, \ldots, A_n \in \mathcal{F}$ satisfy $P(A_1 \cap \cdots \cap A_{n-1}) > 0$, then

$$P(A_1 \cap \cdots \cap A_n) = P(A_1)\, P(A_2 \mid A_1)\, P(A_3 \mid A_1 \cap A_2) \cdots P(A_n \mid A_1 \cap \cdots \cap A_{n-1}).$$

2. (Law of total probability) Let $I$ be an at most countable index set and let $(B_i)_{i \in I} \subset \mathcal{F}$ be pairwise disjoint with $\bigcup_{i \in I} B_i = \Omega$ and $P(B_i) > 0$ for every $i$. Then for every $A \in \mathcal{F}$,

$$P(A) = \sum_{i \in I} P(A \mid B_i)\, P(B_i).$$

3. (Bayes’ theorem) Under the same hypotheses as (2), if moreover $P(A) > 0$, then for each $j \in I$,

$$P(B_j \mid A) = \frac{P(A \mid B_j)\, P(B_j)}{\sum_{i \in I} P(A \mid B_i)\, P(B_i)}.$$

Proof（Theorem 5.3）

(1) First we check that each conditional probability on the right is defined. For $k \le n-1$ we have $A_1 \cap \cdots \cap A_k \supset A_1 \cap \cdots \cap A_{n-1}$, so monotonicity Theorem 4.2 (4) gives $P(A_1 \cap \cdots \cap A_k) \ge P(A_1 \cap \cdots \cap A_{n-1}) > 0$, and Definition 5.1 applies. Writing $D_k := A_1 \cap \cdots \cap A_k$, the definition gives $P(A_{k+1} \mid D_k) = P(D_{k+1})/P(D_k)$. Therefore the right-hand side telescopes:

$$P(D_1) \cdot \frac{P(D_2)}{P(D_1)} \cdot \frac{P(D_3)}{P(D_2)} \cdots \frac{P(D_n)}{P(D_{n-1})} = P(D_n),$$

which is the left-hand side.

(2) Since $(B_i)$ is a partition of $\Omega$, distributivity gives

$$A = A \cap \Omega = A \cap \bigcup_{i \in I} B_i = \bigcup_{i \in I} (A \cap B_i),$$

and $(A \cap B_i)_{i \in I}$ is pairwise disjoint (for $i \ne j$, $(A\cap B_i) \cap (A \cap B_j) \subset B_i \cap B_j = \emptyset$). As $I$ is at most countable, (P3) applies (or Theorem 4.2 (2) if $I$ is finite), giving

$$P(A) = \sum_{i \in I} P(A \cap B_i) = \sum_{i \in I} P(A \mid B_i)\, P(B_i).$$

The last equality is Definition 5.1 in the form $P(A \cap B_i) = P(A \mid B_i) P(B_i)$ (this is where $P(B_i) > 0$ is used).

(3) Since $P(A) > 0$, the quantity $P(B_j \mid A)$ is defined, and by the definition

$$P(B_j \mid A) = \frac{P(A \cap B_j)}{P(A)} = \frac{P(A \mid B_j) P(B_j)}{P(A)}.$$

Substituting (2) into the denominator gives the claim.

∎

The law of total probability: slicing the event A along the partition B₁, …, B₄

Example 5.4（What does a positive test result mean?）

Consider a disease with prevalence $0.1\%$ and a test with sensitivity $99\%$ (the probability that a diseased person tests positive) and specificity $95\%$ (the probability that a healthy person tests negative). Given that a randomly chosen person tests positive, what is the probability that the person really has the disease?

Let $D$ be the event “has the disease” and $T$ the event “the test is positive”. The hypotheses read

$$P(D) = 0.001, \quad P(T \mid D) = 0.99, \quad P(T \mid D^{c}) = 1 - 0.95 = 0.05.$$

The family $\{D, D^{c}\}$ is a partition of $\Omega$ with $P(D) > 0$ and $P(D^{c}) = 0.999 > 0$. By the law of total probability Theorem 5.3 (2),

$$P(T) = 0.99 \times 0.001 + 0.05 \times 0.999 = 0.00099 + 0.04995 = 0.05094.$$

By Bayes’ theorem Theorem 5.3 (3),

$$P(D \mid T) = \frac{0.00099}{0.05094} = 0.01943\ldots \approx 1.9\%.$$

Despite a positive result on a test with $99\%$ sensitivity, the probability of actually having the disease is only about $2\%$. The reason is visible in the breakdown of the denominator: of the total positive mass $0.05094$, the true positives contribute $0.00099$ and the false positives $0.04995$, so false positives outnumber true positives by a factor of $50$. The $5\%$ of the healthy people, who make up $99.9\%$ of the population, overwhelm the entire diseased group, which is only $0.1\%$ of it. The error of looking only at the likelihood while ignoring the prior is called base rate neglect.

Writing this in terms of odds makes the structure even clearer: $\dfrac{P(D \mid T)}{P(D^{c} \mid T)} = \dfrac{P(T \mid D)}{P(T \mid D^{c})} \cdot \dfrac{P(D)}{P(D^{c})}$ (write Bayes’ theorem for $D$ and for $D^{c}$ and take the ratio; the factor $P(T)$ in the denominators cancels). Inserting the numbers,

$$\text{posterior odds} = \frac{0.99}{0.05} \times \frac{0.001}{0.999} = 19.8 \times 0.0010010\ldots = 0.019820\ldots,$$

and converting back to a probability, $0.019820/(1 + 0.019820) = 0.01943\ldots$, in agreement with the above. The information carried by the test is condensed into the single number $19.8$ (the likelihood ratio), which updates the prior odds of $1{:}999$ multiplicatively.

6. Independence of events and the Borel–Cantelli lemma

If the conditional probability $P(A \mid B)$ equals $P(A)$, then learning $B$ does not change our judgement about $A$. This is independence. The definition, however, is written without division: this allows the case $P(B) = 0$ and makes the generalization to $3$ or more events natural.

Definition 6.1（Independence of events）

Let $(\Omega, \mathcal{F}, P)$ be a probability space.

1. Two events $A, B \in \mathcal{F}$ are independent if $P(A \cap B) = P(A) P(B)$.
2. A family of events $(A_i)_{i \in I} \subset \mathcal{F}$ is independent if for every nonempty finite subset $J$ of $I$,

$$P\Bigl( \bigcap_{i \in J} A_i \Bigr) = \prod_{i \in J} P(A_i).$$

3. A family $(A_i)_{i \in I}$ is pairwise independent if $A_i$ and $A_j$ are independent for all $i, j \in I$ with $i \ne j$.

When $P(B) > 0$, independence of $A$ and $B$ is equivalent to $P(A \mid B) = P(A)$. Indeed $P(A \mid B) = P(A \cap B)/P(B)$, so multiplying both sides by $P(B)$ passes from either statement to the other.

Proposition 6.2（Independence is preserved under complementation）

Let $(\Omega,\mathcal{F},P)$ be a probability space and let $A, B \in \mathcal{F}$ be independent. Then $A$ and $B^{c}$, $A^{c}$ and $B$, and $A^{c}$ and $B^{c}$ are all independent.

Proof（Proposition 6.2）

We have $A \cap B \subset A$ and $A \cap B^{c} = A \setminus (A \cap B)$. Applying Theorem 4.2 (4) to $A \cap B \subset A$,

$$P(A \cap B^{c}) = P(A) - P(A \cap B).$$

Substituting the hypothesis $P(A \cap B) = P(A)P(B)$ and using Theorem 4.2 (3),

$$P(A \cap B^{c}) = P(A) - P(A)P(B) = P(A)\bigl(1 - P(B)\bigr) = P(A) P(B^{c}).$$

Hence $A$ and $B^{c}$ are independent. Independence of $A^{c}$ and $B$ follows by the same argument with the roles of $A$ and $B$ exchanged. For $A^{c}$ and $B^{c}$, apply the operation once more to the pair ”$A$ and $B^{c}$” just obtained, holding $B^{c}$ fixed and complementing on the $A$ side.

∎

Example 6.3（Pairwise independent but not independent (Bernstein)）

Let $\Omega = \{1,2,3,4\}$, $\mathcal{F} = 2^{\Omega}$, and let $P$ be the uniform distribution (mass $1/4$ at each point). Put

$$A := \{1,2\}, \qquad B := \{1,3\}, \qquad C := \{1,4\}.$$

Then $P(A) = P(B) = P(C) = 2/4 = 1/2$. Every pairwise intersection equals $\{1\}$, so

$$P(A \cap B) = P(B \cap C) = P(A \cap C) = \frac{1}{4} = \frac{1}{2} \cdot \frac{1}{2},$$

that is, $A, B, C$ are pairwise independent. However $A \cap B \cap C = \{1\}$, so

$$P(A \cap B \cap C) = \frac{1}{4} \neq \frac{1}{8} = P(A)P(B)P(C).$$

Hence the family $\{A, B, C\}$ is not independent in the sense of Definition 6.1 (2). Intuitively, once we know that both $A$ and $B$ have occurred, the outcome is pinned to $1$ and $C$ occurs automatically. Events can be unrelated one at a time and yet, taken two at a time, completely determine a third.

Remark 6.4（An example in the opposite direction）

There are also examples where the triple product identity holds but pairwise independence fails. Let $\Omega = \{1,\ldots,8\}$ carry the uniform distribution and put $A = \{1,2,3,4\}$, $B = \{1,2,3,5\}$, $C = \{1,6,7,8\}$. Then $P(A) = P(B) = P(C) = 1/2$, and since $A \cap B \cap C = \{1\}$ we get $P(A\cap B \cap C) = 1/8 = P(A)P(B)P(C)$. But $A \cap B = \{1,2,3\}$, so $P(A \cap B) = 3/8 \ne 1/4$ and $A$ and $B$ are not independent. Examples like this are why the definition of independence for $3$ or more events demands the product identity for every finite subset.

6.1. The Borel–Cantelli lemma

Here is the first theorem in which countable additivity really earns its keep. It bounds the probability that infinitely many of an infinite sequence of events occur, using only the sum of their individual probabilities.

Lemma 6.5（Borel–Cantelli lemma (first)）

Let $(\Omega, \mathcal{F}, P)$ be a probability space and let $(A_n)_{n \ge 1} \subset \mathcal{F}$. If

$$\sum_{n=1}^{\infty} P(A_n) < \infty$$

then $P\bigl(\limsup_{n \to \infty} A_n\bigr) = 0$; that is, with probability $1$ only finitely many of the $A_n$ occur. No independence is assumed.

Proof（Lemma 6.5）

Put $B_n := \bigcup_{k=n}^{\infty} A_k$. By Proposition 3.2 we have $B_n \in \mathcal{F}$, and by definition $L := \limsup_m A_m = \bigcap_{n=1}^{\infty} B_n$, which is again an event (part (5) of the same proposition).

For every $n$ we have $L \subset B_n$, so monotonicity Theorem 4.2 (4) gives $P(L) \le P(B_n)$. Applying countable subadditivity Theorem 4.2 (7) to $B_n = \bigcup_{k \ge n} A_k$,

$$P(L) \le P(B_n) \le \sum_{k=n}^{\infty} P(A_k).$$

The right-hand side is the $n$-th tail of the convergent series $\sum_{k} P(A_k)$, so it tends to $0$ as $n \to \infty$ because the series converges. The left-hand side $P(L)$ is a constant independent of $n$, so $0 \le P(L) \le \inf_n \sum_{k \ge n} P(A_k) = 0$, that is, $P(L) = 0$.

Alternatively, since $(B_n)$ is decreasing, one may use continuity from above Theorem 4.3 (2) to conclude $P(L) = \lim_n P(B_n) = 0$.

∎

Example 6.6（Long runs of heads must eventually stop）

In the fair-coin probability space $(\Omega, \mathcal{F}, P)$ of Example 3.6, put

$$A_n := \{\omega : \omega_n = \omega_{n+1} = \cdots = \omega_{2n-1} = 1\}$$

(heads $n$ times in a row starting at toss $n$). The event $A_n$ is a union of cylinder sets determined by the first $2n-1$ coordinates: there are $2^{n-1}$ choices for the free coordinates $\omega_1,\ldots,\omega_{n-1}$, and each cylinder set has probability $2^{-(2n-1)}$, so finite additivity Theorem 4.2 (2) gives

$$P(A_n) = 2^{n-1} \cdot 2^{-(2n-1)} = 2^{(n-1)-(2n-1)} = 2^{-n}.$$

Hence $\sum_{n=1}^{\infty} P(A_n) = \sum_{n=1}^{\infty} 2^{-n} = 1 < \infty$. By Lemma 6.5 we get $P(\limsup_n A_n) = 0$: with probability $1$, only finitely many $n$ have the property that $n$ consecutive heads begin at toss $n$. In other words, beyond some $N$ this phenomenon never happens again.

Each individual $A_n$ has positive probability ($2^{-n} > 0$), and yet the probability that they occur infinitely often is $0$. Finite additivity alone cannot reach a conclusion of this kind; we needed the subadditivity and monotonicity derived from (P3). The converse statement (the second lemma, which assumes independence and deduces $P(\limsup_n A_n) = 1$ from $\sum_n P(A_n) = \infty$) is used in the proof of the strong law of large numbers (Theorem 4.5［The Law of Large Numbers and the Central Limit Theorem］); see The Law of Large Numbers and the Central Limit Theorem.

7. Exercises

Exercise 7.1Easy

Let $(\Omega,\mathcal{F},P)$ be a probability space and $A, B, C \in \mathcal{F}$. Show that

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

Solution

Apply the addition formula Theorem 4.2 (6) to $A \cup B$ and $C$:

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

Using (6) once more on the first term gives $P(A \cup B) = P(A) + P(B) - P(A \cap B)$. For the third term, distributivity gives $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$, and (6) again yields

$$P\bigl((A\cup B)\cap C\bigr) = P(A \cap C) + P(B \cap C) - P\bigl((A \cap C) \cap (B \cap C)\bigr),$$

where $(A\cap C)\cap(B\cap C) = A \cap B \cap C$. Substituting everything,

$$P(A\cup B \cup C) = \bigl(P(A)+P(B)-P(A\cap B)\bigr) + P(C) - P(A\cap C) - P(B\cap C) + P(A\cap B\cap C),$$

which is the desired identity. That the sets appearing along the way, such as $A \cup B$ and $(A\cup B)\cap C$, all belong to $\mathcal{F}$ follows from Proposition 3.2 (2) and (3).

Exercise 7.2Standard

Behind one of $3$ doors there is a prize, and the other $2$ are empty; the position of the prize is uniformly distributed over the $3$ doors. After the contestant picks door $1$, the host — who knows where the prize is — opens one door that the contestant did not pick and that does not hide the prize (when there are $2$ such doors, that is, when the prize is behind door $1$, the host chooses between them with equal probability). Given that the host opened door $3$, find the conditional probability that the prize is behind door $2$. State the probability space explicitly.

Solution

Let $C \in \{1,2,3\}$ be the door with the prize and $H \in \{2,3\}$ the door the host opens, and set $\Omega := \{(c,h) : c \in \{1,2,3\},\, h \in \{2,3\},\, h \ne c\}$, $\mathcal{F} := 2^{\Omega}$. The hypotheses are

$$P(C = c) = \tfrac13 \ (c=1,2,3), \quad P(H = 3 \mid C = 1) = \tfrac12, \quad P(H=3 \mid C = 2) = 1, \quad P(H = 3 \mid C = 3) = 0$$

(if $C=2$ the host cannot open door $2$, and door $1$ was chosen by the contestant, so only door $3$ remains; if $C=3$ the host cannot open door $3$). By the multiplication rule Theorem 5.3 (1) the probability of each point is determined:

$$P(C=1, H=3) = \tfrac13 \cdot \tfrac12 = \tfrac16, \quad P(C=2,H=3) = \tfrac13 \cdot 1 = \tfrac13, \quad P(C=3,H=3) = 0.$$

The events $\{C=1\},\{C=2\},\{C=3\}$ partition $\Omega$ and each has positive probability, so the law of total probability Theorem 5.3 (2) applies:

$$P(H = 3) = \tfrac16 + \tfrac13 + 0 = \tfrac12 .$$

Since $P(H=3) > 0$, Bayes’ theorem Theorem 5.3 (3) is applicable and

$$P(C = 2 \mid H = 3) = \frac{P(C=2, H=3)}{P(H=3)} = \frac{1/3}{1/2} = \frac{2}{3}, \qquad P(C = 1 \mid H = 3) = \frac{1/6}{1/2} = \frac{1}{3}.$$

Switching doors wins with probability $2/3$. The key is that $P(H=3\mid C=1) = 1/2$ differs from $P(H=3 \mid C=2) = 1$; that is, the host’s behaviour carries information about the location of the prize. If instead the host did not know where the prize was and chose between doors $2$ and $3$ with equal probability, happening to reveal an empty door, then $P(H=3\mid C=1) = P(H=3\mid C=2) = 1/2$ and the same computation gives the answer $1/2$.

Exercise 7.3Standard

Let $(\Omega,\mathcal{F},P)$ be a probability space and let $A, B, C \in \mathcal{F}$ be independent in the sense of Definition 6.1 (2). Show that $A$ and $B \cup C$ are independent.

Solution

By distributivity, $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. Applying the addition formula Theorem 4.2 (6) to the right-hand side and noting that $(A\cap B) \cap (A \cap C) = A \cap B \cap C$,

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

Using the independence of the family $\{A,B,C\}$ for the subsets $\{A,B\}$, $\{A,C\}$ and $\{A,B,C\}$, this equals

$$= P(A)P(B) + P(A)P(C) - P(A)P(B)P(C) = P(A)\bigl(P(B) + P(C) - P(B)P(C)\bigr).$$

Independence for $\{B,C\}$ gives $P(B)P(C) = P(B\cap C)$, so by the addition formula the bracket equals $P(B) + P(C) - P(B\cap C) = P(B \cup C)$. Therefore

$$P\bigl(A \cap (B \cup C)\bigr) = P(A)\, P(B\cup C),$$

that is, $A$ and $B \cup C$ are independent. To see where pairwise independence would not suffice, note that we used $P(A\cap B\cap C) = P(A)P(B)P(C)$. Checking with the $A,B,C$ of Example 6.3: there $B \cup C = \{1,3,4\}$ with $P(B\cup C) = 3/4$, while $A \cap (B\cup C) = \{1\}$ has probability $1/4 \ne (1/2)(3/4) = 3/8$, so pairwise independence alone does not give the conclusion.

Exercise 7.4Hard

Let $(\Omega,\mathcal{F},P)$ be a probability space and $(A_n)_{n\ge1} \subset \mathcal{F}$. Show that

$$P\Bigl(\liminf_{n\to\infty} A_n\Bigr) \le \liminf_{n \to \infty} P(A_n) \le \limsup_{n\to\infty} P(A_n) \le P\Bigl(\limsup_{n\to\infty} A_n\Bigr).$$

Solution

Put $C_n := \bigcap_{k=n}^{\infty} A_k$ and $B_n := \bigcup_{k=n}^{\infty} A_k$. By Proposition 3.2 we have $B_n, C_n \in \mathcal{F}$, with $C_1 \subset C_2 \subset \cdots$ and $B_1 \supset B_2 \supset \cdots$, and $\liminf_n A_n = \bigcup_n C_n$, $\limsup_n A_n = \bigcap_n B_n$.

The left inequality. Continuity from below Theorem 4.3 (1) gives $P(\liminf_n A_n) = \lim_{n} P(C_n)$. On the other hand $C_n \subset A_n$, so monotonicity Theorem 4.2 (4) gives $P(C_n) \le P(A_n)$. Since the limit inferior of a sequence preserves termwise inequalities,

$$P\Bigl(\liminf_n A_n\Bigr) = \lim_n P(C_n) = \liminf_n P(C_n) \le \liminf_n P(A_n).$$

(The limit $\lim_n P(C_n)$ exists, so it coincides with the limit inferior.)

The middle inequality. For any real sequence, $\liminf \le \limsup$ (let $n \to \infty$ on both sides of $\inf_{k\ge n} x_k \le \sup_{k \ge n} x_k$).

The right inequality. Continuity from above Theorem 4.3 (2) gives $P(\limsup_n A_n) = \lim_n P(B_n)$. Since $A_n \subset B_n$, monotonicity gives $P(A_n) \le P(B_n)$, hence

$$\limsup_n P(A_n) \le \limsup_n P(B_n) = \lim_n P(B_n) = P\Bigl(\limsup_n A_n\Bigr).$$

In particular, when $\lim_n A_n$ exists (that is, when $\liminf_n A_n = \limsup_n A_n$), all $4$ quantities agree and we obtain $P(\lim_n A_n) = \lim_n P(A_n)$. This is the set-theoretic version of Fatou’s lemma for measures, the prototype of the version for functions (Lemma 6.1［ルベーグ積分の定義と収束定理］) treated in The Lebesgue Integral and the Convergence Theorems.

References

• A. N. Kolmogorov, Grundbegriffe der Wahrscheinlichkeitsrechnung, Springer, 1933 (English translation: Foundations of the Theory of Probability, Chelsea, 1950) — Chapter I. This is the source of the axiom system used in this article.
• Kiyosi Itô, Kakuritsuron (Probability Theory), Iwanami Shoten (Iwanami Kiso Sūgaku Sensho), 1991 — Chapter 1 (in Japanese). The standard Japanese reference on measure-theoretic probability.
• Naohisa Funaki, Kakuritsuron (Probability Theory), Asakura Shoten (Kōza Sūgaku no Kangaekata 20), 2004 — Chapters 1 and 2 (in Japanese). Careful treatment of the construction of probability spaces and of the extension theorem.
• P. Billingsley, Probability and Measure, 3rd ed., Wiley, 1995 — Chapters 1–4. Detailed treatment of the Borel–Cantelli lemma and of independence.
• R. Durrett, Probability: Theory and Examples, 5th ed., Cambridge University Press, 2019 — Chapter 1.
• D. Williams, Probability with Martingales, Cambridge University Press, 1991 — Chapters 1–4. A lucid presentation of the reading of $\sigma$-algebras as information.

Appendix: Non-measurable sets — why the family of events must be restricted

The problem. As we saw in Example 3.3 (b), the collection $2^{\Omega}$ of all subsets of $\Omega$ is always a $\sigma$-algebra. Why, then, should we go to the trouble of choosing a smaller $\mathcal{F}$? Because on $2^{\Omega}$ there may be no probability measure with the properties we want. The following fact, proved by Vitali in $1905$, is the typical case.

Claim. There is no probability measure $P$ defined on all of $2^{\Omega}$ for $\Omega := [0,1)$ that is translation invariant, that is, satisfies $P(A \oplus t) = P(A)$ for every $A \subset [0,1)$ and every $t \in [0,1)$. Here $A \oplus t := \{(a + t) \bmod 1 : a \in A\}$.

Construction. Introduce on $[0,1)$ the equivalence relation $x \sim y :\iff x - y \in \mathbb{Q}$. Reflexivity, symmetry and transitivity follow from the fact that the rationals form an additive group. By the axiom of choice there is a set $V \subset [0,1)$ containing exactly $1$ point from each equivalence class. Since $\mathbb{Q} \cap [0,1)$ is countably infinite, enumerate it as $\{q_1, q_2, q_3, \ldots\}$ and put $V_n := V \oplus q_n$.

This sequence is a countable partition of $[0,1)$. First, disjointness. If $x \in V_n \cap V_m$ then $x = (v + q_n) \bmod 1 = (v' + q_m) \bmod 1$ for some $v, v' \in V$. Then $v - v' \in \mathbb{Q}$, so $v \sim v'$, and since $V$ contains only $1$ point from each class, $v = v'$; hence $q_n = q_m$, that is, $n = m$. Second, covering. Take any $x \in [0,1)$ and let $v \in V$ be the representative of the class of $x$. Then $x - v \in \mathbb{Q}$, and $(x - v) \bmod 1$ is an element of $\mathbb{Q}\cap[0,1)$, hence equal to some $q_n$. Therefore $x = (v + q_n) \bmod 1 \in V_n$.

The contradiction. Suppose such a $P$ existed. By translation invariance, $P(V_n) = P(V) =: c$ for every $n$. The $(V_n)$ are pairwise disjoint with union $[0,1)$, so (P3) and (P2) give

$$1 = P([0,1)) = \sum_{n=1}^{\infty} P(V_n) = \sum_{n=1}^{\infty} c .$$

If $c = 0$ the right-hand side is $0$, and if $c > 0$ it diverges to $+\infty$. Neither equals $1$: a contradiction.

Conclusion and a caveat. Hence one cannot consistently assign translation-invariant probabilities to all subsets of $[0,1)$. If we want to retain the notion of length, we have no choice but to restrict the objects receiving a probability to something like the Borel sets (or the Lebesgue measurable sets), and this is the reason for introducing $\sigma$-algebras. For the detailed construction, in particular the definition of measurable sets via Carathéodory’s criterion (Definition 4.1［可測集合とルベーグ測度］), see Measurable Sets and Lebesgue Measure.

Note that this argument uses the axiom of choice in an essential way. In $1970$ Solovay showed that (assuming the existence of an inaccessible cardinal) there are models of set theory, with choice weakened to dependent choice, in which every subset of $\mathbb{R}$ is Lebesgue measurable. Non-measurable sets are objects produced by the axiom of choice; they cannot be written down explicitly. Since ordinary mathematics nevertheless adopts the axiom of choice, $\sigma$-algebras remain a necessary tool.

Tip

A $\sigma$-algebra is not merely an annoying technical restriction: it is also a device for specifying how much information may be used. Reading “the smaller $\mathcal{F}$ is, the fewer events can be distinguished” makes it natural to view an increasing sequence of $\sigma$-algebras (a filtration) as information accumulating over time. This viewpoint plays a central role in Martingales and Brownian Motion (the definition of a filtration（Definition 2.1）［マルチンゲールとブラウン運動］).