Probability Theory

1. Measure-Theoretic Foundations

1.1 Probability Space

Definition 1.1 (Sample space): The sample space Ω\Omega is a non-empty set.
Note: The sample space Ω\Omega is the space of all outcomes ω∈Ω\omega \in \Omega of a random experiment.
Definition 1.2 (Complement): For any subset A⊆Ω\setA \subset \Omega, the complement is Ac=Ω∖A\setA^c = \Omega \setminus \setA.

We will use the notion of collections and families of subsets of Ω\Omega frequently.

Definition 1.3 (Collection): The set C⊆P(Ω)\colC \subset \powerset(\Omega) is called a collection.
Definition 1.4 (Familiy): Let I\setI be a non-empty index set. A family of subsets of Ω\Omega is a mapping I↦P(Ω)\setI \mapsto \powerset(\Omega). We denote it by (Ai)i∈I\family*{\setA}{i}{\setI}.
Note:
  • We write (Ai)i∈I⊆C\family*{\setA}{i}{\setI} \subset \colC to denote ∀i∈I:Ai∈C\forall i \in \setI : \setA_i \in \colC.
  • If a collection is the image of a family (Ai)i∈I\family*{\setA}{i}{\setI}, we denote it with {Ai}i∈I={S∈P(Ω) | ∃i∈I:S=Ai}\collection*{\setA}{i}{\setI} = \set{\setS \in \powerset(\Omega) \mid \exists i \in \setI: \setS = \setA_i}.

We introduce the concept of a σ\sigma-algebra.

Definition 1.5 (σ\sigma-algebra): A collection F\sigmaF is a σ\sigma-algebra on Ω\Omega if
  1. Ω∈F\Omega \in \sigmaF
  2. If A∈F\evA \in \sigmaF, then Ac∈F\evA^c \in \sigmaF
  3. If (An)n∈N⊆F\family{\setA} \subset \sigmaF, then ⋃n∈NAn∈F\UnionN \evA_n \in \sigmaF
Note:
  • The elements A∈F\setA \in \sigmaF are called measurable sets or events.
  • An arbitrary intersection of σ\sigma-algebras is a σ\sigma-algebra.
Proposition 1.6 (Stability under countable intersections): If (An)n∈N⊆F\family{\setA} \subset \sigmaF, then ⋂n∈NAn∈F\IntersectN \evA_n \in \sigmaF.
Note: The tuple (Ω,F)(\Omega, \sigmaF) is called a measurable space.
Definition 1.7 (Probability measure): The function P:F→[0,1]\P : \sigmaF \to [0,1] is a probability measure on the measurable space (Ω,F)(\Omega, \sigmaF) if
  1. P ⁣(Ω)=1\probP{\Omega} = 1
  2. Let (An)n∈N⊆F\family{\evA} \subset \sigmaF with Ai\evA_i, Aj\evA_j pairwise disjoint for any i≠ji \neq j, then P(⋃n∈NAn)=∑n∈NP ⁣(An) \probP*{\UnionN \setA_n} = \sumN \probP{\setA_n}
Note: For an event A∈F\evA \in \sigmaF, the quantity P ⁣(A)\probP{\evA} measures the probability that an outcome ω∈Ω\omega \in \Omega lies in A\evA.

We introduce the concept of a probability space.

Definition 1.8 (Probability space): A probability space is a triple (Ω,F,P)(\Omega, \sigmaF, \P), where
  • Ω\Omega is a sample space
  • F\sigmaF is a σ\sigma-algebra on Ω\Omega
  • P\P is a probability measure on (Ω,F)(\Omega, \sigmaF)
Note: In this text, unless noted otherwise, we consider the probability space as fixed to a specific triple (Ω,F,P)(\Omega, \sigmaF, \P).

We present some important properties of the probability measure.

Proposition 1.9 (Probability of complement): Let A∈F\evA \in \sigmaF, then P ⁣(Ac)=1−P ⁣(A)\probP{\evA^c} = 1 - \probP{\evA}.
Proposition 1.10 (Continuity of probability measure): Let (An)n∈N⊆F\family{\evA} \subset \sigmaF.
  • If ∀n∈N:An⊆An+1\forall n \in \N: \evA_n \subset \evA_{n+1}, then P(lim⁡n→∞An)=lim⁡n→∞P ⁣(An) \probP*{\liminfty \evA_n} = \liminfty \probP{\evA_n} i.e. P\P is continuous from below.
  • If ∀n∈N:An+1⊆An\forall n \in \N: \evA_{n+1} \subset \evA_n, then P(lim⁡n→∞An)=lim⁡n→∞P ⁣(An) \probP*{\liminfty \evA_n} = \liminfty \probP{\evA_n} i.e. P\P is continuous from above.
Proposition 1.11 (Union bound): Let (An)n∈N⊆F\family{\evA} \subset \sigmaF, then P(⋃n∈NAn)≤∑n∈NP ⁣(An) \probP*{\UnionN \evA_n} \leq \sum_{n \in \N} \probP{\evA_n}
Proposition 1.12 (Bonferoni inequality): Let (An)n∈N⊆F\family{\evA} \subset \sigmaF, then P(⋂n∈NAn)≥1−∑n∈NP ⁣(Anc) \probP*{\IntersectN \evA_n} \geq 1 - \sum_{n \in \N} \probP{\evA_n^c}

1.2 Collection-Generated σ\sigma-Algebra

The σ\sigma-algebra generated by a collection C\colC is the collection of all events whose occurence is determined once we know whether ω\omega in A\setA for all A∈C\setA \in \colC. We formalize this concept.

Definition 1.13 (Collection-generated σ\sigma-algebra): Let C\colC be a collection, then σ(C)=⋂{F~⊆P(Ω) | C⊆F~ and F~ is a σ-algebra} \sigma(\colC) = \Intersect \set{\tilde{\sigmaF} \subset \powerset(\Omega) \mid \text{C⊆F~\colC \subset \tilde{\sigmaF} and F~\tilde{\sigmaF} is a σ\sigma-algebra}} is the σ\sigma-algebra generated by C\colC.
Note:
  • σ(C)\sigma(\colC) is the smallest σ\sigma-algebra containing C\colC.
  • If F\sigmaF is a σ\sigma-algebra, then σ(F)=F\sigma(\sigmaF) = \sigmaF.
  • If C⊆C~\colC \subset \tilde{\colC}, then σ(C)⊆σ(C~)\sigma(\colC) \subset \sigma(\tilde{\colC}).
  • If C\colC is finite, σ(C)\sigma(\colC) is the set of all possible unions of atoms of C\colC.

We take a closer look at a special case of collection-generated σ\sigma-algebras.

Recap (Topological space): A topological space is a tuple (E,T)(\setE, \colT) where E\setE is a non-empty set and T\colT is a collection of subsets satisfying
  1. ∅,E∈T\varnothing, \setE \in \colT
  2. If (Oi)i∈I⊆T\family*{\setO}{i}{\setI} \subset \colT, then ⋃i∈IOi∈T\Union_{i \in \setI} \setO_i \in \colT
  3. If (Oi)i∈I⊆T\family*{\setO}{i}{\setI} \subset \colT with I\setI finite, then ⋂i∈IOi∈T\Intersect_{i \in \setI} \setO_i \in \colT
Definition 1.14 (Borel σ\sigma-algebra): Let (E,T)(\setE, \colT) be a topological space. Then B(E)=σ(T)\borelB(\setE) = \sigma(\colT) is the Borel σ\sigma-algebra of E\setE.
Proposition 1.15 (Borel σ\sigma-algebra of R\R): Let (R,{(a,b) | a,b∈R})(\R, \set{(a,b) \mid a,b \in \R}) be the standard topology on R\R, we have B(R)=σ({(a,b) | a,b∈R}) \borelB(\R) = \sigma(\set{(a,b) \mid a,b \in \R})
Note: There are multiple equivalent definitions of B(R)\borelB(\R) such as:
  • B(R)=σ({(a,b] | a,b∈R})\borelB(\R) = \sigma(\set{(a,b] \mid a,b \in \R})
  • B(R)=σ({(−∞,a) | a∈R})\borelB(\R) = \sigma(\set{(-\infty,a) \mid a \in \R})
  • B(R)=σ({(−∞,a] | a∈R})\borelB(\R) = \sigma(\set{(-\infty,a] \mid a \in \R})

1.3 λ\lambda- and π\pi-Systems

Definition 1.16 (λ\lambda-system): A collection D\colD is a λ\lambda-sytem if
  • Ω∈D\Omega \in \colD
  • If A∈D\setA \in \colD, then Ac∈D\setA^c \in \colD
  • If (An)n∈N⊆D\family{\setA} \subset \colD pairwise disjoint, then ⋃n∈NAn∈D\UnionN \setA_n \in \colD
Note: If D\colD is a σ\sigma-algebra, then D\colD is a λ\lambda-system. The converse does not hold in general. To see that, let for example Ω={1,2,3,4}\Omega = \set{1,2,3,4} and D={∅,Ω,{1,2},{3,4},{1,3},{2,4}}\colD = \set{\varnothing, \Omega, \set{1,2}, \set{3,4}, \set{1,3}, \set{2,4}}. Then D\colD is a λ\lambda-system but not a σ\sigma-algebra.

The notion of a λ\lambda-sytem is very similar to a σ\sigma-algebra. The only difference lies in the third condition, where it suffices that D\colD is stable under disjoint countable unions.

Definition 1.17 (Collection-generated λ\lambda-system): Let C\colC be a collection, then λ(C)=⋂{D~⊆P(Ω) | C⊆D~ and D~ is a λ-system} \lambda(\colC) = \Intersect \set{ \tilde{\colD} \subset \powerset(\Omega) \mid \text{C⊆D~\colC \subset \tilde{\colD} and D~\tilde{\colD} is a λ\lambda-system} } is the λ\lambda-system generated by C\colC.
Note:
  • λ(C)\lambda(\colC) is the smallest λ\lambda-system containing C\colC.
  • If D\colD is a λ\lambda-system, then λ(D)=D\lambda(\colD) = \colD.
  • If C⊆C~\colC \subset \tilde{\colC}, then λ(C)⊆λ(C~)\lambda(\colC) \subset \lambda(\tilde{\colC}).
  • As σ(C)\sigma(\colC) is a λ\lambda-system containing C\colC, we have λ(C)⊆σ(C)\lambda(\colC) \subset \sigma(\colC).
The converse of the latter property does not hold in general. To see that let Ω\Omega and D\colD be as defined previously. Then λ(D)=D\lambda(\colD) = \colD but σ(D)=P(Ω)\sigma(\colD) = \powerset(\Omega).
Definition 1.18 (π\pi-system): A collection D\colD is a π\pi-system if for any (Ai)i∈I⊆D\family*{\setA}{i}{\setI} \subset \colD with I\setI finite, we have ⋂{Ai}i∈I∈D\Intersect \collection*{\setA}{i}{\setI} \in \colD.
Note:
  • In other words, the only condition for a collection to be a π\pi-system is that it is closed under finite intersections.
  • By induction, it is sufficient to show if A,B∈C\setA, \setB \in \colC then A∩B∈C\setA \intersect \setB \in \colC.
Proposition 1.19 (π\pi and λ\lambda implies σ\sigma): Let D\colD be a π\pi-system. Then it is a σ\sigma-algebra if and only if it is a λ\lambda-system.

Dynkin's Theorem asserts that the inclusion λ(C)⊆σ(C)\lambda(\colC) \subset \sigma(\colC) is an equality when C\colC is a π\pi-system.

Theorem 1.20 (Dynkin's Theorem): Let C\colC be a π\pi-sytem. Then, λ(C)=σ(C)\lambda(\colC) = \sigma(\colC).
Proof: TODO

Dynkin's Theorem simplifies proofs for generated σ\sigma-algebras σ(C)\sigma(\colC) by allowing one to verify a property merely for the λ\lambda-system λ(C)\lambda(\colC), which requires the easier condition of stability under disjoint countable unions rather than general countable unions. Consequently, if C\colC is stable under finite intersection, the theorem guarantees that any property holding for λ(C)\lambda(\colC) is valid for σ(C)\sigma(\colC). An example application is shown in the following.

Example (Uniqueness of measure): Let μ\mu and ν\nu be two measures on the measurable space (R,B(R))(\R, \borelB(\R)) for which ∀a∈R:μ((−∞,a])=ν((−∞,a])\forall a \in \R : \mu((-\infty,a]) = \nu((-\infty,a]). We want to prove that μ\mu and ν\nu are equal on the entirety of B(R)\borelB(\R). We note ∀a∈R:μ((−∞,a])=ν((−∞,a])  ⟺  ∀A∈C:μ(A)=ν(A) \forall a \in \R : \mu((-\infty,a]) = \nu((-\infty,a]) \iff \forall \setA \in \colC : \mu(\setA) = \nu(\setA) for C={(−∞,a] | a∈R}\colC = \set{(-\infty,a] \mid a \in \R}. We show that C\colC is a π\pi-system and that the property of interest, the equality of μ\mu and ν\nu, holds on λ(C)\lambda(\colC).
  1. C\colC is a π\pi-system: Let A1=(−∞,a1]∈C\setA_1 = (-\infty,a_1] \in \colC and A2=(−∞,a2]∈C\setA_2 = (-\infty,a_2] \in \colC. Without loss of generality, let a1≤a2a_1 \leq a_2. Then, A1∩A2=A1∈C\setA_1 \intersect \setA_2 = \setA_1 \in \colC.
  2. μ=ν\mu = \nu holds on λ(C)\lambda(\colC): Let L={A∈B(R) | μ(A)=ν(A)}\colL = \set{\setA \in \borelB(\R) \mid \mu(\setA) = \nu(\setA)} be the collection of all subsets where the measures agree. By hypothesis, C⊆L\colC \subset \colL. We prove that L\colL is a λ\lambda-system. First, Ω∈L\Omega \in \colL since μ(Ω)=ν(Ω)\mu(\Omega) = \nu(\Omega). Second, if A∈L\setA \in \colL, then μ(Ac)=1−μ(A)=1−ν(A)=ν(Ac)\mu(\setA^c) = 1 - \mu(\setA) = 1 - \nu(\setA) = \nu(\setA^c), so Ac∈L\setA^c \in \colL. Third, if (An)n∈N⊆L\family{\setA} \subset \colL pairwise disjoint, then μ ⁣(⋃n∈NAn)=∑n∈Nμ(An)=∑n∈Nν(An)=ν ⁣(⋃n∈NAn) \mu\of{\UnionN \setA_n} = \sumN \mu(\setA_n) = \sumN \nu(\setA_n) = \nu\of{\UnionN \setA_n} so ⋃n∈NAn∈L\UnionN \setA_n \in \colL. Since L\colL is a λ\lambda-system containing C\colC, we have λ(C)⊆L\lambda(\colC) \subset \colL. Therefore, μ=ν\mu = \nu on λ(C)\lambda(\colC).
By Dynkin's Theorem, λ(C)=σ(C)=B(R)\lambda(\colC) = \sigma(\colC) = \borelB(\R). Thus μ=ν\mu = \nu holds on B(R)\borelB(\R).
Note: The technique used in step 2. is called the Good Sets Principle. It allows one to prove that a property A\mathfrak{A} holds for all sets in λ(C)\lambda(\colC) without constructing the sets explicitly. The logic proceeds in three steps.
  1. One defines the collection of good sets L={A∈σ(C) | A(A) is true}\colL = \set{ \setA \in \sigma(\colC) \mid \mathfrak{A}(\setA) \text{ is true}}.
  2. One shows that C\colC is contained in L\colL and that L\colL forms a λ\lambda-system.
  3. By the minimality of generated systems, one concludes that λ(C)⊆L\lambda(\colC) \subseteq \mathcal{L}, implying A\mathfrak{A} holds for λ(C)\lambda(\colC).

1.4 Independence of Collections

The language of probability theory relies on measure theory, together with the concept of independence. We introduce the concept of independence for a collection of events.

Definition 1.21 (Independent collection): Let I\setI be an arbitrary index set. A collection C={Ai}i∈I⊆F\colC = \collection*{\setA}{i}{\setI} \subset \sigmaF is called independent if for each finite index set J⊆I\setJ \subset \setI we have P(⋂j∈JAj)=∏j∈JP ⁣(Aj) \probP*{\Intersect_{j \in \setJ} \evA_j} = \prod_{j \in \setJ} \probP{\evA_j}

We extend the concept of independence to family of collections.

Definition 1.22 (Independent family of collections): Let K\setK be an arbitrary index set and for each k∈Kk \in \setK, let Ck⊆F\colC_k \subset \sigmaF be a collection of events. The family of collections (Ck)k∈K\family*{\colC}{k}{\setK} is called independent if for each finite index set {k1,…,kn}⊆K\set{k_1, \ldots, k_n} \subset \setK we have ∀Ak1∈Ck1  ⋯  ∀Akn∈Ckn:P(⋂i=1nAki)=∏i=1nP ⁣(Aki) \forall \evA_{k_1} \in \colC_{k_1} \sep \cdots \sep \forall \evA_{k_n} \in \colC_{k_n} : \probP*{\Intersect_{i = 1}^n \evA_{k_i}} = \prod_{i = 1}^n \probP{\evA_{k_i}}
Note:
  • The independence of a family of collections (Ck)k∈K\family*{\colC}{k}{\setK} does not imply that each individual collection Ck\colC_k is an independent collection.
  • If each family is made of a single event, i.e. Ck={Ak}\colC_k = \set{\setA_k}, then the independence of the families family of collections (Ck)k∈K\family*{\colC}{k}{\setK} is equivalent to the independence of the collection C=⋃k∈KCk\colC = \Union_{k \in \setK} \colC_k.
  • (Ck)k∈K\family*{\colC}{k}{\setK} is independent if and only if (Cki)ki∈K~\family*{\colC}{k_i}{\tilde{\setK}} is independent for each finite index set K~⊆K\tilde{\setK} \subset \setK.
  • Let n∈Nn \in \N. The finite family of collections C1,…,Cn⊆F\colC_1, \ldots, \colC_n \subset \sigmaF is independent if and only if ∀A1∈C1∪{Ω}  ⋯  ∀An∈Cn∪{Ω}:P(⋂i=1nAi)=∏i=1nP ⁣(Ai) \forall \evA_{1} \in \colC_{1} \union \set{\Omega} \sep \cdots \sep \forall \evA_{n} \in \colC_{n} \union \set{\Omega} : \probP*{\Intersect_{i = 1}^n \evA_{i}} = \prod_{i = 1}^n \probP{\evA_{i}}

The following proposition asserts that to establish independence of σ\sigma-algebras, it suffices to prove independence of generating π\pi-systems.

Proposition 1.23 (σ\sigma-algebras inherit independence): Let I\setI be an arbitrary index set and for each i∈Ii \in \setI, let Ci⊆F\colC_i \subset \sigmaF be a π\pi-system. The family of collections (Ci)i∈I\family*{\colC}{i}{\setI} is independent if and only if the family of collections (σ(Ci))i∈I(\sigma(\colC_i))_{i \in \setI} is independent.
Proof: TODO

The following is a direct consequence of the previous proposition.

Proposition 1.24 (Independent collection of complements): Let I\setI be an arbitrary index set. The collection {Ai}i∈I\collection*{\setA}{i}{\setI} is independent if and only if the collection {Aic}i∈I\{\setA_i^c\}_{i \in \setI} is independent.