Probability Spaces and Random Variables

The measure-theoretic setup, stated once and precisely, so that later statements about independence, conditioning and convergence have something to mean.

ProbabilityFoundations⏱ 1 hour7 min readprobability spacesigma algebrarandom variabledistributionindependence

3 problems →

AssumesAnalysis Prerequisites

The three axioms

DefinitionProbability space

A probability space is a triple $(\Omega, \mathcal{A}, \P)$ where

$\Omega$ is a set of outcomes;
$\mathcal{A}$ is a $\sigma$ -algebra on $\Omega$ : a collection of subsets containing $\Omega$ and closed under complement and countable union;
$\P : \mathcal{A} \to [0,1]$ is a probability measure: $\P(\Omega) = 1$ and, for pairwise disjoint $A_1, A_2, \dots \in \mathcal{A}$ , $\P\left(\bigcup_i A_i\right) = \sum_i \P(A_i)$ (countable additivity).

Members of $\mathcal{A}$ are events.

The $\sigma$ -algebra is the part that is easy to dismiss and occasionally essential. It is the collection of sets to which a probability can be assigned; on $\Omega = \R$ the standard choice is the Borel $\sigma$ -algebra $\mathcal{B}(\R)$ , the smallest $\sigma$ -algebra containing all open intervals.

PropositionElementary consequences of the axioms

Let $(\Omega,\mathcal{A},\P)$ be a probability space and $A, B, A_1, A_2, \dots \in \mathcal{A}$ . Then

$\P(A^c) = 1 - \P(A)$ and $\P(\emptyset) = 0$ ;
if $A \subseteq B$ then $\P(A) \le \P(B)$ (monotonicity);
$\P(A \cup B) = \P(A) + \P(B) - \P(A\cap B)$ ;
if $A_1 \subseteq A_2 \subseteq \cdots$ then $\P(A_n) \uparrow \P\left(\bigcup_n A_n\right)$ .

LemmaUnion bound (Boole's inequality)

For any events $A_1, A_2, \dots$ ,

\P\left(\bigcup_{i} A_i\right) \le \sum_i \P(A_i) .

Key idea

The union bound is three lines to prove and it is the workhorse of this entire laboratory. It is how a bound for one random variable becomes a bound for the maximum of many; it is the source of the $\log N$ in Johnson–Lindenstrauss, of the $\log|\Fcal|$ in finite-class generalisation bounds, and of the covering-number factors in net arguments. It is also lossy: it ignores all dependence, and much of high-dimensional probability is about recovering what it throws away.

Random variables and distributions

DefinitionRandom variable

A random variable is a measurable map $X : \Omega \to \R$ , meaning $X^{-1}(B) \in \mathcal{A}$ for every $B \in \mathcal{B}(\R)$ . We write $\{X \in B\}$ for $X^{-1}(B)$ and $\P(X \in B)$ for $\P(X^{-1}(B))$ . A random vector is a measurable map into $\R^d$ , equivalently a $d$ -tuple of random variables.

PropositionThe distribution of a random variable

The map $\mu_X(B) := \P(X \in B)$ defines a probability measure on $(\R, \mathcal{B}(\R))$ , the distribution or law of $X$ . It is determined by the cumulative distribution function $F_X(t) = \P(X \le t)$ , which is non-decreasing, right-continuous, with limits $0$ at $-\infty$ and $1$ at $+\infty$ .

Independence

DefinitionIndependence

Events $A_1,\dots,A_n$ are independent if for every subset $S \subseteq \{1,\dots,n\}$

\P\left(\bigcap_{i\in S} A_i\right) = \prod_{i \in S}\P(A_i) .

Random variables $X_1,\dots,X_n$ are independent if the events $\{X_i \in B_i\}$ are independent for all Borel $B_i$ , equivalently if the joint law is the product of the marginals.

Almost sure events and Borel–Cantelli

DefinitionAlmost surely

An event $A$ holds almost surely (a.s.) if $\P(A) = 1$ . A statement holds a.s. if the set of outcomes where it holds is an event of probability one.

TheoremBorel–Cantelli lemmas

Let $A_1, A_2, \dots$ be events and let $\{A_n \text{ i.o.}\} = \bigcap_{n\ge1}\bigcup_{k \ge n} A_k$ be the event that infinitely many occur.

If $\sum_n \P(A_n) < \infty$ then $\P(A_n \text{ i.o.}) = 0$ .
If the $A_n$ are independent and $\sum_n \P(A_n) = \infty$ then $\P(A_n \text{ i.o.}) = 1$ .

Key idea

Borel–Cantelli is the standard route from a quantitative tail bound to an almost sure statement. If a concentration inequality gives $\P(|Z_n - z| > \eps_n) \le \delta_n$ with $\sum_n \delta_n < \infty$ , then $Z_n \to z$ almost surely. That is exactly how the strong law is upgraded from the weak law, and how almost-sure convergence of SGD is obtained from its expected-error bounds on the SGD page.

Problems

When is the union bound tight?Proof · Foundation · 15 min Pairwise independence does not imply independenceProof · Foundation · 15 min From an exponential tail bound to almost sure convergenceProof · Intermediate · 30 min

References

BookRick Durrett (2019). Probability: Theory and Examples
BookDavid Williams (1991). Probability with MartingalesShort, sharp, and the standard route into martingales used later for Azuma's inequality.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionElementary consequences of the axiomsproof includedMonotonicity, finite additivity, complements, continuity along monotone sequences and the union bound, all from the three axioms.
LemmaUnion boundproof includedThe probability of a union is at most the sum of the probabilities.
PropositionThe distribution of a random variableproof includedA random variable induces a probability measure on the real line, and only that measure matters for its law.
TheoremBorel–Cantelli lemmasproof includedSummable probabilities imply almost surely finitely many occurrences; for independent events the converse holds.

Problems (3)

All problems