Sample Spaces, Events & Axioms

The sample space of a random experiment is the set $\Omega$ whose elements are the possible outcomes of the experiment. An individual outcome $\omega \in \Omega$ is called a sample point.

An event is a subset $A \subseteq \Omega$. The event $A$ occurs if the outcome $\omega$ of the experiment belongs to $A$.

Special events:

• The certain event $\Omega$ always occurs.
• The impossible event $\emptyset$ never occurs.
• A simple event $\{\omega\}$ consists of a single outcome.

Let $\Omega = \{1, 2, 3, 4, 5, 6\}$.

• $A = \{2, 4, 6\}$ is the event “roll an even number.”
• $B = \{5, 6\}$ is the event “roll at least 5.”
• $A \cap B = \{6\}$ is the event “roll an even number that is at least 5.”
• $A \cup B = \{2, 4, 5, 6\}$ is the event “roll an even number or at least 5.”
• $A^c = \{1, 3, 5\}$ is the event “do not roll an even number” (i.e., roll odd).

A $\sigma$-algebra (or $\sigma$-field) on a set $\Omega$ is a collection $\mathcal{F} \subseteq \mathcal{P}(\Omega)$ satisfying:

1. $\Omega \in \mathcal{F}$  (the sample space is an event)
2. If $A \in \mathcal{F}$, then $A^c \in \mathcal{F}$  (closed under complements)
3. If $A_1, A_2, A_3, \ldots \in \mathcal{F}$, then $\bigcup_{n=1}^{\infty} A_n \in \mathcal{F}$  (closed under countable unions)

By De Morgan’s law, closure under complements + countable unions gives closure under countable intersections for free. And since $\emptyset = \Omega^c$, the empty set is always in $\mathcal{F}$.

The word “countable” in axiom (3) is doing heavy lifting. A collection closed under finite unions but not countable unions is called an algebra (or field) of sets. The upgrade from algebra to $\sigma$-algebra is exactly what we need for limit theorems — taking limits of sequences of events requires countable set operations.

• The trivial $\sigma$-algebra $\mathcal{F} = \{\emptyset, \Omega\}$ is the smallest possible — we can only say “something happened” or “nothing happened.”
• The discrete $\sigma$-algebra $\mathcal{F} = \mathcal{P}(\Omega)$ is the largest — every subset is an event. This works for countable $\Omega$.

Let $\Omega = \{1, 2, 3, 4\}$. Consider $\mathcal{F} = \{\emptyset, \{1,2\}, \{3,4\}, \Omega\}$.

Check: (1) $\Omega \in \mathcal{F}$ ✓. (2) $\{1,2\}^c = \{3,4\} \in \mathcal{F}$ ✓. (3) All unions of members yield members ✓.

This $\sigma$-algebra “sees” the partition $\{\{1,2\}, \{3,4\}\}$ but cannot distinguish 1 from 2 or 3 from 4. It encodes partial information — a theme that becomes central in conditional probability and filtrations.

On $\Omega = \mathbb{R}$, the Borel $\sigma$-algebra $\mathcal{B}(\mathbb{R})$ is the smallest $\sigma$-algebra containing all open intervals $(a, b)$. It contains all open sets, all closed sets, all countable intersections of open sets ($G_\delta$ sets), all countable unions of closed sets ($F_\sigma$ sets), and more. This is the standard $\sigma$-algebra for probability on $\mathbb{R}$ — the one you use 99% of the time.

Why this matters for ML: When you write ”$X \sim \mathcal{N}(\mu, \sigma^2)$,” you are implicitly working with the Borel $\sigma$-algebra on $\mathbb{R}$. The measurability requirement — that a random variable must pull Borel sets back to events in your $\sigma$-algebra — is what makes statements like "$P(X \leq t)$" well-defined. We’ll formalize this in Random Variables & Distributions (coming soon).

A probability measure on a measurable space $(\Omega, \mathcal{F})$ is a function $P : \mathcal{F} \to [0,1]$ satisfying:

Axiom 1 (Non-negativity). For every $A \in \mathcal{F}$, $P(A) \geq 0$.

Axiom 2 (Normalization). $P(\Omega) = 1$.

Axiom 3 (Countable Additivity). If $A_1, A_2, A_3, \ldots \in \mathcal{F}$ are pairwise disjoint (i.e., $A_i \cap A_j = \emptyset$ for all $i \neq j$), then

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

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

Axiom 3 demands countable additivity, not mere finite additivity. This is the axiom that makes limit theorems possible. If we only required $P(A_1 \cup \cdots \cup A_n) = P(A_1) + \cdots + P(A_n)$ for finite collections, we could not take limits of sequences of events — and without limits, no convergence theorems, no law of large numbers, no central limit theorem. The jump from “finitely many” to “countably many” is small in notation but enormous in mathematical power.

Roll a fair die. The probability space is:

• $\Omega = \{1, 2, 3, 4, 5, 6\}$
• $\mathcal{F} = \mathcal{P}(\Omega)$ (all 64 subsets)
• $P(\{\omega\}) = 1/6$ for each $\omega$, extended by additivity: $P(A) = \lvert A\rvert/6$

Check the axioms: (1) $P(A) = \lvert A\rvert/6 \geq 0$ ✓. (2) $P(\Omega) = 6/6 = 1$ ✓. (3) For disjoint $A, B$: $P(A \cup B) = \lvert A \cup B\rvert/6 = (\lvert A\rvert + \lvert B\rvert)/6 = P(A) + P(B)$ ✓.

For any event $A \in \mathcal{F}$,

$P(A^c) = 1 - P(A).$

$P(\emptyset) = 0$.

If $A \subseteq B$, then $P(A) \leq P(B)$.

For any events $A, B \in \mathcal{F}$,

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

For events $A_1, \ldots, A_n \in \mathcal{F}$,

$P\left(\bigcup_{i=1}^n A_i\right) = \sum_{i} P(A_i) - \sum_{i \lt j} P(A_i \cap A_j) + \sum_{i \lt j \lt k} P(A_i \cap A_j \cap A_k) - \cdots + (-1)^{n+1} P(A_1 \cap \cdots \cap A_n).$

The proof proceeds by induction on $n$, with the base case $n = 2$ being Theorem 3. The inductive step applies Theorem 3 to $\left(\bigcup_{i=1}^{n-1} A_i\right) \cup A_n$ and uses the distributive law.

For any countable collection of events $A_1, A_2, \ldots \in \mathcal{F}$,

$P\left(\bigcup_{n=1}^{\infty} A_n\right) \leq \sum_{n=1}^{\infty} P(A_n).$

Let $A_1, A_2, \ldots \in \mathcal{F}$.

(a) If $A_n \uparrow A$ (i.e., $A_1 \subseteq A_2 \subseteq \cdots$ and $A = \bigcup_{n=1}^{\infty} A_n$), then $P(A) = \lim_{n \to \infty} P(A_n)$.

(b) If $A_n \downarrow A$ (i.e., $A_1 \supseteq A_2 \supseteq \cdots$ and $A = \bigcap_{n=1}^{\infty} A_n$), then $P(A) = \lim_{n \to \infty} P(A_n)$.

Given finite additivity, countable additivity is equivalent to continuity from below (Theorem 6a). This means Axiom 3 is really saying “probability is a continuous set function,” connecting our probability axioms directly to the continuity of limits.

In a group of $n$ people, what is the probability that at least two share a birthday? Assume 365 equally likely birthdays.

It’s easier to compute the complement: $P(\text{all different})$.

• Person 1 has $365/365$ choices.
• Person 2 must avoid person 1’s birthday: $364/365$.
• Person $k$ must avoid the previous $k-1$ birthdays: $(365-k+1)/365$.

$P(\text{all different}) = \prod_{k=0}^{n-1} \frac{365 - k}{365} = \frac{365!}{(365-n)! \cdot 365^n}$

$P(\text{at least one match}) = 1 - P(\text{all different})$

The famous result: with just $n = 23$ people, the probability exceeds 50%.

$n$ people check their hats; the hats are returned at random. What is the probability that nobody gets their own hat back?

A permutation with no fixed points is called a derangement. Let $A_i$ be the event “person $i$ gets their own hat.” We want $P\left(\bigcup_{i=1}^n A_i\right)^c$.

By inclusion-exclusion:

$P\left(\bigcup_{i=1}^n A_i\right) = \sum_{k=1}^n (-1)^{k+1} \binom{n}{k} \cdot \frac{(n-k)!}{n!} = \sum_{k=1}^n \frac{(-1)^{k+1}}{k!}$

So the probability of a derangement is:

$P(\text{derangement}) = \sum_{k=0}^n \frac{(-1)^k}{k!} \xrightarrow{n \to \infty} \frac{1}{e} \approx 0.3679$

This is remarkable: for large $n$, the probability converges to $1/e$, independent of $n$. The convergence is extremely fast — already at $n = 5$, the answer is accurate to three decimal places.

For events $A, B \in \mathcal{F}$ with $P(B) > 0$,

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

Events $A$ and $B$ are independent if

$P(A \cap B) = P(A) \cdot P(B).$

Equivalently (when $P(B) > 0$): $P(A \mid B) = P(A)$ — knowing $B$ occurred doesn’t change the probability of $A$.