Introduction

Uncertainty is all around us! Most events in life involve some uncertainty, from our chances to succeed in a career to our luck finding a parking spot. So, how can we express events involving uncertainty, likelihood, risk, or chance? The theory of probability provides a rigorous framework to reason about uncertainty, quantify it, and study the laws that govern chance. It is thanks to probability that much of science, engineering, and other areas have made significant progress today. An example is artificial intelligence, where probability allowed the field to make a huge leap by modeling uncertainty in applications as diverse as machine translation and robotics.

Prerequisites: Set theory, functions, and counting.

1 Basic Definitions

Definition 1: Random Experiment

A random experiment consists of a process whose outcome cannot be predicted with certainty, but the set of possible outcomes is known.

Definition 2: Sample Space

The sample space S of an experiment is the set of all possible outcomes of the experiment.

Example 1

1. Single Coin Flip

   • Sample Space: $S = \{H, T\}$
   • Where H represents Heads and T represents Tails

2. Two Coin Flips

   • Sample Space: $S = \{HH, HT, TH, TT\}$
   • Each outcome represents the sequence of results

3. Single Die Roll

   • Sample Space: $S = \{1, 2, 3, 4, 5, 6\}$

4. Two Dice Roll

   • Sample Space size: $|S| = 6 × 6 = 36$

Probability Functions

Definition 3: Probability Function A probability function P takes an outcome $s \in S$ and returns the probability of $s$, denoted

$P : S \rightarrow [0, 1]$

Subject to these conditions:

1. $0 \leq P(s) \leq 1$ for all $s \in S$
2. The sum of probabilities of all outcomes equals 1: $$\sum_{s\in S} P(s) = 1$$

Assigning Probabilities

For finite sample spaces where all outcomes are equally likely, the probability of an outcome s ∈ S is given by:

$$P(s) = 1/|S|$$

Example 2: Fair Coin Toss

For a single fair coin toss:

• $P(H) = 1/2$
• $P(T) = 1/2$

Example 3: Three Fair Coin Tosses

• Sample Space: $S = \{TTT, TTH, THT, THH, HTT, HTH, HHT, HHH\}$
• $|S| = 2^3 = 8$
• For any outcome $s \in S: P(s) = 1/8$

2 Events

Instead of individual outcomes, we might be interested in a subset of the sample space with some characteristics. In the example above with $S = \{TTT, TTH, THT, THH, HTT, HTH, HHT, HHH\}$, an event could be "Getting exactly two Tails in flipping a fair coin three time in a row." The event is then the subset of all outcomes fulfilling the event description. In this case, this subset is $\{TTH, THT, HTT\} \subseteq S$

Definition 4 Event: An event is any subset $A$ of the sample space $S$, $A \subseteq S$

Definition 5 Probability of an event: The probability of $A$, denoted $P(A)$ is the sum of the probabilities of all outcomes that belong to A.

$$P(A) = \sum_{a \in A} P(a)$$

Note: $0 \leq P(A) \leq 1$ for all $A \subseteq S$

Example: We toss a coin five times in a row.

1. Let A denotes the event that exactly one Heads emerges.

   $A = \{HTTTT, THTTT, TTHTT, TTTHT, TTTTH\}$ A contains 5 outcomes, each of which has a probability of 1/32.

$P(A) = 5/32$

Let $S$ be a sample space and let $A$ and $B$ be two events. The following properties hold:

1. $P(\emptyset) = 0$
2. $P(S) = 1$
3. $P(\bar{A}) = 1 - P(A)$ where $\bar{A}$ denotes the complement of $A$.
4. $P(A \cup B) = P(A) + P(B) - P(A \cap B)$
5. $P(A \cup B) \leq P(A) + P(B)$
6. If A and B are disjoint, i.e., $A \cap B = \emptyset$ then $P(A \cup B) = P(A) + P(B)$
7. If $A \subseteq B$ then $P(A) \leq P(B)$