Probability spaces

Let us start with the most basic definition. Let $\Omega$ be a non-empty set. A function $f: \Omega \rightarrow {\mathbb R}$ is said to be a probability distribution on $\Omega$ if it satisfies the following two conditions.

• For all $a \in \Omega$, we have $f(a) \geq 0$
• $\sum_{a \in \Omega} f(a) = 1$

We additionally say that $f$ is uniform if $f(a) = 1/|\Omega|$.

Definition 3

A finite probability space is a pair $(\Omega, {\mathbb P})$ where $\Omega$ is a non-empty finite set and ${\mathbb P}$ is a probability distribution on $\Omega$.

We refer to $\Omega$ as a sample space (containing every possible outcome of an experiment). Each element $x \in \Omega$ is called atomic event.

Definition 4

An event of a probability space is a subset $A \subseteq \Omega$. Atomic events are of the form $\{a\}$ for $a \in \Omega$.

For $A \subseteq \Omega$, we define

$${\mathbb P}[A] = \sum_{a \in A} {\mathbb P}[a]$$

Example 32

This definition implies that ${\mathbb P}[\Omega] = \sum_{a \in \Omega} {\mathbb P}[a]=1$. Moreover, ${\mathbb P}[\emptyset] = 0$.

Example 33

From this definition, in a uniform probability space, calculating the probability of event $A$ amounts to dividing $|A|$ by $|\Omega|$ (i.e., the number of cases we are interested in divided by the number of all cases).

Definition 5

An event $A$ is said to be trivial if ${\mathbb P}[A] = 0$ or ${\mathbb P}[A]= 1$.

In the following exercise, you will investigate some abstract mathematical structure of finite probability spaces.

Exercise 83

Prove: The number of trivial events (in a finite probability space) is a power of two.

Theorem 36 (Union bound)

Let $A_1,\ldots, A_n \subseteq \Omega$ be events. Then

$${\mathbb P}[A_1 \cup \cdots \cup A_n] \leq \sum_{i=1}^n {\mathbb P}[A_i]$$

Since we have already done a lot of tedious inductions in the lecture notes, this is again your turn to do it 😊

Exercise 84

Prove the union bound by induction on $n$. Argue that the equality holds if and only if every pair $A_i$ and $A_j$ is almost disjoint (${\mathbb P}[A_i \cap A_j] = 0$).

📄️ Coin tossingSingle Page

📄️ Balls and binsSingle Page

📄️ Random graphs: The Erdös-Rényi modelSingle Page