## Probability

### The Analysis of Data, volume 1

Measure Theory: sigma-algebras

## E.1. $\sigma$-Algebras

We attempt in this book to circumvent the use of measure theory as much as possible. However, in several places where measure theory is essential we make an exception (for example the limit theorems in Chapter 8 and Kolmogorov's extension theorem in Chapter 6). Sections containing such exceptions are marked by an asterisk.

This chapter contains a introduction to the parts of measure theory that are the most essential to probability theory. The next chapter covers Lebesgue integration and the Lebesgue measure.

Definition E.1.1. An algebra $\mathcal{C}$ is a non-empty set of sets that satisfies: (i) $\Omega\in\mathcal{C}$, (ii) if $A\in\mathcal{C}$ then $A^c\in\mathcal{C}$, and (iii) if $A,B\in\mathcal{C}$ then $A\cup B\in\mathcal{C}$.

1. By induction, if $\mathcal{C}$ is an algebra then $A_1,\ldots,A_k\in\mathcal{C}$ implies $A_1\cup\cdots\cup A_n\in\mathcal{C}$.
2. Using De-Morgan's rule and the second property above, $A_1,\ldots,A_k\in\mathcal{C}$ implies $A_1\cap\cdots\cap A_n\in\mathcal{C}$,
3. A more compact definition of an algebra is a set containing $\Omega$ that is closed under finite unions, finite intersections, and complements.
Definition E.1.2. A $\sigma$-algebra is a non-empty set of sets that is closed under countable unions, countable intersections, and complements.

In other words, if $A_n, n\in\mathbb{N}$ reside in a $\sigma$-algebra $\mathcal{A}$ then we also have $\cup_{n\in\mathbb{N}} A_n\in\mathcal{A}$, $\cap_{n\in\mathbb{N}} A_n\in\mathcal{A}$ and $A_n^c\in\mathcal{A}$.

Definition E.1.3. A measurable space $(\Omega,\mathcal{F})$ consists of a set $\Omega$ and a $\sigma$-algebra of subsets of $\Omega$.
Example E.1.1. The power set $2^\Omega$ is a $\sigma$-algebra. It contains all subsets and is therefore closed under complements and countable unions and intersections.

Note that every $\sigma$-algebra necessarily includes $\emptyset$ and $\Omega$ since $A_n\cap A_n^c=\emptyset$ and $A_n\cup A_n^c=\Omega$. As a consequence, a $\sigma$-algebra is also closed under finite unions and intersections (define $A_k$ above for $k\geq c$ to be either $\emptyset$ or $\Omega$), implying that a $\sigma$ algebra is also an algebra.

Proposition E.1.1. A set of sets $\mathcal{A}$ is a $\sigma$-algebra if and only if (i) $\Omega\in\mathcal{A}$, (ii) $A\in\mathcal{A}$ implies $A^c\in\mathcal{A}$, and (iii) if $A_n\in\mathcal{A}$ for $n\in\mathbb{N}$ then $\cup_n A_n\in\mathcal{A}$.
Proof. If $\mathcal{A}$ is a $\sigma$-algebra then it obviously satisfies the three properties. If $\mathcal{A}$ satisfies the three properties, it is obviously closed under union and under complements. It remains to show that it is closed under intersections. Let $B_n, n\in\mathbb{N}$ be a sequence of sets in $\mathcal{A}$. Since $\mathcal{A}$ is closed under complements, we have $A_n\defeq B_n^c\in\mathcal{A}$ and also $\cup_n A_n\in\mathcal{A}$. Taking the complement again and applying De-Morgan's theorem we get $(\cup_n A_n)^c=\cap_n A_n^c=\cap_n B_n\in\mathcal{A}$.
Proposition E.1.2. An intersection of multiple $\sigma$-algebras is also a $\sigma$-algebra.
Proof. Since each $\sigma$ algebra contains $\Omega$ their intersection is non-empty and it contains $\Omega$ as well. If $A$ is a member of the intersection then it is a member of all the $\sigma$-algebras and therefore $A^c$ is also a member of all the $\sigma$-algebras. It follows that $A^c$ is also in the intersection. The intersections of the $\sigma$ algebras is closed under countable unions and intersections for the same reason.
Proposition E.1.3. Given a set of sets $\mathcal{A}$, there exists a unique minimal $\sigma$-algebra containing $\mathcal{A}$. We refer to this $\sigma$-algebra as the $\sigma$-algebra generated by $\mathcal{A}$ and denote it as $\sigma(\mathcal{A})$.

In other words, there is a $\sigma$-algebra containing $\mathcal{A}$ that is a subset of all other $\sigma$-algebras containing $\mathcal{A}$.

Proof. Since the power set $2^{\Omega}$ is a $\sigma$-algebra containing $\mathcal{A}$ there exists at least one $\sigma$-algebra containing $\mathcal{A}$. We define the smallest $\sigma$-algebra to be the intersection of all $\sigma$-algebras containing $\mathcal{A}$. It is a $\sigma$-algebra by Proposition E.1.2 and by construction it is minimal in the sense that is a subset of all other $\sigma$-algebras.
Corollary E.1.1. If $\mathcal{C}$ is a $\sigma$-algebra then $\sigma(\mathcal{C})=\mathcal{C}$.
Proof. This is a direct corollary of the definition of $\sigma(\mathcal{C})$ as the smallest $\sigma$-algebra containing $\mathcal{C}$ and the fact that it is uniquely defined.

It is desirable to have an efficient mechanism for producing the smallest $\sigma$-algebra containing a set of sets $\mathcal{C}$. A conceptual mechanism is as follows: (i) create a set $\mathcal{C}'$ containing the sets in $\mathcal{C}$, their complements, and their countable unions and intersections, (ii) repeat step (i) with $\mathcal{C}'$ substituting $\mathcal{C}$. Unfortunately, the mechanism above is not computationally efficient as it may never terminate. The proposition above asserts the existence of a smallest $\sigma$-algebra but does not offer any assistance into constructing it.

Definition E.1.4. Let $\mathcal{C}$ be a set of sets and $U$ be a set. We denote $\mathcal{C}\cap U = \{C\cap U: C\in\mathcal{C}\}.$
Proposition E.1.4. Let $\mathcal{C}$ be a $\sigma$-algebra over $\Omega$ and $U\subset \Omega$. Then $\mathcal{C}\cap U$ is a $\sigma$-algebra over $U$.
Proof. Since $U=\Omega\cap U$, we have $U\in\mathcal{C}\cap U$. If $B\in\mathcal{C}\cap U$ then $B= C\cap U$ for some $C\in\mathcal{C}$ and therefore $U\setminus B = (\Omega \setminus C) \cap U \in \mathcal{C}\cap U$ (since $\Omega\setminus C=C^c\in\mathcal{C}$). If $B_n=C_n\cap U, n\in\mathbb{N}$ is a sequence of sets in $\mathcal{C}\cap U$ then $\cup C_n\in\mathcal{C}$ and $\bigcup_{n\in\mathbb{N}} B_n = \bigcup_{n\in\mathbb{N}} (U\cap C_n) = \left(\bigcup_{n\in\mathbb{N}} C_n\right) \cap U \in \mathcal{C}\cap U.$
Proposition E.1.5. Let $\mathcal{C}$ be a set of sets and $U$ be a set. Then $\sigma(\mathcal{C}\cap U) = \sigma(\mathcal{C}) \cap U.$
Proof. By the previous proposition $\sigma(\mathcal{C})\cap U$ is a $\sigma$-algebra and $\sigma(\mathcal{C}\cap U) \subset \sigma(\sigma(\mathcal{C})\cap U) =\sigma(\mathcal{C})\cap U.$ It remains to show that $\sigma(\mathcal{C}) \cap U \subset \sigma(\mathcal{C}\cap U)$.

We show that the set $\mathcal{G}=\{A:A\cap U\in\sigma(\mathcal{C}\cap U)\}$ is a $\sigma$-algebra. The first requirement holds since $\Omega\in\mathcal{G}$. If $A\in\mathcal{G}$ then $A\cap U\in\sigma(\mathcal{C}\cap U)$, implying that $A^c\cap U=U\setminus (A\cap U)\in\sigma(\mathcal{C}\cap U)$ as well (the set difference of two sets in a $\sigma$ algebra is in the $\sigma$ algebra as well). It follows that $A^c\in\mathcal{G}$, showing that the second requirement holds as well. To show the third requirement, note that if $A_n\in\mathcal{G}$ for $n\in\mathbb{N}$ then $(\cup_n A_n)\cap U = \cup_n (A_n\cap U)\in\sigma(\mathcal{C}\cap U)$ (since $A_n\cap U\in\sigma(\mathcal{C}\cap U)$) and thus $\cup_n A_n\in\mathcal{G}$.

Since $\mathcal{G}$ is a $\sigma$-algebra and $\mathcal{C}\subset \mathcal{G}$ (if $A\in\mathcal{C}$ then $A\cap U\in \sigma(\mathcal{C}\cap U)$ implying that $A\in\mathcal{G}$) we have $\sigma(\mathcal{C})\subset \sigma(\mathcal{G}) = \mathcal{G}.$ (The last equality holds since $\mathcal{G}$ is a $\sigma$-algebra.) If $A\in\sigma(\mathcal{C})$ then $A\in\mathcal{G}$ and $A\cap U\in\sigma(\mathcal{C}\cap U)$ implying that $A\in \sigma(\mathcal{C}\cap U)$. It follows that $\sigma(\mathcal{C}) \cap U \subset \sigma(\mathcal{C}\cap U)$.