Introduction to Probability

Foundations

Sample spaces, events, counting, and probability axioms

• Sample Spaces and Events

  Experiments and Outcomes

  Probability theory provides mathematical tools for reasoning about uncertain events. The starting point is the notion of an experiment: a process that produces an outcome.

  Examples:

  • Rolling a die: outcome is which face lands uppermost
  • Flipping a coin three times: outcome is a sequence like HTH
  • Measuring the time until a component fails: outcome is a non-negative real number

  Sample Space

  The sample space $\Omega$ (or $S$) is the set of all possible outcomes of an experiment.

  Discrete Sample Spaces

  A sample space is discrete if it is finite or countably infinite.

  Example (coin flip): $\Omega = \{H, T\}$

  Example (two dice): $\Omega = \{(i,j) : i,j \in \{1,2,3,4,5,6\}\}$ has 36 outcomes.

  Example (coin flips until heads): $\Omega = \{1, 2, 3, \ldots\}$ is countably infinite.

  Continuous Sample Spaces

  A sample space is continuous if outcomes can take any value in an interval.

  Example (time to failure): $\Omega = [0, \infty)$

  Example (temperature): $\Omega = \mathbb{R}$ or some bounded interval.

  Events

  An event is a subset of the sample space: a collection of outcomes. We say an event $E$ occurs if the actual outcome of the experiment is in $E$.

  Example (single die):

  • Event “rolling an even number”: $E = \{2, 4, 6\}$
  • Event “rolling at least 5”: $F = \{5, 6\}$

  Example (two dice):

  • Event “sum equals 7”: $E = \{(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)\}$
  • Event “both dice show the same”: $F = \{(1,1), (2,2), (3,3), (4,4), (5,5), (6,6)\}$

  Special Events

  • The entire sample space $\Omega$ is the certain event: it always occurs.
  • The empty set $\emptyset$ is the impossible event: it never occurs.
  • An elementary event (or atomic event) contains exactly one outcome: $\{x\}$ for some $x \in \Omega$.

  Event Operations

  Since events are sets, we can combine them using set operations:

  Operation	Notation	Meaning
  Union	$E \cup F$	$E$ or $F$ (or both) occurs
  Intersection	$E \cap F$ or $EF$	Both $E$ and $F$ occur
  Complement	$E^c$ or $\bar{E}$	$E$ does not occur
  Difference	$E - F$ or $E \setminus F$	$E$ occurs but $F$ does not

  

  Mutually Exclusive Events

  Events $E$ and $F$ are mutually exclusive (or disjoint) if they cannot both occur: $E \cap F = \emptyset$.

  Example (single die): The events “roll an even number” $\{2,4,6\}$ and “roll a 3” $\{3\}$ are mutually exclusive. But “roll an even number” and “roll at most 4” $\{1,2,3,4\}$ are not mutually exclusive: both occur if we roll 2 or 4.

  The Event Space

  The collection of all events forms a sigma-algebra (or $\sigma$-algebra), denoted $\mathcal{F}$. This is a collection of subsets of $\Omega$ satisfying:

  1. $\Omega \in \mathcal{F}$
  2. If $E \in \mathcal{F}$, then $E^c \in \mathcal{F}$ (closed under complements)
  3. If $E_1, E_2, \ldots \in \mathcal{F}$, then $\bigcup_{i=1}^{\infty} E_i \in \mathcal{F}$ (closed under countable unions)

  For finite sample spaces, $\mathcal{F}$ is typically the power set $\mathcal{P}(\Omega)$: all possible subsets.

  Why sigma-algebras? They ensure we can assign probabilities consistently. If we can talk about the probability of $E$ and of $F$, we should also be able to talk about the probability of $E^c$ and $E \cup F$.

  De Morgan’s Laws

  For any events $E$ and $F$:

  $(E \cup F)^c = E^c \cap F^c$ $(E \cap F)^c = E^c \cup F^c$

  Intuition: For $E \cup F$ to not occur, both $E$ and $F$ must not occur. For $E \cap F$ to not occur, either $E$ or $F$ must not occur.

  Partition

  A partition of $\Omega$ is a collection of mutually exclusive events $F_1, F_2, \ldots, F_n$ whose union is $\Omega$:

  $F_i \cap F_j = \emptyset \text{ for } i \neq j$ $\bigcup_{i=1}^{n} F_i = \Omega$

  Partitions are crucial for the Law of Total Probability.

  Example (single die): $\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}$ partitions the sample space.

  Example (blood type): $F_1 = \text{type A}, F_2 = \text{type B}, F_3 = \text{type AB}, F_4 = \text{type O}$ partitions by blood type.

  Summary

  Concept	Definition
  Sample space $\Omega$	Set of all possible outcomes
  Event $E$	Subset of the sample space
  Elementary event	Event containing one outcome
  Mutually exclusive	$E \cap F = \emptyset$
  Partition	Mutually exclusive events that cover $\Omega$

• Counting and the Product Rule

  Why Counting?

  Many probability problems reduce to counting: determining how many outcomes lie in an event. If we can count the total number of equally likely outcomes and count how many satisfy our criterion, the probability is their ratio.

  The Product Rule

  Principle: If an experiment has $n_1$ possible outcomes, and for each of these, a second experiment has $n_2$ possible outcomes, then the combined experiment has $n_1 \times n_2$ possible outcomes.

  More generally, for $r$ experiments:

  $\text{Total outcomes} = n_1 \times n_2 \times \cdots \times n_r$

  Why does this work? Each outcome of the first experiment branches into $n_2$ outcomes of the second, each of those branches into $n_3$ outcomes of the third, and so on. The total is the product.

  

  Examples

  Example 1: Rolling Two Dice

  Each die has 6 outcomes. The pair of dice has $6 \times 6 = 36$ possible outcomes.

  Example 2: Coin Flips

  Three coin flips: each flip has 2 outcomes. Total: $2 \times 2 \times 2 = 8$ outcomes.

  The sample space: $\{HHH, HHT, HTH, HTT, THH, THT, TTH, TTT\}$

  Example 3: Licence Plates

  A licence plate has 3 letters followed by 3 digits. How many possible plates?

  • Each letter position: 26 choices
  • Each digit position: 10 choices
  • Total: $26^3 \times 10^3 = 17{,}576{,}000$

  Example 4: Hash Tables

  A hash table has 100 buckets. Two strings are hashed independently. How many ways can they be stored?

  Each string can go to any of 100 buckets. Total: $100 \times 100 = 10{,}000$ possible storage configurations.

  Ordered vs Unordered

  The product rule counts ordered outcomes: the sequence matters.

  Example (ordered): Drawing two balls from an urn with replacement, recording the order. If we have 5 balls, there are $5 \times 5 = 25$ ordered pairs.

  Example (unordered): If we only care about which two balls we get (not the order), we divide by 2! for each pair: $\frac{25 - 5}{2} + 5 = 15$ distinct unordered outcomes (the 5 pairs of the same ball, plus 20 ordered pairs reduced by a factor of 2).

  The Pigeonhole Principle

  Principle: If $n$ items are placed into $k$ boxes and $n > k$, at least one box contains at least $\lceil n/k \rceil$ items.

  Corollary: If $n$ items are placed into $n-1$ boxes, at least one box contains at least 2 items.

  Example: Hash Collisions

  A hash table has 100 buckets. We hash 950 strings.

  • Is it possible some bucket has no entries? Yes, the items might cluster.
  • Is it guaranteed at least one bucket has at least 2 entries? Yes: $950 > 100$, so by pigeonhole, at least one bucket has at least $\lceil 950/100 \rceil = 10$ entries.
  • Is it guaranteed at least one bucket has at least 11 entries? No: we could potentially distribute 950 items with 9 buckets having 10 items and the rest having fewer.

  Counting with Restrictions

  Sometimes we impose restrictions that reduce the number of valid outcomes.

  Example: iPhone Passcodes

  Old iPhone passcodes were 4 digits. If fingerprints appear on 3 digits (one digit used twice), how many distinct passcodes?

  The passcode uses digits $\{a, b, c\}$ where one appears twice. We need to count sequences of length 4 using exactly these three digits.

  Method: Choose which digit appears twice (3 choices). Then arrange 4 items where 2 are identical: $\frac{4!}{2!} = 12$ arrangements.

  Total: $3 \times 12 = 36$.

  If fingerprints on only 2 digits: one digit used twice, another used twice. Choose which two digits (from the visible 2): must be those 2. Arrange: $\frac{4!}{2! \cdot 2!} = 6$ arrangements.

  The General Counting Principle

  For a sequence of choices where the $i$th choice has $n_i$ options:

  $\text{Total} = \prod_{i=1}^{r} n_i$

  This assumes choices are independent: the options at each step do not depend on previous choices.

  When choices depend on previous selections (sampling without replacement), each $n_i$ decreases.

  Example: Drawing Without Replacement

  Draw 3 cards from a standard 52-card deck without replacement.

  • First card: 52 choices
  • Second card: 51 choices
  • Third card: 50 choices
  • Total ordered draws: $52 \times 51 \times 50 = 132{,}600$

  Summary

  Concept	Formula
  Product rule	$n_1 \times n_2 \times \cdots \times n_r$
  Pigeonhole principle	$n$ items in $k$ boxes $\Rightarrow$ some box has $\geq \lceil n/k \rceil$
  Ordered sampling with replacement	$n^r$ sequences of length $r$ from $n$ items
  Ordered sampling without replacement	$n(n-1)\cdots(n-r+1) = \frac{n!}{(n-r)!}$

• Permutations and Combinations

  Factorial

  For a positive integer $n$, the factorial is:

  $n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$

  By convention, $0! = 1$.

  Factorials count the number of ways to arrange $n$ distinct objects in a sequence. The first position has $n$ choices, the second has $n-1$, and so on.

  Example: Arranging Books

  Six distinct books can be arranged on a shelf in $6! = 720$ ways.

  Permutations

  A permutation is an ordered arrangement of objects.

  Permutations of $n$ Objects Taken $r$ at a Time

  The number of ways to arrange $r$ objects selected from $n$ distinct objects:

  $P(n, r) = \frac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1)$

  Intuition: We have $n$ choices for the first position, $n-1$ for the second, down to $n-r+1$ for the $r$th position.

  Special case: $P(n, n) = n!$ arrangements of all $n$ objects.

  Example: Committee Officers

  From 10 people, select a president, vice-president, and treasurer. The order matters: select 3 and assign them to distinct roles.

  $P(10, 3) = 10 \times 9 \times 8 = 720$

  Combinations

  A combination is an unordered selection of objects.

  Combinations of $n$ Objects Taken $r$ at a Time

  The number of ways to select $r$ objects from $n$ distinct objects (order does not matter):

  $\binom{n}{r} = C(n, r) = \frac{n!}{r!(n-r)!}$

  Why divide by $r!$? Each unordered selection corresponds to $r!$ ordered arrangements. The permutations overcount by exactly this factor.

  Example: Selecting Books

  How many ways to select 3 books from a set of 6?

  $\binom{6}{3} = \frac{6!}{3! \cdot 3!} = \frac{720}{36} = 20$

  Compare with permutations: $P(6, 3) = 120$. Each unordered set appears as $3! = 6$ permutations.

  Example: Committee Members

  From 10 people, select 3 committee members (no roles assigned):

  $\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{720}{6} = 120$

  Key Properties of Binomial Coefficients

  Symmetry

  $\binom{n}{r} = \binom{n}{n-r}$

  Intuition: Selecting $r$ objects to include is equivalent to selecting $n-r$ objects to exclude.

  Pascal’s Identity

  $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

  Intuition: Any selection of $r$ from $n$ objects either includes a specific object (leaving $\binom{n-1}{r-1}$ ways) or excludes it (leaving $\binom{n-1}{r}$ ways).

  Sum

  $\sum_{r=0}^{n} \binom{n}{r} = 2^n$

  This counts all subsets of an $n$-element set. Each element can be either in or out: $n$ independent binary choices.

  Balls and Bins

  The techniques extend to distributing objects into containers.

  Distinct Balls into Distinct Bins

  $n$ distinct balls into $k$ distinct bins: $k^n$ ways. Each ball independently chooses a bin.

  Identical Balls into Distinct Bins

  $n$ identical balls into $k$ distinct bins, no restrictions: equivalent to placing $k-1$ dividers among $n+k-1$ positions.

  $\binom{n+k-1}{k-1} = \binom{n+k-1}{n}$

  Intuition: Imagine placing all $n$ balls in a row with $k-1$ dividers. The balls before the first divider go to bin 1, between first and second dividers to bin 2, and so on.

  Example: Server Distribution

  13 servers into 3 datacentres with capacities 6, 4, and 3. This counts arrangements where we partition the 13 labelled servers into groups of those sizes:

  $\binom{13}{6} \binom{7}{4} \binom{3}{3} = 1716 \times 35 \times 1 = 60{,}060$

  Alternatively: $\frac{13!}{6! \cdot 4! \cdot 3!}$ (multinomial coefficient).

  Permutations with Repetition

  When some objects are identical, the number of distinct arrangements is:

  $\frac{n!}{n_1! \cdot n_2! \cdots n_k!}$

  where $n_i$ is the number of objects of type $i$.

  Example: DNA Sequences

  How many distinct sequences can be formed from 3 A’s, 2 C’s, 1 G, and 1 T?

  $\frac{7!}{3! \cdot 2! \cdot 1! \cdot 1!} = \frac{5040}{12} = 420$

  Example: Bit Strings

  Distinct bit strings from three 0’s and two 1’s:

  $\frac{5!}{3! \cdot 2!} = \frac{120}{12} = 10$

  These are: 00111, 01011, 01101, 01110, 10011, 10101, 10110, 11001, 11010, 11100.

  Hypergeometric Formula

  When sampling without replacement, we use hypergeometric counts.

  Select $n$ items from a population of $N$ containing $m$ “special” items. The number of ways to get exactly $i$ special items:

  $\binom{m}{i} \binom{N-m}{n-i}$

  Choose $i$ special items from the $m$ available, and $n-i$ ordinary items from the $N-m$ non-special.

  Summary Table

  Problem	Formula
  Arrange all $n$ objects	$n!$
  Arrange $r$ from $n$	$P(n,r) = \frac{n!}{(n-r)!}$
  Choose $r$ from $n$	$\binom{n}{r} = \frac{n!}{r!(n-r)!}$
  Arrange with repetitions	$\frac{n!}{n_1! \cdots n_k!}$
  $n$ identical into $k$ bins	$\binom{n+k-1}{n}$

• Probability Axioms

  The Need for Axioms

  Intuitively, probability measures “how likely” an event is. But intuition can mislead. The axioms provide a rigorous foundation, ensuring all probability calculations are consistent.

  Kolmogorov’s Axioms

  Let $\Omega$ be a sample space and $\mathcal{F}$ an event space. A probability measure $P: \mathcal{F} \to [0,1]$ satisfies:

  Axiom 1: Non-negativity

  $P(E) \geq 0 \text{ for all events } E$

  Probabilities are never negative.

  Axiom 2: Normalisation

  $P(\Omega) = 1$

  The certain event has probability 1. It always occurs.

  Axiom 3: Additivity

  For mutually exclusive events $E_1, E_2, \ldots$:

  $P\left(\bigcup_{i=1}^{\infty} E_i\right) = \sum_{i=1}^{\infty} P(E_i)$

  The probability of the union of disjoint events equals the sum of their probabilities.

  For finite collections of mutually exclusive events:

  $P(E_1 \cup E_2 \cup \cdots \cup E_n) = P(E_1) + P(E_2) + \cdots + P(E_n)$

  when all $E_i \cap E_j = \emptyset$ for $i \neq j$.

  Consequences of the Axioms

  Probability of the Empty Set

  $P(\emptyset) = 0$

  Proof: $\Omega$ and $\emptyset$ are mutually exclusive with $\Omega \cup \emptyset = \Omega$. By Axiom 3: $P(\Omega) = P(\Omega) + P(\emptyset)$, so $P(\emptyset) = 0$.

  Probability of Complement

  $P(E^c) = 1 - P(E)$

  Proof: $E$ and $E^c$ partition $\Omega$: $E \cup E^c = \Omega$ and $E \cap E^c = \emptyset$. By additivity: $P(\Omega) = P(E) + P(E^c) = 1$, hence $P(E^c) = 1 - P(E)$.

  Probability Bounds

  $0 \leq P(E) \leq 1$

  The lower bound is Axiom 1. The upper bound follows from $P(E) = 1 - P(E^c)$ and $P(E^c) \geq 0$.

  Monotonicity

  If $E \subseteq F$, then $P(E) \leq P(F)$.

  Proof: Write $F = E \cup (F \setminus E)$ where these are disjoint. Then $P(F) = P(E) + P(F \setminus E) \geq P(E)$.

  Inclusion-Exclusion for Two Events

  $P(E \cup F) = P(E) + P(F) - P(E \cap F)$

  Why subtract $P(E \cap F)$? The sum $P(E) + P(F)$ counts outcomes in $E \cap F$ twice. We correct by subtracting once.

  

  Inclusion-Exclusion for Three Events

  $P(E \cup F \cup G) = P(E) + P(F) + P(G) - P(E \cap F) - P(E \cap G) - P(F \cap G) + P(E \cap F \cap G)$

  The pattern: add singletons, subtract pairwise intersections, add triple intersections.

  General Inclusion-Exclusion

  For $n$ events $E_1, E_2, \ldots, E_n$:

  $P\left(\bigcup_{i=1}^{n} E_i\right) = \sum_{i} P(E_i) - \sum_{i<j} P(E_i \cap E_j) + \sum_{i<j<k} P(E_i \cap E_j \cap E_k) - \cdots$

  Alternating signs: add, subtract, add, subtract, and so on.

  Example: Card Drawing

  Draw a card from a standard deck. Let:

  • $E$ = card is a heart
  • $F$ = card is an ace

  $P(E \cup F) = P(E) + P(F) - P(E \cap F) = \frac{13}{52} + \frac{4}{52} - \frac{1}{52} = \frac{16}{52} = \frac{4}{13}$

  Countable vs Uncountable

  The axioms extend to countable unions, but not uncountable ones. For uncountable sample spaces (like $\mathbb{R}$), we cannot assign positive probability to every singleton while maintaining total probability 1.

  This motivates using probability density functions for continuous random variables rather than assigning probability to individual points.

  Constructing Probability Measures

  For finite sample spaces with equally likely outcomes:

  $P(E) = \frac{|E|}{|\Omega|} = \frac{\text{number of outcomes in } E}{\text{total number of outcomes}}$

  This construction satisfies all axioms.

  Example (fair die): $\Omega = \{1,2,3,4,5,6\}$ with each outcome having probability $1/6$. Event “even” has probability $|\{2,4,6\}|/6 = 3/6 = 1/2$.

  Summary

  Property	Formula
  Certain event	$P(\Omega) = 1$
  Impossible event	$P(\emptyset) = 0$
  Complement	$P(E^c) = 1 - P(E)$
  Union (2 events)	$P(E \cup F) = P(E) + P(F) - P(E \cap F)$
  Monotonicity	$E \subseteq F \Rightarrow P(E) \leq P(F)$
  Bounds	$0 \leq P(E) \leq 1$

• Set Operations and Probability

  Events as Sets

  Events are subsets of the sample space. Set operations translate naturally into probability operations.

  Union

  The union $E \cup F$ is the event that $E$ or $F$ (or both) occurs.

  $P(E \cup F) = P(E) + P(F) - P(E \cap F)$

  The inclusion-exclusion formula corrects for double-counting outcomes in both events.

  Multiple Unions

  For $n$ events:

  $P\left(\bigcup_{i=1}^{n} E_i\right) \leq \sum_{i=1}^{n} P(E_i)$

  This upper bound is the union bound (Boole’s inequality): the probability of at least one occurring is at most the sum of individual probabilities.

  Intersection

  The intersection $E \cap F$ (or $EF$) is the event that both $E$ and $F$ occur.

  For mutually exclusive events: $P(E \cap F) = 0$.

  Complement

  The complement $E^c$ is the event that $E$ does not occur.

  $P(E^c) = 1 - P(E)$

  This is useful when computing the probability of “at least one” by considering “none”:

  $P(\text{at least one}) = 1 - P(\text{none})$

  Example: Matching Problem

  Three letters are randomly placed into three addressed envelopes. What is the probability at least one letter is in the correct envelope?

  Direct approach: Inclusion-exclusion over three events.

  Complement approach: Compute $P(\text{none correct}) = P(\text{derangement})$. There are 2 derangements out of $3! = 6$ permutations. So $P(\text{none}) = 2/6 = 1/3$.

  $P(\text{at least one}) = 1 - \frac{1}{3} = \frac{2}{3}$

  Difference

  The set difference $E - F = E \setminus F$ is the event that $E$ occurs but $F$ does not.

  $P(E - F) = P(E) - P(E \cap F)$

  Proof: $E = (E - F) \cup (E \cap F)$ where these are disjoint. By additivity: $P(E) = P(E - F) + P(E \cap F)$, so $P(E - F) = P(E) - P(E \cap F)$.

  Symmetric Difference

  The symmetric difference $E \triangle F = (E - F) \cup (F - E)$ is the event that exactly one of $E$, $F$ occurs.

  $P(E \triangle F) = P(E) + P(F) - 2P(E \cap F)$

  De Morgan’s Laws

  First Law

  $(E \cup F)^c = E^c \cap F^c$

  Probability interpretation: The event that neither $E$ nor $F$ occurs is the event that $E$ does not occur AND $F$ does not occur.

  Second Law

  $(E \cap F)^c = E^c \cup F^c$

  Probability interpretation: The event that not both $E$ and $F$ occur is the event that $E$ does not occur OR $F$ does not occur.

  Example

  Roll a die. Let $E$ = “roll even” $\{2,4,6\}$ and $F$ = “roll at least 5” $\{5,6\}$.

  • $E \cup F = \{2,4,5,6\}$, so $(E \cup F)^c = \{1,3\}$
  • $E^c = \{1,3,5\}$, $F^c = \{1,2,3,4\}$
  • $E^c \cap F^c = \{1,3\}$ (matches first law)

  Distributive Laws

  $E \cap (F \cup G) = (E \cap F) \cup (E \cap G)$ $E \cup (F \cap G) = (E \cup F) \cap (E \cup G)$

  These allow us to expand or simplify probability expressions.

  Associative and Commutative Laws

  Union and intersection are associative and commutative:

  $E \cup F = F \cup E, \quad E \cap F = F \cap E$ $E \cup (F \cup G) = (E \cup F) \cup G, \quad E \cap (F \cap G) = (E \cap F) \cap G$

  This means we can rearrange events in unions and intersections without changing the result.

  Summary Table

  Operation	Set Notation	Probability Formula
  Union	$E \cup F$	$P(E) + P(F) - P(E \cap F)$
  Intersection	$E \cap F$	$P(E \cap F)$
  Complement	$E^c$	$1 - P(E)$
  Difference	$E - F$	$P(E) - P(E \cap F)$
  De Morgan 1	$(E \cup F)^c$	$E^c \cap F^c$
  De Morgan 2	$(E \cap F)^c$	$E^c \cup F^c$

• Inclusion-Exclusion Principle

  The Problem with Unions

  When computing $P(E \cup F)$, we cannot simply add $P(E) + P(F)$ because outcomes in $E \cap F$ get counted twice.

  Two-Event Inclusion-Exclusion

  $P(E \cup F) = P(E) + P(F) - P(E \cap F)$

  Intuition: Add probabilities of each event, then subtract the intersection to correct for double-counting.

  Example: Cards

  Draw a card. Let $E$ = “heart” and $F$ = “ace”.

  $P(E \cup F) = \frac{13}{52} + \frac{4}{52} - \frac{1}{52} = \frac{16}{52} = \frac{4}{13}$

  Verify directly: 13 hearts + 3 other aces = 16 cards out of 52.

  Three-Event Inclusion-Exclusion

  $P(E \cup F \cup G) = P(E) + P(F) + P(G) - P(E \cap F) - P(E \cap G) - P(F \cap G) + P(E \cap F \cap G)$

  Pattern: Add singletons, subtract pairs, add triples. The signs alternate.

  

  Why Add the Triple?

  Each element in $E \cap F \cap G$:

  • Counted 3 times in singletons (+3)
  • Counted 3 times in pairs (−3)
  • Not yet counted in triples (+0)

  We need +1 total, so add $P(E \cap F \cap G)$.

  General Formula

  For $n$ events $E_1, E_2, \ldots, E_n$:

  $P\left(\bigcup_{i=1}^{n} E_i\right) = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} P(E_{i_1} \cap E_{i_2} \cap \cdots \cap E_{i_k})$

  In words: sum probabilities of $k$-fold intersections with sign $(-1)^{k+1}$.

  Example: Hat Check Problem

  $n$ people throw their hats into a pile. Each picks a hat randomly. What is the probability at least one person gets their own hat?

  Let $E_i$ = person $i$ gets their own hat.

  $P\left(\bigcup_{i=1}^{n} E_i\right) = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} \frac{(n-k)!}{n!}$

  • $P(E_i) = \frac{1}{n}$ for each of $\binom{n}{1}$ choices
  • $P(E_i \cap E_j) = \frac{(n-2)!}{n!}$ for $\binom{n}{2}$ pairs
  • Generally: $P$($k$ specific people get their hats) $= \frac{(n-k)!}{n!}$

  This gives:

  $P(\text{at least one match}) = \sum_{k=1}^{n} (-1)^{k+1} \frac{1}{k!}$

  As $n \to \infty$, this approaches $1 - e^{-1} \approx 0.632$.

  The Complement View

  For complex unions, computing $P(\text{none})$ via complement is often easier.

  $P\left(\bigcup_{i=1}^{n} E_i\right) = 1 - P\left(\bigcap_{i=1}^{n} E_i^c\right)$

  When events are independent: $P(\text{all fail}) = \prod P(E_i^c)$, giving:

  $P(\text{at least one}) = 1 - \prod_{i=1}^{n}(1 - P(E_i))$

  Example: Reliability

  A system has 3 components, each failing independently with probability 0.1. What is the probability the system fails (at least one component fails)?

  $P(\text{system fails}) = 1 - P(\text{all work}) = 1 - 0.9^3 = 1 - 0.729 = 0.271$

  Inclusion-Exclusion for Counting

  The principle applies to counting, not just probability:

  $|\bigcup_{i=1}^{n} A_i| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \leq i_1 < \cdots < i_k \leq n} |A_{i_1} \cap \cdots \cap A_{i_k}|$

  Example: Integer Properties

  How many integers from 1 to 1000 are divisible by 2 or 3?

  Let $A$ = multiples of 2, $B$ = multiples of 3.

  • $|A| = \lfloor 1000/2 \rfloor = 500$
  • $|B| = \lfloor 1000/3 \rfloor = 333$
  • $|A \cap B|$ = multiples of 6: $\lfloor 1000/6 \rfloor = 166$

  $|A \cup B| = 500 + 333 - 166 = 667$

  Bonferroni Inequalities

  The partial sums in inclusion-exclusion alternate between over- and under-estimates:

  $P(E_1 \cup \cdots \cup E_n) \leq \sum_{i} P(E_i)$ $P(E_1 \cup \cdots \cup E_n) \geq \sum_{i} P(E_i) - \sum_{i<j} P(E_i \cap E_j)$

  These provide upper and lower bounds when exact computation is impractical.

  Summary

  Events	Formula
  2 events	$P(E) + P(F) - P(E \cap F)$
  3 events	$P(E)+P(F)+P(G) - P(E \cap F) - P(E \cap G) - P(F \cap G) + P(E \cap F \cap G)$
  $n$ events	$\sum_{k=1}^{n} (-1)^{k+1} \sum_{i_1 < \cdots < i_k} P(E_{i_1} \cap \cdots \cap E_{i_k})$
  Complement	$1 - P(\bigcap E_i^c)$

• The Union Bound

  Statement

  Boole’s inequality (Union Bound): For any events $E_1, E_2, \ldots, E_n$:

  $P\left(\bigcup_{i=1}^{n} E_i\right) \leq \sum_{i=1}^{n} P(E_i)$

  The probability of at least one event occurring is at most the sum of their individual probabilities.

  For infinitely many events:

  $P\left(\bigcup_{i=1}^{\infty} E_i\right) \leq \sum_{i=1}^{\infty} P(E_i)$

  Proof

  By inclusion-exclusion:

  $P(E_1 \cup E_2) = P(E_1) + P(E_2) - P(E_1 \cap E_2) \leq P(E_1) + P(E_2)$

  since $P(E_1 \cap E_2) \geq 0$.

  By induction: assume true for $n-1$ events. Then:

  $P\left(\bigcup_{i=1}^{n} E_i\right) = P\left(\bigcup_{i=1}^{n-1} E_i\right) + P(E_n) - P\left(\bigcup_{i=1}^{n-1} E_i \cap E_n\right) \leq \sum_{i=1}^{n-1} P(E_i) + P(E_n) = \sum_{i=1}^{n} P(E_i)$

  When is Equality Achieved?

  Equality holds when all $E_i$ are mutually exclusive: when $E_i \cap E_j = \emptyset$ for all $i \neq j$, the intersection terms vanish and the bound becomes exact.

  Why the Union Bound Matters

  The union bound provides a simple upper bound when:

  1. Exact probabilities are hard to compute
  2. We need to prove something is “small enough”
  3. Events may be dependent (union bound doesn’t require independence)

  It is often used in algorithm analysis and error bounds.

  Example: Hash Collisions

  A hash table has $m$ buckets. We insert $n$ keys. Let $E_i$ be the event that key $i$ collides with some earlier key.

  The probability of at least one collision satisfies:

  $P(\text{some collision}) \leq \sum_{i=1}^{n} P(E_i)$

  If each key lands uniformly: $P(E_i) \leq \frac{i-1}{m}$. Then:

  $P(\text{some collision}) \leq \sum_{i=1}^{n} \frac{i-1}{m} = \frac{n(n-1)}{2m}$

  This is the birthday problem bound.

  Example: Error Bounds

  A system makes $n$ independent trials, each with error probability $\epsilon$. Let $E_i$ = “error on trial $i$”.

  $P(\text{at least one error}) \leq n \epsilon$

  If $\epsilon = \frac{1}{n^2}$, then $P(\text{error}) \leq \frac{1}{n}$.

  This is useful in probabilistic analysis: if each step has small error, the total error is bounded.

  Frechet Inequalities

  Related bounds for intersections:

  $\max\{0, \sum_i P(E_i) - (n-1)\} \leq P\left(\bigcap_{i=1}^{n} E_i\right) \leq \min_i P(E_i)$

  The upper bound follows from monotonicity: $\bigcap E_i \subseteq E_j$ for each $j$, so $P(\bigcap E_i) \leq P(E_j)$.

  Bonferroni Correction

  The union bound motivates multiple testing corrections. If we run $n$ hypothesis tests, each at significance level $\alpha$, the probability of at least one false positive is at most $n\alpha$.

  To ensure overall error rate $\alpha$, use threshold $\alpha/n$ for each test.

  Comparing with Exact Calculation

  Scenario	Exact	Union Bound
  Mutually exclusive	$\sum P(E_i)$	$\sum P(E_i)$ (tight)
  Independent	$1 - \prod(1-P(E_i))$	$\sum P(E_i)$ (loose when $P(E_i)$ not tiny)
  General case	Inclusion-exclusion	$\sum P(E_i)$

  The union bound is loosest when probabilities are large and events overlap significantly.

  Summary

  • Union bound: $P(\bigcup E_i) \leq \sum P(E_i)$
  • Equality when: events are mutually exclusive
  • Useful for: simpler analysis, error bounds, algorithm correctness proofs
  • Limitation: can be very loose for large probabilities and dependent events

• Conditional Probability

  The Intuition

  New information changes probabilities. If we roll a die and learn the result is even, the probability of rolling 6 changes from $\frac{1}{6}$ to $\frac{1}{3}$.

  Conditional probability formalises this: given that some event occurred, what is the probability of another?

  Definition

  The conditional probability of $E$ given $F$ (with $P(F) > 0$) is:

  $P(E \mid F) = \frac{P(E \cap F)}{P(F)}$

  Interpretation: We restrict our attention to outcomes where $F$ occurs. The probability of $E$ is then the relative proportion of these outcomes that also lie in $E$.

  

  Equivalent Forms

  Rearranging:

  $P(E \cap F) = P(E \mid F) \cdot P(F)$

  This is useful for computing joint probabilities: decompose into conditional times marginal.

  Similarly:

  $P(E \cap F) = P(F \mid E) \cdot P(E)$

  Properties

  Conditional probability satisfies all probability axioms:

  • $P(E \mid F) \geq 0$ for all $E$
  • $P(\Omega \mid F) = 1$
  • $P(\bigcup_{i} E_i \mid F) = \sum_{i} P(E_i \mid F)$ for disjoint $E_i$

  Conditional on $F$, we have a valid probability measure on the restricted sample space $F$.

  Examples

  Example 1: Dice

  Roll two dice. Given that the sum is 7, what is the probability the first die shows 4?

  Let $E$ = “first die is 4”, $F$ = “sum is 7”. The outcomes in $F$ are: $\{(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)\}$.

  Out of these 6 equally likely outcomes, only $(4,3)$ has first die 4.

  $P(E \mid F) = \frac{1}{6}$

  Compare: $P(E) = \frac{1}{6}$ (unconditionally). In this case, knowing the sum is 7 doesn’t change the probability.

  Example 2: Cards

  Draw two cards without replacement from a standard deck. Given the first card is a heart, what is the probability the second card is a heart?

  Let $E$ = “second card is a heart”, $F$ = “first card is a heart”.

  After drawing a heart first, 12 hearts remain out of 51 cards.

  $P(E \mid F) = \frac{12}{51} = \frac{4}{17}$

  Compare: $P(E) = \frac{1}{2}$ (unconditionally, by symmetry).

  Example 3: Medical Tests

  A test for a disease has 99% sensitivity (true positive rate) and 95% specificity (true negative rate). Disease prevalence is 1%. What is the probability of having the disease given a positive test?

  Let $D$ = “has disease”, $T$ = “tests positive”.

  We want $P(D \mid T)$.

  $P(D \mid T) = \frac{P(T \mid D) \cdot P(D)}{P(T)}$

  where $P(T) = P(T \mid D) P(D) + P(T \mid D^c) P(D^c) = 0.99 \times 0.01 + 0.05 \times 0.99 = 0.0099 + 0.0495 = 0.0594$

  $P(D \mid T) = \frac{0.99 \times 0.01}{0.0594} \approx \frac{0.0099}{0.0594} \approx 16.7\%$

  Despite a positive test, there’s only a 16.7% chance of having the disease, due to low prevalence.

  The Chain Rule

  For multiple events:

  $P(E_1 \cap E_2 \cap \cdots \cap E_n) = P(E_1) \cdot P(E_2 \mid E_1) \cdot P(E_3 \mid E_1 \cap E_2) \cdots P(E_n \mid E_1 \cap \cdots \cap E_{n-1})$

  This decomposes complex joint probabilities into simpler conditional probabilities.

  Example: Drawing Without Replacement

  Draw 3 cards from 52 without replacement. Probability all are spades:

  $P(\text{all spades}) = \frac{13}{52} \cdot \frac{12}{51} \cdot \frac{11}{50} = \frac{13 \cdot 12 \cdot 11}{52 \cdot 51 \cdot 50}$

  Common Misconceptions

  Confusion with Inverse

  $P(E \mid F) \neq P(F \mid E)$ in general.

  In the medical test example:

  • $P(T \mid D) = 0.99$ (sensitivity)
  • $P(D \mid T) \approx 0.167$ (much smaller)

  The Prosecutor’s Fallacy

  Confusing $P(\text{evidence} \mid \text{innocent})$ with $P(\text{innocent} \mid \text{evidence})$. A small false positive rate doesn’t guarantee a small probability of innocence.

  Conditioning as Restriction

  Conditional probability can be understood as:

  1. Restrict the sample space to $F$
  2. Renormalise probabilities so they sum to 1

  For equally likely outcomes:

  $P(E \mid F) = \frac{|E \cap F|}{|F|}$

  Count outcomes in $E \cap F$, divide by outcomes in $F$.

  Summary

  Concept	Formula
  Definition	$P(E \mid F) = \frac{P(E \cap F)}{P(F)}$
  Product rule	$P(E \cap F) = P(E \mid F) P(F)$
  Chain rule	$P(E_1 \cap \cdots \cap E_n) = \prod_{i=1}^{n} P(E_i \mid E_1 \cap \cdots \cap E_{i-1})$

• The Law of Total Probability and Bayes' Theorem

  Law of Total Probability

  Statement

  Let $F_1, F_2, \ldots, F_n$ be a partition of $\Omega$: mutually exclusive events that cover all possibilities. For any event $E$:

  $P(E) = \sum_{i=1}^{n} P(E \mid F_i) \cdot P(F_i)$

  Intuition

  To find the probability of $E$, condition on which scenario $F_i$ occurs and sum over all scenarios, weighting by the probability of each scenario.

  

  Proof

  $E = E \cap \Omega = E \cap \bigcup_{i=1}^{n} F_i = \bigcup_{i=1}^{n} (E \cap F_i)$

  Since $F_i$ are disjoint, $E \cap F_i$ are also disjoint. By additivity:

  $P(E) = \sum_{i=1}^{n} P(E \cap F_i) = \sum_{i=1}^{n} P(E \mid F_i) P(F_i)$

  Example: Two Dice

  Roll two dice. Let $E$ = “sum is even”. Partition by first die being odd ($F_1$) or even ($F_2$).

  • $P(F_1) = P(F_2) = \frac{1}{2}$
  • $P(E \mid F_1)$ = first die odd, sum even $\Rightarrow$ second die odd: $\frac{1}{2}$
  • $P(E \mid F_2)$ = first die even, sum even $\Rightarrow$ second die even: $\frac{1}{2}$

  $P(E) = P(E \mid F_1) P(F_1) + P(E \mid F_2) P(F_2) = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{2}$

  Bayes’ Theorem

  Statement

  $P(F \mid E) = \frac{P(E \mid F) \cdot P(F)}{P(E)}$

  Or, using the law of total probability for $P(E)$:

  $P(F \mid E) = \frac{P(E \mid F) \cdot P(F)}{\sum_i P(E \mid F_i) \cdot P(F_i)}$

  Terminology

  • Prior $P(F)$: probability before observing evidence $E$
  • Posterior $P(F \mid E)$: updated probability after observing evidence $E$
  • Likelihood $P(E \mid F)$: how likely is the evidence under hypothesis $F$
  • Marginal likelihood $P(E)$: normalising constant

  

  Proof

  By definition of conditional probability:

  $P(F \mid E) = \frac{P(F \cap E)}{P(E)} = \frac{P(E \cap F)}{P(E)} = \frac{P(E \mid F) \cdot P(F)}{P(E)}$

  Example: Medical Diagnosis

  A disease affects 1% of the population. A test has:

  • 99% sensitivity: $P(\text{positive} \mid \text{disease}) = 0.99$
  • 95% specificity: $P(\text{negative} \mid \text{no disease}) = 0.95$

  What is $P(\text{disease} \mid \text{positive})$?

  Let $D$ = disease, $T$ = positive test.

  $P(D \mid T) = \frac{P(T \mid D) P(D)}{P(T \mid D) P(D) + P(T \mid D^c) P(D^c)} = \frac{0.99 \times 0.01}{0.99 \times 0.01 + 0.05 \times 0.99} = \frac{0.0099}{0.0594} \approx 16.7\%$

  Interpretation: Even with a positive test, there’s only a 17% chance of having the disease (for rare diseases, most positives are false positives).

  Example: Monty Hall Problem

  You’re on a game show with 3 doors. One hides a prize. You pick door 1. The host opens door 2, revealing no prize. Should you switch to door 3?

  Let $F_i$ = prize behind door $i$. Initially $P(F_1) = P(F_2) = P(F_3) = \frac{1}{3}$.

  Let $E$ = host opens door 2.

  Compute $P(F_1 \mid E)$ and $P(F_3 \mid E)$:

  • If $F_1$ (prize behind door 1), host randomly opens door 2 or 3: $P(E \mid F_1) = \frac{1}{2}$
  • If $F_2$ (prize behind door 2), host cannot open door 2: $P(E \mid F_2) = 0$
  • If $F_3$ (prize behind door 3), host must open door 2: $P(E \mid F_3) = 1$

  $P(F_1 \mid E) = \frac{\frac{1}{2} \times \frac{1}{3}}{\frac{1}{2} \times \frac{1}{3} + 0 + 1 \times \frac{1}{3}} = \frac{\frac{1}{6}}{\frac{1}{6} + \frac{1}{3}} = \frac{1}{3}$

  $P(F_3 \mid E) = \frac{1 \times \frac{1}{3}}{\frac{1}{2}} = \frac{2}{3}$

  Conclusion: Switch to door 3 for a $\frac{2}{3}$ chance of winning.

  Example: Quality Control

  Two factories produce light bulbs. Factory A supplies 60% of the market with 2% defect rate. Factory B supplies 40% with 5% defect rate. A bulb is defective. What is the probability it came from A?

  Let $A$ = from factory A, $B$ = from factory B, $D$ = defective.

  $P(A \mid D) = \frac{0.02 \times 0.60}{0.02 \times 0.60 + 0.05 \times 0.40} = \frac{0.012}{0.012 + 0.020} = \frac{0.012}{0.032} = \frac{3}{8}$

  Sequential Bayesian Updating

  As more evidence arrives, today’s posterior becomes tomorrow’s prior. This is the foundation of Bayesian inference.

  Example: Disease Testing Repeat

  If we get two independent positive tests:

  $P(D \mid T_1 \cap T_2) \propto P(T_1 \cap T_2 \mid D) P(D) = P(T_1 \mid D) P(T_2 \mid D) P(D)$

  Starting from prior $P(D) = 0.01$, after one positive test the posterior is $\approx 0.167$. This becomes the new prior for the second test.

  Summary

  Concept	Formula
  Total probability	$P(E) = \sum_i P(E \mid F_i) P(F_i)$
  Bayes’ theorem	$P(F \mid E) = \frac{P(E \mid F) P(F)}{P(E)}$
  Prior	$P(F)$ before evidence
  Posterior	$P(F \mid E)$ after evidence
  Likelihood	$P(E \mid F)$ how likely evidence under hypothesis

• Bayes' Theorem and Independence

  Bayes’ Theorem Review

  $P(F \mid E) = \frac{P(E \mid F) \cdot P(F)}{P(E)}$

  This lets us reverse the direction of conditioning: from $P(E \mid F)$ to $P(F \mid E)$.

  Computational Form

  With partition $F_1, \ldots, F_n$:

  $P(F_i \mid E) = \frac{P(E \mid F_i) \cdot P(F_i)}{\sum_{j=1}^{n} P(E \mid F_j) \cdot P(F_j)}$

  The denominator is the law of total probability applied to $P(E)$.

  Example: Spam Filtering

  An email contains the word “free”. Historical data shows:

  • $P(\text{"free"} \mid \text{spam}) = 0.3$
  • $P(\text{"free"} \mid \text{not spam}) = 0.05$
  • $P(\text{spam}) = 0.4$

  $P(\text{spam} \mid \text{"free"}) = \frac{0.3 \times 0.4}{0.3 \times 0.4 + 0.05 \times 0.6} = \frac{0.12}{0.12 + 0.03} = \frac{0.12}{0.15} = 0.8$

  An email with “free” has 80% probability of being spam.

  Independence of Events

  Definition

  Events $E$ and $F$ are independent if:

  $P(E \cap F) = P(E) \cdot P(F)$

  Equivalently (when $P(F) > 0$):

  $P(E \mid F) = P(E)$

  Knowing $F$ occurred gives no information about $E$.

  Intuition

  Two events are independent if the occurrence of one tells us nothing about the occurrence of the other. The probability of $E$ is the same whether or not we know $F$ occurred.

  Example: Coin Flips

  Flip a fair coin twice. Let $E$ = “first is heads”, $F$ = “second is heads”.

  $P(E \cap F) = P(HH) = \frac{1}{4} = \frac{1}{2} \times \frac{1}{2} = P(E) \cdot P(F)$

  The outcomes are independent.

  Example: Dependent Events

  Draw two cards without replacement. Let $E$ = “first is ace”, $F$ = “second is ace”.

  $P(E \cap F) = \frac{4}{52} \cdot \frac{3}{51} = \frac{12}{2652} \neq \frac{4}{52} \cdot \frac{4}{52}$

  Not independent: drawing an ace first changes the probability of drawing an ace second.

  Independent vs Mutually Exclusive

  Common confusion: Independence and mutual exclusivity are different concepts.

  Property	$E, F$ disjoint (ME)	$E, F$ independent
  Defining equation	$E \cap F = \emptyset$	$P(E \cap F) = P(E) P(F)$
  Probability	$P(E \cap F) = 0$	$P(E \cap F) = P(E) P(F) > 0$ typically
  Knowing $F$ occurred	$E$ cannot occur	Gives no info about $E$

  Key insight: If $E$ and $F$ are both possible (positive probability) and mutually exclusive, they are NOT independent. Knowing $F$ occurred tells us $E$ did NOT occur.

  Mutual Independence

  Pairwise Independence

  Events $E_1, E_2, \ldots, E_n$ are pairwise independent if $E_i$ and $E_j$ are independent for all $i \neq j$.

  This is weaker than mutual independence.

  Mutual Independence

  Events $E_1, E_2, \ldots, E_n$ are mutually independent if for every subset $S \subseteq \{1, 2, \ldots, n\}$:

  $P\left(\bigcap_{i \in S} E_i\right) = \prod_{i \in S} P(E_i)$

  Important: Pairwise independence does NOT imply mutual independence.

  Example: Pairwise but Not Mutual

  Flip two fair coins. Define:

  • $A$ = first coin is heads
  • $B$ = second coin is heads
  • $C$ = coins match (both heads or both tails)

  Check independence:

  • $P(A) = P(B) = P(C) = \frac{1}{2}$
  • $P(A \cap B) = \frac{1}{4} = P(A) P(B)$ (pairwise independent)
  • $P(A \cap C) = \frac{1}{4} = P(A) P(C)$ (pairwise independent)
  • $P(B \cap C) = \frac{1}{4} = P(B) P(C)$ (pairwise independent)

  But:

  • $P(A \cap B \cap C) = \frac{1}{4}$ (only HH)
  • $P(A) P(B) P(C) = \frac{1}{8}$

  These events are pairwise independent but NOT mutually independent.

  Conditional Independence

  Events $E$ and $F$ are conditionally independent given $G$ if:

  $P(E \cap F \mid G) = P(E \mid G) \cdot P(F \mid G)$

  Events can be independent unconditionally but dependent conditionally, or vice versa.

  Example: Berger’s Bullets

  Two shooters aim at a target. Let $A, B$ be “shooter A/B hits”. Unconditionally, $A$ and $B$ might be independent. But given the target is hit, knowing $A$ missed makes it more likely $B$ hit, creating dependence.

  Properties of Independence

  1. If $E$ and $F$ are independent, then so are $E$ and $F^c$.

     Proof: $P(E) = P(E \cap F) + P(E \cap F^c) = P(E) P(F) + P(E \cap F^c)$, so $P(E \cap F^c) = P(E) - P(E) P(F) = P(E)(1 - P(F)) = P(E) P(F^c)$.

  2. If $E$ and $F$ are independent, then $E^c$ and $F^c$ are independent.

  3. Independence is symmetric: $E$ independent of $F$ iff $F$ independent of $E$.

  Application: System Reliability

  Components in series all must work. If each has reliability $p$ and failures are independent:

  $P(\text{system works}) = p^n$

  Components in parallel: at least one must work:

  $P(\text{system works}) = 1 - (1-p)^n$

  Summary

  Concept	Definition
  Independence	$P(E \cap F) = P(E) P(F)$
  Equivalent form	$P(E \mid F) = P(E)$ (when $P(F) > 0$)
  Mutual independence	$P(\bigcap_{i \in S} E_i) = \prod_{i \in S} P(E_i)$ for all subsets $S$
  Conditional independence	$P(E \cap F \mid G) = P(E \mid G) P(F \mid G)$