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 Tossing

This is an example that everyone has seen at some point in their studies. Let us take a formal view on it. If we toss a coin $k$ times, we represent an outcome by a string $s \in \{0,1\}^k$ where $s_i = 1$ means that the $i$-th coin toss turns up head.

📄️ Balls and Bins

We throw $m$ balls into $n$ bins. Assume that any ball is equally likely to land into any bin. We can represent each outcome by a function $f: [m] \rightarrow [n]$ where $f(i) = j$ means that the $i$-th ball lands into the $j$-th bin.

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

When we talk about random graphs, we refer to graphs generated as an outcome of the following experiment. Let $n$ be the number of vertices. For each $\{i,j\} \in {[n] \choose 2}$, we toss an unbiased coin and if the coin turns up head, there is an edge connecting $\{i,j\}$.