# Lecture 13. Probabilities

## 13.1 Overview

Every branch of mathematics we have met so far describes a *deterministic* world: a
set either contains an element or it does not (Lectures 1–2), two elements are either
related or they are not (Lecture 3), a proposition is either true or false (Lecture 6).
Probability theory is the branch of discrete mathematics that extends this black-and-white
logic to a world of **graded certainty** — it attaches to each uncertain statement a number
between $0$ and $1$ measuring *how likely* it is to be true.

Why should a computer scientist care? Because the most powerful ideas in modern
computing are probabilistic:

- **Randomized algorithms** (quicksort with a random pivot, randomized primality testing,
  skip lists, hashing) trade a tiny chance of a bad outcome for dramatic speed. Analysing
  them means computing $P(\text{algorithm is slow})$ and showing it is negligible.
- **Hashing and load balancing** live or die by *collision probabilities* — the birthday
  problem of this lecture is exactly the analysis of a hash table.
- **Machine learning** is applied probability: a spam filter computes $P(\text{spam}\mid\text{words})$
  with Bayes' theorem; a classifier's *precision* and *recall* are conditional probabilities.
- **Cryptography** rests on the infeasibility of guessing a random key, and the "birthday
  attack" is a direct application of the birthday problem.
- **Networks, queues, and reliability** are modelled by the probability that a packet is
  lost, a server is busy, or a component fails.

This lecture builds *finite* (discrete) probability from the ground up in three stages.

1. **Language.** Random experiments, the sample space $\Omega$, and events — which turn out
   to be nothing more than the *sets* of Lecture 1, so the whole algebra of Lecture 2
   transfers verbatim.
2. **Measure.** How to attach a number $P(A)\in[0,1]$ to an event: the classical (Laplace)
   ratio, the counting tools (combinatorics) needed to evaluate it, and the three axioms
   of Kolmogorov that pin down what "probability" *is*.
3. **A calculus of events.** Theorems that combine probabilities — the complement rule,
   the addition rule (a probabilistic inclusion–exclusion), conditional probability, the
   multiplication rule, independence, the law of total probability, and Bayes' theorem —
   each stated precisely and **proved** from the axioms.

We close with three celebrated problems every student should meet once — the **birthday
problem**, the **Monty Hall problem**, and a **Bayesian medical-test** calculation — and a
first look at **random variables** and **expectation**.

Throughout we stay in the **discrete, finite** world: the sample space has finitely many
outcomes. Continuous distributions (the normal curve, densities, integrals) are the subject
of a later course and are out of scope here.

## 13.2 Random experiments, sample space, and events

A **random experiment (trial)** is a process whose individual outcome cannot be predicted
with certainty in advance, even though the *set* of possible outcomes is known and the
experiment can (in principle) be repeated under identical conditions. Tossing a coin,
rolling a die, drawing a card, and picking a ball from an urn are the classic examples; so
is "hash a random key into a table of size $m$" or "run randomized quicksort on this array."

The **sample space** $\Omega$ (also written $S$ or $U$) is the set of **all** possible
outcomes of the experiment. Each individual outcome $\omega\in\Omega$ is an **elementary
event (sample point)** — an outcome that cannot be decomposed further.

An **event** is any statement about the experiment that becomes definitely true or false
once the outcome is known — formally, a **subset** $A\subseteq\Omega$. The event *occurs*
exactly when the realized outcome $\omega$ belongs to $A$. An event containing more than one
elementary outcome is a **compound event**.

**Example (die).** Roll one fair six-sided die, so $\Omega=\{1,2,3,4,5,6\}$ and
$|\Omega|=6$. The elementary event "roll a $4$" is the singleton $\{4\}$. The compound event
$A=$ "even number" is $\{2,4,6\}$; $B=$ "greater than $4$" is $\{5,6\}$. Then
$A\cup B=\{2,4,5,6\}$, $A\cap B=\{6\}$, and $\overline{A}=\{1,3,5\}$.

**Example (two coins).** Toss two distinguishable coins:
$\Omega=\{HH,HT,TH,TT\}$, $|\Omega|=4$. The event "exactly one head" is
$\{HT,TH\}$. Note that this $\Omega$ is the Cartesian product $\{H,T\}\times\{H,T\}$ from
Lecture 2 — building compound sample spaces out of simple ones is exactly the product
construction.

![Probability tree for tossing two coins, enumerating the sample space Ω = {HH, HT, TH, TT} with |Ω| = 4](img/l13_sample_space.png)

### Events are sets: the algebra of events

Because an event *is* a subset of $\Omega$, the set operations of Lectures 1–2 carry over
with no change — only the *reading* changes. This dictionary is the single most useful table
in the lecture; keep it in view.

| Set notation | Event language | "occurs when…" |
|---|---|---|
| $\omega\in A$ | outcome $\omega$ makes $A$ occur | the realized outcome lies in $A$ |
| $\Omega$ | **certain event** | always |
| $\varnothing$ | **impossible event** | never |
| $A\cup B$ | "$A$ **or** $B$" (at least one) | $\omega\in A$ or $\omega\in B$ |
| $A\cap B$ (also $AB$) | "$A$ **and** $B$" (both) | $\omega\in A$ and $\omega\in B$ |
| $\overline{A}=\Omega\setminus A$ | "**not** $A$" | $\omega\notin A$ |
| $A\subseteq B$ | "$A$ **implies** $B$" | whenever $A$ occurs, so does $B$ |
| $A\cap B=\varnothing$ | $A,B$ **mutually exclusive** | they cannot co-occur |
| $A\setminus B=A\cap\overline B$ | "$A$ but not $B$" | $\omega\in A$ and $\omega\notin B$ |

Consequently De Morgan's laws from Lecture 2 read, in event language,

$$
\overline{A\cup B}=\overline A\cap\overline B\quad(\text{"not (}A\text{ or }B\text{)}"=\text{"neither"}),\qquad \overline{A\cap B}=\overline A\cup\overline B .
$$

**Remark (why "events as sets" matters).** This is not a coincidence to be admired and
forgotten. Every probability manipulation below is *first* a set manipulation and *then* an
application of an axiom. When a word problem confuses you, translate it into set operations
on $\Omega$ first; the arithmetic follows.

**Remark (the event space).** For a finite $\Omega$ we take *every* subset to be an event,
so the collection of events is the power set $2^{\Omega}$ (Lecture 1), with $|2^{\Omega}|=2^{|\Omega|}$
events in all. For infinite sample spaces one cannot always take every subset and must
restrict to a so-called $\sigma$-algebra; that subtlety never arises in the finite world of
this lecture.

## 13.3 Types of events

Classifying how events relate to one another decides *which* rule applies later, so the
vocabulary is worth stating precisely.

**Certain (reliable) event** — occurs in **every** trial. It is the whole sample space
$\Omega$ and (we will prove) has probability $1$. Example: "the die shows a number in
$\{1,\dots,6\}$."

**Impossible event** — **never** occurs. It is the empty set $\varnothing$ and has
probability $0$. Example: "the die shows $7$."

**Compatible (jointly possible) events** — **can** occur in the same trial:
$A\cap B\neq\varnothing$. On one die, $A=$ "even" and $B=$ "greater than $3$" share the
outcome $6$, so they are compatible.

**Incompatible (mutually exclusive) events** — **cannot** occur together:
$A\cap B=\varnothing$ (the disjoint sets of Lecture 2). "Roll a $2$" and "roll a $5$" cannot
both happen in one roll. Distinct elementary events are always pairwise incompatible.

A family of events $A_1,\dots,A_n$ forms a **complete group** (a **partition** of $\Omega$)
if they are pairwise incompatible and their union is $\Omega$ — so **exactly one** of them
occurs in every trial. This is precisely the partition concept of Lecture 3, where a
partition of a set arose as the family of equivalence classes of an equivalence relation.
There, blocks were "elements that are equivalent"; here, blocks are "outcomes that trigger
the same hypothesis." The idea returns as the backbone of the total-probability formula.

**Complementary (opposite) events** — the special case of a complete group of *two*:
$A$ and $\overline{A}$ are incompatible and together exhaust $\Omega$. Example: "the die
shows $6$" and "the die does not show $6$." We will prove $P(A)+P(\overline A)=1$.

**Independent events** — the occurrence of one does **not** change the probability of the
other (made precise below). Drawing a ball, replacing it, then drawing again gives
independent draws.

**Dependent events** — the occurrence of one **does** change the probability of the other.
Drawing two balls *without* replacement makes the second draw depend on the first.

> **Common pitfall.** Independence is *not* the same as incompatibility — in fact they are
> almost opposites. We will prove that two incompatible events of positive probability are
> necessarily *dependent*: if $A$ occurs then $B$ has become impossible, which is a maximal
> change in $B$'s probability. Do not equate "$A\cap B=\varnothing$" with "$A,B$ independent."

## 13.4 The classical (Laplace) definition of probability

When a finite experiment has $n$ **equally likely** elementary outcomes, of which exactly
$m$ are **favourable** to an event $A$, the **classical (Laplace) probability** of $A$ is

$$
P(A)=\frac{m}{n}=\frac{\lvert A\rvert}{\lvert\Omega\rvert}=\frac{\text{number of favourable outcomes}}{\text{number of possible outcomes}}.
$$

The "equally likely" hypothesis is essential and is justified by **symmetry**: a fair coin,
a fair die, a well-shuffled deck, and a thoroughly mixed urn have no physical reason to
prefer one outcome over another. Where symmetry fails, the classical definition does not
apply and we fall back on the statistical definition below.

**Example (die).** $P(\text{even})=\tfrac{3}{6}=\tfrac12$, since $3$ of the $6$ equally
likely faces are even.

**Example (cards).** From a standard $52$-card deck, $P(\text{ace})=\tfrac{4}{52}=\tfrac1{13}$
and $P(\text{face card})=\tfrac{12}{52}=\tfrac3{13}$ (the $12$ jacks, queens, kings).

Because $0\le m\le n$, the ratio always lies in $[0,1]$; $P(\Omega)=n/n=1$ and
$P(\varnothing)=0/n=0$. The whole of classical probability therefore reduces to a *counting*
problem — "how many favourable, how many total?" — which is why we develop combinatorics
next.

**Statistical (frequentist) probability.** When symmetry fails (a bent coin, an unknown
manufacturing process) we estimate probability empirically. If in $N$ independent trials the
event $A$ occurs $N_A$ times, its **relative frequency** is $W(A)=N_A/N$. The **law of large
numbers** says that as $N\to\infty$ this
frequency stabilizes around a fixed number, the **statistical probability** $P(A)$. For fair
mechanisms the statistical and classical values agree; the statistical view is what lets us
speak of "the probability of rain" or "the probability a hard drive fails within a year,"
where no symmetry is available.

## 13.5 Counting: combinatorics as the engine of classical probability

To use $P(A)=m/n$ we must count outcomes. Three counting devices — resting on one master
principle — handle almost every finite problem. Throughout, $n$ is the number of available
objects and $k$ the number chosen.

### The multiplication principle (rule of product)

**Multiplication principle.** If a procedure consists of $k$ successive steps, where step $1$
can be done in $n_1$ ways, step $2$ in $n_2$ ways *regardless of the first choice*, …, and
step $k$ in $n_k$ ways regardless of the earlier choices, then the whole procedure can be
carried out in

$$
n_1\cdot n_2\cdots n_k\quad\text{ways.}
$$

*Proof.* An outcome of the procedure is precisely a $k$-tuple $(x_1,\dots,x_k)$ with $x_i$
one of the $n_i$ choices at step $i$, so the set of outcomes is the Cartesian product
$X_1\times\cdots\times X_k$ of Lecture 2 with $|X_i|=n_i$. The cardinality of a finite
Cartesian product is the product of the cardinalities, $|X_1\times\cdots\times X_k|=\prod_i n_i$,
which one proves by induction on $k$: the case $k=1$ is immediate, and
$|X_1\times\cdots\times X_{k}|=|X_1\times\cdots\times X_{k-1}|\cdot|X_k|$ because each of the
$|X_1\times\cdots\times X_{k-1}|$ shorter tuples extends in exactly $n_k$ ways. ∎

**Example.** A password of $3$ lowercase letters followed by $2$ digits can be formed in
$26\cdot26\cdot26\cdot10\cdot10=26^3\cdot10^2=1{,}757{,}600$ ways. Rolling two dice yields
$6\cdot6=36$ ordered outcomes — the sample space $\{1,\dots,6\}\times\{1,\dots,6\}$.

### Permutations

**Permutation of $n$ objects** — an ordering (in a row) of all $n$ distinct objects. The
number of permutations is

$$
P_n=n!=1\cdot2\cdot3\cdots n,\qquad\text{with the convention }0!=1.
$$

*Proof.* Filling the $n$ positions left to right is a $k=n$-step procedure: the first
position admits $n$ choices, the second $n-1$ (one object is used up), …, the last $1$. By
the multiplication principle the count is $n(n-1)\cdots1=n!$. ∎

**$k$-permutation (arrangement)** — an ordered selection of $k$ out of $n$ distinct objects
(order matters, no repetition). Its count, written $P(n,k)$ (the notation used in Rosen; the
same quantity appears in the European tradition as $A_n^{k}$, the number of *arrangements*), is

$$
P(n,k)=A_n^{k}=\frac{n!}{(n-k)!}=\underbrace{n(n-1)\cdots(n-k+1)}_{k\text{ factors}}.
$$

*Proof.* Fill $k$ ordered positions from $n$ objects: $n$ choices for the first, $n-1$ for
the second, …, $n-k+1$ for the $k$-th. The product of these $k$ factors is
$n(n-1)\cdots(n-k+1)$, which equals $n!/(n-k)!$ after cancelling the tail
$(n-k)(n-k-1)\cdots1$. ∎

**Example.** Choosing a president and then a (distinct) secretary from $10$ people gives
$P(10,2)=10\cdot9=90$ ordered pairs. All orderings of $5$ books on a shelf: $P_5=5!=120$.

### Combinations

**Combination** — an unordered selection of $k$ out of $n$ distinct objects (order does
**not** matter, no repetition), i.e. a $k$-element *subset*. Its count is the **binomial
coefficient**

$$
\binom{n}{k}=C(n,k)=C_n^{k}=\frac{n!}{k!\,(n-k)!},\qquad 0\le k\le n.
$$

*Proof.* Count ordered $k$-selections two ways. On one hand there are $P(n,k)=n!/(n-k)!$ of
them. On the other hand, to build an ordered selection we may first choose the *set* of $k$
objects — say there are $\binom{n}{k}$ such sets — and then order them, which by the
permutation count can be done in $k!$ ways. By the multiplication principle
$P(n,k)=\binom{n}{k}\cdot k!$, so

$$
\binom{n}{k}=\frac{P(n,k)}{k!}=\frac{n!}{k!\,(n-k)!}.\qquad\blacksquare
$$

**Example.** A committee of $3$ from $10$ people:
$\binom{10}{3}=\dfrac{10!}{3!\,7!}=\dfrac{10\cdot9\cdot8}{3\cdot2\cdot1}=120$. (Contrast with
the *ordered* count $P(10,3)=720$; dividing by $3!=6$ removes the ordering.)

Two facts we will reuse:

- **Symmetry:** $\binom{n}{k}=\binom{n}{n-k}$, since choosing the $k$ objects to include is
  the same as choosing the $n-k$ objects to exclude.
- **Pascal's identity:** $\displaystyle\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$.

*Proof of Pascal's identity (combinatorial).* Fix one particular object $x$ among the $n$.
Every $k$-subset either contains $x$ or not. Those containing $x$ are formed by choosing the
remaining $k-1$ members from the other $n-1$ objects: $\binom{n-1}{k-1}$ of them. Those not
containing $x$ choose all $k$ members from the other $n-1$: $\binom{n-1}{k}$ of them. These
two cases are disjoint and exhaustive, so their counts add. ∎

> **Common pitfall (a notation clash).** The letter $P$ is overloaded: $P(A)$ is the
> *probability* of an event $A$, while $P(n,k)$ is the *number* of $k$-permutations. They are
> told apart only by what sits inside the parentheses (a set/event vs. two integers). To avoid
> confusion this lecture writes probabilities of named events, e.g. $P(A)$, and permutation
> counts with two integer arguments, e.g. $P(10,2)=90$. The European-tradition notation
> $A_n^k$, $C_n^k$ sidesteps the clash entirely.

> **Order matters?** The single question that selects the tool: *does rearranging the chosen
> objects give a different outcome?* Yes ⇒ permutation $P(n,k)$; No ⇒ combination
> $\binom{n}{k}$. "President and secretary" is ordered; "a committee" is not.

![Table contrasting permutations (order matters) with combinations (order does not); for n=5, k=2 they give 20 versus 10](img/l13_perm_comb.png)

**Example (urn, counting).** An urn holds $6$ white and $4$ black balls; draw $3$ at once
(order irrelevant). Total selections: $\binom{10}{3}=120$. Favourable to "exactly $2$ white
and $1$ black": choose the whites $\binom{6}{2}=15$ ways and the black $\binom{4}{1}=4$ ways,
giving $15\cdot4=60$. Hence

$$
P(\text{2 white, 1 black})=\frac{\binom{6}{2}\binom{4}{1}}{\binom{10}{3}}=\frac{60}{120}=\frac12 .
$$

(This is a **hypergeometric** count — sampling without replacement — and we return to it below.)

### Three more counting tools

- **Sum rule (addition principle).** If an object comes from one of **disjoint** cases with
  $m_1, m_2,\dots$ options, the total is $m_1+m_2+\cdots$. "**Or** / separate cases" adds,
  where the product rule's "**and** / in stages" multiplies.
- **Selections with repetition (multisets / stars-and-bars).** Choosing $k$ objects from
  $n$ **types** with repetition allowed — equivalently, distributing $k$ *identical* balls
  into $n$ distinct boxes — is counted by
  $$\overline{C}(n,k)=\binom{n+k-1}{k}$$
  (line up $k$ **stars** and $n-1$ **bars**). This fills the last cell of the
  order-vs-repetition taxonomy: unordered **with** repetition.
- **Binomial theorem.** The combinations are the coefficients of a binomial power:
  $$(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^k y^{n-k},$$
  whence $\sum_k\binom{n}{k}=2^n$ (put $x=y=1$) and the binomial-distribution weights
  $\binom{n}{k}p^k(1-p)^{n-k}$ sum to $1$ (put $x=p,\ y=1-p$).

## 13.6 Kolmogorov's axioms

The classical ratio $m/n$ works only for equally likely outcomes and only for finite
spaces. In 1933 A. N. Kolmogorov gave probability the abstract, symmetry-free foundation
still used today: probability is *any* function on events obeying three axioms.

**Definition (probability measure).** A **probability** on a finite sample space $\Omega$ is
a function $P$ assigning to every event $A\subseteq\Omega$ a real number $P(A)$ such that

1. **(Non-negativity)** $P(A)\ge0$ for every event $A$;
2. **(Normalization)** $P(\Omega)=1$;
3. **(Additivity)** if $A\cap B=\varnothing$ then $P(A\cup B)=P(A)+P(B)$; more generally, for
   pairwise incompatible events $A_1,A_2,\dots$ (finitely or countably many),

$$
P\!\Big(\bigcup_i A_i\Big)=\sum_i P(A_i).
$$

Everything else in this lecture is a *theorem* deduced from these three lines. Nothing about
"equally likely" is assumed; the classical model is just one instance.

**Building a finite probability space.** On a finite $\Omega=\{\omega_1,\dots,\omega_n\}$ it
suffices to assign each outcome a **weight** $p_i=P(\{\omega_i\})\ge0$ with
$\sum_{i=1}^n p_i=1$, and then define $P(A)=\sum_{\omega_i\in A}p_i$. Additivity then holds
automatically. The **classical (uniform) model** is the special case $p_i=1/n$ for all $i$.

**Theorem (the classical ratio is a probability).** For finite $\Omega$ with $|\Omega|=n$,
the function $P(A)=|A|/n$ satisfies the three axioms.

*Proof.* Non-negativity: $|A|\ge0$, so $P(A)\ge0$. Normalization: $P(\Omega)=|\Omega|/n=n/n=1$.
Additivity: if $A\cap B=\varnothing$ then $|A\cup B|=|A|+|B|$ — this is exactly the
disjoint-union counting rule of Lecture 2 — so
$P(A\cup B)=\dfrac{|A|+|B|}{n}=\dfrac{|A|}{n}+\dfrac{|B|}{n}=P(A)+P(B)$. ∎

## 13.7 Derived rules and their proofs

We now prove, purely from Axioms 1–3, the working rules of probability. These proofs are the
mathematical heart of the lecture; each is short, and together they show how much structure
three axioms already force.

**Theorem (finite additivity).** If $A_1,\dots,A_n$ are pairwise incompatible then
$P(A_1\cup\cdots\cup A_n)=\sum_{i=1}^n P(A_i)$.

*Proof.* Induction on $n$. The case $n=2$ is Axiom 3. Assume the claim for $n-1$ and let
$A_1,\dots,A_n$ be pairwise incompatible. Put $B=A_1\cup\cdots\cup A_{n-1}$. Then
$B\cap A_n=\big(\bigcup_{i<n}A_i\big)\cap A_n=\bigcup_{i<n}(A_i\cap A_n)=\bigcup_{i<n}\varnothing=\varnothing$,
so by Axiom 3 and the induction hypothesis

$$
P\Big(\bigcup_{i\le n}A_i\Big)=P(B\cup A_n)=P(B)+P(A_n)=\sum_{i<n}P(A_i)+P(A_n)=\sum_{i\le n}P(A_i).\qquad\blacksquare
$$

**Theorem (impossible event).** $P(\varnothing)=0$.

*Proof.* $\varnothing\cap\varnothing=\varnothing$ and $\varnothing\cup\varnothing=\varnothing$,
so $\varnothing$ is incompatible with itself. Axiom 3 gives
$P(\varnothing)=P(\varnothing\cup\varnothing)=P(\varnothing)+P(\varnothing)=2\,P(\varnothing)$.
Subtracting $P(\varnothing)$ from both sides yields $P(\varnothing)=0$. ∎

**Theorem (complement rule).** For every event $A$, $\;P(\overline A)=1-P(A)$.

*Proof.* $A$ and $\overline A$ are incompatible ($A\cap\overline A=\varnothing$) and
exhaust the space ($A\cup\overline A=\Omega$). By Axiom 3 and then Axiom 2,

$$
P(A)+P(\overline A)=P(A\cup\overline A)=P(\Omega)=1,
$$

so $P(\overline A)=1-P(A)$. ∎

This is the workhorse behind every "**at least one**" computation, because the complement
"**none**" is usually far easier to count.

**Theorem (range of probability).** For every event $A$, $\;0\le P(A)\le1$.

*Proof.* The lower bound is Axiom 1. For the upper bound, the complement rule gives
$P(A)=1-P(\overline A)$, and $P(\overline A)\ge0$ by Axiom 1, so $P(A)\le1$. ∎

**Theorem (monotonicity and difference).** If $A\subseteq B$ then
$P(B\setminus A)=P(B)-P(A)$ and hence $P(A)\le P(B)$.

*Proof.* Since $A\subseteq B$, the set $B$ splits as the disjoint union
$B=A\cup(B\setminus A)$ with $A\cap(B\setminus A)=\varnothing$. Axiom 3 gives
$P(B)=P(A)+P(B\setminus A)$, whence $P(B\setminus A)=P(B)-P(A)$. As $P(B\setminus A)\ge0$ by
Axiom 1, we get $P(A)\le P(B)$. ∎

**Theorem (addition rule / inclusion–exclusion for two events).** For *any* two events,

$$
P(A\cup B)=P(A)+P(B)-P(A\cap B).
$$

*Proof.* Write $A\cup B$ as the disjoint union $A\cup B=A\cup(B\setminus A)$, so by Axiom 3

$$
P(A\cup B)=P(A)+P(B\setminus A).\tag{1}
$$

Now $A\cap B\subseteq B$, and $B$ splits as the disjoint union
$B=(A\cap B)\cup(B\setminus A)$ (an outcome of $B$ is either also in $A$ or not), so by
Axiom 3

$$
P(B)=P(A\cap B)+P(B\setminus A)\ \Longrightarrow\ P(B\setminus A)=P(B)-P(A\cap B).\tag{2}
$$

Substituting (2) into (1) gives $P(A\cup B)=P(A)+P(B)-P(A\cap B)$. ∎

**Remark.** This is the probabilistic twin of the cardinality identity
$|A\cup B|=|A|+|B|-|A\cap B|$ proved in Lecture 2; dividing that by $|\Omega|$ in the
classical model recovers it. The overlap $A\cap B$ is *subtracted* because outcomes in it
are counted once in $P(A)$ and again in $P(B)$. For incompatible events $A\cap B=\varnothing$,
the term vanishes and we recover $P(A\cup B)=P(A)+P(B)$.

**Theorem (inclusion–exclusion for three events).**

$$
P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C).
$$

*Proof.* Apply the two-event rule to $(A\cup B)$ and $C$:

$$
P\big((A\cup B)\cup C\big)=P(A\cup B)+P(C)-P\big((A\cup B)\cap C\big).
$$

Expand $P(A\cup B)=P(A)+P(B)-P(A\cap B)$. For the last term, distributivity (Lecture 2)
gives $(A\cup B)\cap C=(A\cap C)\cup(B\cap C)$, so by the two-event rule again

$$
P\big((A\cup B)\cap C\big)=P(A\cap C)+P(B\cap C)-P\big((A\cap C)\cap(B\cap C)\big),
$$

and $(A\cap C)\cap(B\cap C)=A\cap B\cap C$. Combining the pieces gives the stated formula. ∎

**Theorem (Boole's inequality / union bound).** For any events $A_1,\dots,A_n$,

$$
P\Big(\bigcup_{i=1}^n A_i\Big)\le\sum_{i=1}^n P(A_i).
$$

*Proof.* Induction on $n$. For $n=1$ it is an equality. Assume it for $n-1$. Writing
$U=\bigcup_{i<n}A_i$, the two-event addition rule gives
$P(U\cup A_n)=P(U)+P(A_n)-P(U\cap A_n)\le P(U)+P(A_n)$, since $P(U\cap A_n)\ge0$. By the
induction hypothesis $P(U)\le\sum_{i<n}P(A_i)$, so
$P(\bigcup_{i\le n}A_i)\le\sum_{i\le n}P(A_i)$. ∎

**CS connection.** The union bound is the single most-used inequality in the analysis of
randomized algorithms. If an algorithm fails only when at least one of $n$ "bad events"
$A_i$ happens, and each has tiny probability $P(A_i)\le\delta/n$, then the total failure
probability is at most $n\cdot(\delta/n)=\delta$ — no independence assumptions needed. Its
power is that it needs *nothing* about how the $A_i$ interact.

## 13.8 Worked problems I: dice, cards, urns

We consolidate the rules so far on the three workhorse experiments, easy to hard. Every
number is verified.

**Problem 1 (single die, warm-up).** Roll one fair die. Then
$P(\text{prime})=P(\{2,3,5\})=\tfrac36=\tfrac12$ and, since "roll $1$ or $2$" are
incompatible, $P(\{1\}\cup\{2\})=\tfrac16+\tfrac16=\tfrac13$.

**Problem 2 (two dice, the sum distribution).** Roll two fair dice; $|\Omega|=36$ equally
likely ordered pairs. Counting the pairs $(a,b)$ with $a+b=s$ gives the full distribution:

| Sum $s$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| favourable pairs | 1 | 2 | 3 | 4 | 5 | 6 | 5 | 4 | 3 | 2 | 1 |
| $P(\text{sum}=s)$ | $\tfrac1{36}$ | $\tfrac2{36}$ | $\tfrac3{36}$ | $\tfrac4{36}$ | $\tfrac5{36}$ | $\tfrac6{36}$ | $\tfrac5{36}$ | $\tfrac4{36}$ | $\tfrac3{36}$ | $\tfrac2{36}$ | $\tfrac1{36}$ |

The counts sum to $1+2+\cdots+6+\cdots+2+1=36$, confirming the probabilities total $1$. The
most likely sum is $7$ (six ways: $(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)$), giving
$P(\text{sum}=7)=\tfrac{6}{36}=\tfrac16$.

**Problem 3 (at least one six — complement).** Roll two dice.
$P(\text{no six})=\big(\tfrac56\big)^2=\tfrac{25}{36}$ (each die independently avoids six),
so by the complement rule $P(\text{at least one six})=1-\tfrac{25}{36}=\tfrac{11}{36}\approx0.306$.
Direct enumeration confirms $11$ of the $36$ pairs contain a six.

**Problem 4 (cards, addition rule).** Draw one card from $52$.

$$
P(\text{king or heart})=P(\text{king})+P(\text{heart})-P(\text{king of hearts}) =\tfrac{4}{52}+\tfrac{13}{52}-\tfrac{1}{52}=\tfrac{16}{52}=\tfrac{4}{13},
$$

subtracting the king of hearts, counted in both.

**Problem 5 (cards, two aces).** Draw $2$ cards without replacement. Counting unordered
hands, $P(\text{both aces})=\dfrac{\binom{4}{2}}{\binom{52}{2}}=\dfrac{6}{1326}=\dfrac1{221}\approx0.0045$.
The sequential view agrees: $\tfrac{4}{52}\cdot\tfrac{3}{51}=\tfrac{12}{2652}=\tfrac1{221}$.

**Problem 6 (cards, at least one ace in a 5-card hand — complement).**

$$
P(\text{no ace})=\frac{\binom{48}{5}}{\binom{52}{5}}=\frac{1{,}712{,}304}{2{,}598{,}960}\approx0.6588, \qquad P(\text{at least one ace})\approx1-0.6588=0.3412.
$$

**Problem 7 (urn without replacement, hypergeometric).** An urn has $6$ white and $4$ black
balls; draw $3$ without replacement.

| Event | Count | Probability |
|---|---|---|
| all $3$ white | $\binom63=20$ | $20/120=\tfrac16\approx0.167$ |
| exactly $2$ white, $1$ black | $\binom62\binom41=60$ | $60/120=\tfrac12$ |
| exactly $1$ white, $2$ black | $\binom61\binom42=36$ | $36/120=\tfrac{3}{10}=0.3$ |
| no white ($3$ black) | $\binom43=4$ | $4/120=\tfrac1{30}\approx0.033$ |

The four cases partition the outcomes: $20+60+36+4=120=\binom{10}{3}$, so the probabilities
sum to $1$. ✓

**Problem 8 (De Méré's problem, historical, hard).** The Chevalier de Méré, a 17th-century
gambler, asked Pascal about two bets that "should" have equal odds:

- Bet A: at least one six in **four** rolls of one die.
- Bet B: at least one double-six in **twenty-four** rolls of two dice.

Using the complement rule and independence of rolls,

$$
P(\text{A})=1-\Big(\tfrac56\Big)^{4}=1-\tfrac{625}{1296}=\tfrac{671}{1296}\approx0.5177,
$$

$$
P(\text{B})=1-\Big(\tfrac{35}{36}\Big)^{24}\approx1-0.5086=0.4914.
$$

So Bet A is (barely) favourable and Bet B (barely) unfavourable — a difference of about
$2.6$ percentage points that de Méré had detected *empirically* at the gaming table. The
correspondence Pascal and Fermat exchanged to resolve such puzzles in 1654 is usually taken
as the birth of probability theory.

## 13.9 Conditional probability

Often we learn *partial* information — a related event $B$ is known to have occurred — and
must revise the probability of $A$ accordingly.

**Definition (conditional probability).** For events $A,B$ with $P(B)>0$, the **conditional
probability of $A$ given $B$** is

$$
P(A\mid B)=\frac{P(A\cap B)}{P(B)}.
$$

![Venn diagram of overlapping events A and B, with the shaded intersection illustrating P(A|B) = P(A∩B)/P(B)](img/l13_conditional.png)

**Intuition.** Learning that $B$ occurred *shrinks the world* from $\Omega$ down to $B$:
outcomes outside $B$ are now impossible. We rescale so that $B$ carries the full probability
$1$ (divide by $P(B)$) and ask what fraction of $B$'s probability also lies in $A$ (the
numerator $P(A\cap B)$). In the classical model this is transparent:
$P(A\mid B)=\dfrac{|A\cap B|/|\Omega|}{|B|/|\Omega|}=\dfrac{|A\cap B|}{|B|}$ — literally
"favourable-within-$B$ over size-of-$B$."

**Example (die).** With $A=$"roll a $2$" and $B=$"even":
$P(A\mid B)=\dfrac{P(\{2\})}{P(\{2,4,6\})}=\dfrac{1/6}{3/6}=\dfrac13$. Knowing the roll is even
lifts the chance of a $2$ from $\tfrac16$ to $\tfrac13$, because only three outcomes remain.

**Remark (conditioning yields a probability).** For fixed $B$ with $P(B)>0$, the map
$A\mapsto P(A\mid B)$ is itself a probability measure on $\Omega$: it is non-negative,
assigns $P(\Omega\mid B)=P(B)/P(B)=1$, and is additive over incompatible events. So every
theorem proved above (complement rule, addition rule, …) holds *inside* a conditional world.

### The multiplication rule and the chain rule

Rearranging the definition removes the fraction and gives the probability that **both**
events occur.

**Multiplication rule.** For $P(A),P(B)>0$,

$$
P(A\cap B)=P(B)\,P(A\mid B)=P(A)\,P(B\mid A).
$$

This generalizes to any number of events.

**Theorem (chain rule / general multiplication rule).** For events $A_1,\dots,A_n$ with
$P(A_1\cap\cdots\cap A_{n-1})>0$,

$$
P(A_1\cap A_2\cap\cdots\cap A_n)=P(A_1)\,P(A_2\mid A_1)\,P(A_3\mid A_1\cap A_2)\cdots P(A_n\mid A_1\cap\cdots\cap A_{n-1}).
$$

*Proof.* Induction on $n$. The case $n=2$ is the multiplication rule. Assume the identity for
$n-1$ and write $B=A_1\cap\cdots\cap A_{n-1}$; note $P(B)>0$ implies each earlier
intersection is positive too, by monotonicity. Then

$$
P(A_1\cap\cdots\cap A_n)=P(B\cap A_n)=P(B)\,P(A_n\mid B),
$$

and expanding $P(B)$ by the induction hypothesis gives exactly the stated product. ∎

**Example (draws without replacement, dependent).** A box holds $10$ white and $14$ red
balls ($24$ total); draw $2$ without replacement. With $A=$"first white," $B=$"second white,"

$$
P(A\cap B)=P(A)\,P(B\mid A)=\frac{10}{24}\cdot\frac{9}{23}=\frac{90}{552}=\frac{15}{92}\approx0.163.
$$

The draws are **dependent**: removing a white ball changes the second draw's odds from
$\tfrac{10}{24}$ to $\tfrac{9}{23}$.

**Example (defective parts, dependent).** $4\%$ of parts are defective, so $96\%$ are
non-defective; of the non-defective parts, $75\%$ are low quality. The probability a random
part is non-defective **and** low quality is, by the multiplication rule,
$0.96\cdot0.75=0.72=72\%$.

**Example (two children — a conditional-probability pitfall).** A family has two children;
assume the four birth orders $\{BB,BG,GB,GG\}$ are equally likely.

- *Given that at least one child is a boy*, what is $P(\text{both boys})$? The condition is
  $\{BB,BG,GB\}$ (three equally likely outcomes) and "both boys" is $\{BB\}$, so the answer is
  $\tfrac13$.
- *Given that the elder child is a boy*, what is $P(\text{both boys})$? Now the condition is
  $\{BB,BG\}$ and the answer is $\tfrac{1}{2}$.

The two questions sound alike but condition on *different* events, and the answers genuinely
differ. This is the classic warning that in $P(A\mid B)$ the event $B$ must be pinned down
exactly.

> **Common pitfall (transposing the conditional).** $P(A\mid B)$ and $P(B\mid A)$ are
> different numbers; equating them is the **prosecutor's fallacy**. "The probability of this
> DNA match if the suspect is innocent is $1$ in a million" ($P(\text{match}\mid\text{innocent})$)
> is *not* "the probability the suspect is innocent given the match"
> ($P(\text{innocent}\mid\text{match})$). Bayes' theorem below is exactly the machine for
> converting one into the other, and it shows they can differ by orders of magnitude when the
> base rates differ.

> **Common pitfall ($P(A\mid B)$ vs $P(A\cap B)$).** The conditional $P(A\mid B)$ presumes $B$
> has happened and lives in the shrunken world $B$; the joint $P(A\cap B)$ makes no such
> assumption and lives in all of $\Omega$. They are related by a factor of $P(B)$ and are
> equal only when $P(B)=1$.

## 13.10 Independence

**Definition (independence of two events).** Events $A$ and $B$ are **independent** if

$$
P(A\cap B)=P(A)\,P(B).
$$

Equivalently, when $P(B)>0$, this says $P(A\mid B)=P(A)$: knowing $B$ tells us nothing new
about $A$.

Independence is often *justified physically* (separate coins, distinct dice, draws **with**
replacement, independently chosen hash keys), but the defining equation is the formal test —
and physical intuition can mislead, so when in doubt, check the equation.

**Example (independent, product rule).** Roll a die twice:
$P(\text{first }6\text{ and second }6)=\tfrac16\cdot\tfrac16=\tfrac1{36}$, matching direct
enumeration of the $36$ outcomes.

**Example (two boxes, independent).** Box 1 has $2$ white and $10$ red ($12$ total); Box 2
has $8$ white and $4$ red ($12$ total). Draw one ball from each. With $A=$"white from Box 1"
and $B=$"white from Box 2" the draws are independent, so

$$
P(A\cap B)=P(A)\,P(B)=\frac{2}{12}\cdot\frac{8}{12}=\frac16\cdot\frac23=\frac19\approx0.111.
$$

**Theorem (incompatible $\ne$ independent).** If $A,B$ are incompatible and both have
positive probability, then they are **dependent**.

*Proof.* Incompatibility means $A\cap B=\varnothing$, so $P(A\cap B)=P(\varnothing)=0$. But
independence would require $P(A\cap B)=P(A)P(B)>0$, since both factors are positive. The two
are contradictory, so $A,B$ cannot be independent. ∎

This confirms the warning from the start of the lecture: incompatible events with positive
probability are as far from independent as possible — the occurrence of one drives the
other's conditional probability to $0$.

**Remark (mutual vs. pairwise independence).** For three or more events, *pairwise*
independence (every pair satisfies the product rule) is weaker than *mutual* independence,
which requires the product rule for **every** sub-collection, e.g.
$P(A\cap B\cap C)=P(A)P(B)P(C)$ as well as the three pairwise equations. There are standard
examples (two independent fair coins with $C=$"the coins agree") that are pairwise but not
mutually independent. Independence of "steps" in the multiplication principle is what makes
$P=\prod p_i$ valid, as in the "at least one six" and De Méré computations.

**Example (lottery — dependent and compatible).** Of $100$ tickets, $5$ win; you buy $2$.
Find $P(\text{at least one wins})$. The two "this ticket wins" events are compatible and
dependent (sampling without replacement). The complement route is cleanest:

$$
P(\text{no win})=\frac{95}{100}\cdot\frac{94}{99}\approx0.9020,\qquad P(\text{at least one})\approx1-0.9020=0.098.
$$

The general addition rule agrees: with $P(A)=P(B)=\tfrac{5}{100}$ and
$P(A\cap B)=\tfrac{5}{100}\cdot\tfrac{4}{99}\approx0.00202$,
$P(A\cup B)=0.05+0.05-0.00202\approx0.098$. ✓

## 13.11 The law of total probability

Suppose a first stage of an experiment produces one of several **hypotheses** (causes,
scenarios), and a later event $A$ has known probability *under each*. The law of total
probability assembles these into $P(A)$.

**Theorem (law of total probability).** Let $H_1,\dots,H_n$ form a complete group (partition
of $\Omega$): pairwise incompatible, $H_1\cup\cdots\cup H_n=\Omega$, and each $P(H_i)>0$.
Then for any event $A$,

$$
P(A)=\sum_{i=1}^n P(H_i)\,P(A\mid H_i).
$$

*Proof.* Because the $H_i$ cover $\Omega$,

$$
A=A\cap\Omega=A\cap\Big(\bigcup_{i=1}^n H_i\Big)=\bigcup_{i=1}^n(A\cap H_i),
$$

using distributivity (Lecture 2). The sets $A\cap H_i$ are pairwise incompatible, since
$(A\cap H_i)\cap(A\cap H_j)\subseteq H_i\cap H_j=\varnothing$ for $i\ne j$. By finite
additivity and then the multiplication rule ($P(A\cap H_i)=P(H_i)P(A\mid H_i)$, valid as
$P(H_i)>0$),

$$
P(A)=\sum_{i=1}^n P(A\cap H_i)=\sum_{i=1}^n P(H_i)\,P(A\mid H_i).\qquad\blacksquare
$$

Read it as a **weighted average**: the chance of $A$ is the average of its conditional
chances $P(A\mid H_i)$, each weighted by how likely its hypothesis $H_i$ is.

![Probability tree for the law of total probability: branch on each hypothesis Hᵢ, then on A, giving P(A) = Σ P(Hᵢ)·P(A|Hᵢ)](img/l13_total_prob.png)

**Example (choose an urn, then a ball).** Urn 1 holds $2$ white and $10$ red; Urn 2 holds $8$
white and $4$ red. Pick an urn at random ($P(H_1)=P(H_2)=\tfrac12$) and draw one ball. The
probability it is white:

$$
P(W)=P(H_1)P(W\mid H_1)+P(H_2)P(W\mid H_2)=\tfrac12\cdot\tfrac{2}{12}+\tfrac12\cdot\tfrac{8}{12}=\tfrac12\cdot\tfrac{10}{12}=\tfrac{5}{12}\approx0.417.
$$

A **probability tree** organizes exactly this computation — first branch on the hypothesis,
then on $A$, multiply along a path, add across paths ending in $A$:

```
                 P(W|H1)=2/12
        P(H1)=1/2 ─────────── White   path prob = 1/2 · 2/12 = 2/24
       ┌──────── Urn 1
       │         └─────────── Red     1/2 · 10/12 = 10/24
 start ┤
       │         ┌─────────── White   1/2 · 8/12  = 8/24
       └──────── Urn 2
        P(H2)=1/2 ─────────── Red     1/2 · 4/12  = 4/24
                 P(R|H2)=4/12
   P(White) = 2/24 + 8/24 = 10/24 = 5/12 ✓
```

## 13.12 Bayes' theorem

The law of total probability runs "forward": from causes $H_i$ to effect $A$. Bayes' theorem
runs it **backward**, updating the probability of each cause *after* the effect is observed —
the mathematics of learning from evidence.

**Theorem (Bayes).** Let $H_1,\dots,H_n$ be a complete group with each $P(H_i)>0$, and let
$A$ be an event with $P(A)>0$. Then for each $i$,

$$
P(H_i\mid A)=\frac{P(H_i)\,P(A\mid H_i)}{\displaystyle\sum_{j=1}^n P(H_j)\,P(A\mid H_j)}=\frac{P(H_i)\,P(A\mid H_i)}{P(A)}.
$$

*Proof.* By the definition of conditional probability (using $P(A)>0$) and then the
multiplication rule applied to the numerator,

$$
P(H_i\mid A)=\frac{P(H_i\cap A)}{P(A)}=\frac{P(H_i)\,P(A\mid H_i)}{P(A)}.
$$

Finally substitute the law of total probability $P(A)=\sum_j P(H_j)P(A\mid H_j)$ for the
denominator. ∎

**Vocabulary.** $P(H_i)$ is the **prior** (belief before evidence), $P(A\mid H_i)$ the
**likelihood** (how well hypothesis $i$ predicts the evidence), and $P(H_i\mid A)$ the
**posterior** (updated belief). Bayes' theorem is the formal rule for turning prior belief +
data into posterior belief.

**Odds form (two hypotheses).** For $H$ and $\overline H$, dividing the two Bayes formulas
cancels the shared denominator $P(A)$ and yields a memorable multiplicative update:

$$
\underbrace{\frac{P(H\mid A)}{P(\overline H\mid A)}}_{\text{posterior odds}} =\underbrace{\frac{P(H)}{P(\overline H)}}_{\text{prior odds}}\cdot \underbrace{\frac{P(A\mid H)}{P(A\mid \overline H)}}_{\text{likelihood ratio}}.
$$

### Worked example: a medical test (with a natural-frequency cross-check)

A disease affects $1\%$ of a population, so the prior is $P(D)=0.01$. A test has
**sensitivity** $P(+\mid D)=0.99$ (it catches $99\%$ of true cases) and **false-positive
rate** $P(+\mid\overline D)=0.05$. A randomly chosen person tests positive. What is
$P(D\mid+)$?

*Step 1 — total probability of a positive test.*

$$
P(+)=P(D)P(+\mid D)+P(\overline D)P(+\mid\overline D)=0.01\cdot0.99+0.99\cdot0.05=0.0099+0.0495=0.0594.
$$

*Step 2 — Bayes.*

$$
P(D\mid+)=\frac{P(D)P(+\mid D)}{P(+)}=\frac{0.0099}{0.0594}\approx0.167.
$$

Despite a "$99\%$ accurate" test, a positive result gives only about a **$16.7\%$** chance of
actually having the disease. The reason is the **base rate**: the disease is rare, so the
few genuine positives are swamped by false positives generated from the huge healthy
majority.

![Natural-frequency tree for the medical test: of 10,000 people, 100 are sick (99 test positive) and 9,900 healthy (495 test positive), so P(sick | +) = 99/(99+495) ≈ 16.7%](img/l13_bayes_medical.png)

*Natural-frequency cross-check.* Abandon fractions and imagine a concrete cohort of
$10{,}000$ people. This "confusion matrix" is exactly the $2\times2$ contingency table used
to evaluate classifiers in machine learning:

| | Test $+$ | Test $-$ | Row total |
|---|---|---|---|
| **Diseased** ($1\%$) | $99$ (true pos.) | $1$ (false neg.) | $100$ |
| **Healthy** ($99\%$) | $495$ (false pos.) | $9{,}405$ (true neg.) | $9{,}900$ |
| **Column total** | $594$ | $9{,}406$ | $10{,}000$ |

Of the $594$ people who test positive, only $99$ are truly ill, so
$P(D\mid+)=99/594=0.1\overline{6}\approx0.167$ — identical to Bayes, and far easier to feel.
The odds form gives the same answer in one line: prior odds
$0.01/0.99=1/99$, likelihood ratio $0.99/0.05=19.8$, posterior odds $19.8/99=0.2$, hence
posterior probability $0.2/(1+0.2)=1/6\approx0.167$.

**CS / ML connection.** In classifier terms the table's quantities are named: **recall
(sensitivity)** $=P(+\mid D)$, and **precision** $=P(D\mid+)=99/594\approx0.167$. A spam
filter faces the same arithmetic — a rare event (a genuine phishing mail) with an imperfect
detector — and a **naive Bayes** classifier is literally Bayes' theorem applied under a
simplifying independence assumption on the features (words). Base-rate neglect is the human
bug that Bayesian reasoning fixes.

## 13.13 The birthday problem

*In a room of $n$ people, how likely is it that two share a birthday?* The answer is
famously larger than intuition suggests, and it is the exact model of hash collisions.

**Setup.** Assume $365$ equally likely birthdays, independent across people (ignore leap
days and twins). The sample space of birthday assignments has $365^{\,n}$ equally likely
elements. Let $A_n=$"some two of the $n$ people share a birthday." Compute the complement
$\overline{A_n}=$"all $n$ birthdays are distinct" — far easier to count.

**Derivation.** Assigning $n$ *distinct* birthdays is an ordered selection of $n$ days from
$365$ without repetition, i.e. a $k$-permutation with $k=n$:

$$
P(\overline{A_n})=\frac{P(365,n)}{365^{\,n}}=\frac{365\cdot364\cdots(365-n+1)}{365^{\,n}} =\prod_{j=0}^{n-1}\frac{365-j}{365}=\prod_{j=1}^{n-1}\Big(1-\frac{j}{365}\Big).
$$

Therefore $P(A_n)=1-P(\overline{A_n})$. Tabulating:

| $n$ | $P(\text{all distinct})$ | $P(\text{some match})$ |
|---|---|---|
| 10 | 0.8831 | 0.1169 |
| 20 | 0.5886 | 0.4114 |
| **23** | **0.4927** | **0.5073** |
| 30 | 0.2937 | 0.7063 |
| 40 | 0.1088 | 0.8912 |
| 50 | 0.0296 | 0.9704 |
| 70 | 0.0008 | 0.9992 |

At $n=23$ the probability of a shared birthday first exceeds $\tfrac12$ — only $23$ people,
not the $183$ (half of $365$) that intuition often guesses. By $n=70$ a match is virtually
certain.

![Curve of P(shared birthday) against the number of people, crossing the 50% line at 23 people (50.7%)](img/l13_birthday.png)

**Why so few?** A shared birthday needs only *some* pair to coincide, and $n$ people form
$\binom{n}{2}=\dfrac{n(n-1)}{2}$ pairs — a quantity that grows like $n^2$. For $n=23$ that is
$\binom{23}{2}=253$ pairs, already comparable to $365$. The standard approximation makes this
precise: using $1-x\approx e^{-x}$,

$$
P(\overline{A_n})=\prod_{j=1}^{n-1}\Big(1-\tfrac{j}{365}\Big)\approx\exp\!\Big(-\tfrac1{365}\sum_{j=1}^{n-1}j\Big)=\exp\!\Big(-\frac{n(n-1)}{2\cdot365}\Big).
$$

For $n=23$: $\dfrac{23\cdot22}{2\cdot365}=\dfrac{253}{365}\approx0.693$, and $e^{-0.693}\approx0.500$,
so $P(A_{23})\approx0.50$ — matching the exact $0.5073$.

**CS connection (hash collisions and the birthday attack).** Replace $365$ by the number
$N$ of hash buckets (or possible hash values). The same computation shows that once about
$\sqrt{N}$ items have been hashed, a collision becomes more likely than not. This is why a
hash function with a $b$-bit output ($N=2^b$) offers only about $2^{b/2}$ collision
resistance, and why the **birthday attack** forces cryptographic hash lengths to be doubled:
to resist collisions at the $2^{128}$ level, one needs a $256$-bit hash. The birthday
problem is thus a load-bearing calculation in the design of hash tables and cryptographic
digests.

## 13.14 The Monty Hall problem

A game show has three doors: behind one is a car, behind the other two are goats. You pick a
door. The host — who **knows** what is behind each door — opens a *different* door, always
revealing a goat, and offers you the chance to switch to the remaining unopened door.
**Should you switch?**

**State the rules precisely (they matter).** The standard problem assumes:

1. the car is equally likely behind any door;
2. the host always opens a door you did not pick and always reveals a goat;
3. if your initial pick hides the car (so the host has two goat doors to choose from), the
   host picks between them uniformly at random.

Under these rules the answer is that **switching wins with probability $\tfrac23$**, staying
only $\tfrac13$. Two independent arguments confirm it.

**Argument 1 (enumeration on the initial pick).** Your first choice is right (car) with
probability $\tfrac13$ and wrong (goat) with probability $\tfrac23$.

- If your first pick was the car ($\tfrac13$): the other unopened door hides a goat, so
  **switching loses**.
- If your first pick was a goat ($\tfrac23$): the host is forced to reveal the *other* goat,
  so the remaining unopened door hides the car, and **switching wins**.

Hence $P(\text{win}\mid\text{switch})=P(\text{first pick was a goat})=\tfrac23$.

**Argument 2 (Bayes).** Say you pick door 1 and the host opens door 3. Let $C_i=$"car behind
door $i$" (priors $\tfrac13$ each) and $O_3=$"host opens door 3." The likelihoods encode the
rules:

| Hypothesis | $P(O_3\mid C_i)$ | reason |
|---|---|---|
| $C_1$ (your door) | $\tfrac12$ | host free to open 2 or 3, chooses randomly |
| $C_2$ | $1$ | host cannot open 1 (yours) or 2 (car) → must open 3 |
| $C_3$ | $0$ | host never opens the car's door |

By total probability $P(O_3)=\tfrac13\cdot\tfrac12+\tfrac13\cdot1+\tfrac13\cdot0=\tfrac16+\tfrac13=\tfrac12$.
Then Bayes gives

$$
P(C_1\mid O_3)=\frac{\tfrac13\cdot\tfrac12}{\tfrac12}=\frac13,\qquad P(C_2\mid O_3)=\frac{\tfrac13\cdot1}{\tfrac12}=\frac23.
$$

Staying keeps door 1 with win probability $\tfrac13$; switching moves to door 2 with win
probability $\tfrac23$. ∎

> **Why intuition fails (the crucial point).** The two remaining doors are *not* symmetric,
> so "it's now 50-50" is wrong. The host's action carries information: when your first pick
> was a goat (probability $\tfrac23$), the host is *forced* to expose the only other goat,
> effectively pointing at the car. Switching converts your initial $\tfrac23$ chance of being
> wrong into a $\tfrac23$ chance of winning. If instead the host opened a door *at random* and
> merely happened to reveal a goat, the information would be different and the odds would
> indeed become $\tfrac12$ — which is why stating the rules is not pedantry.

## 13.15 Random variables and expectation

Often we care not about *which* outcome occurs but about a *number* attached to it — the sum
of two dice, the number of collisions in a hash table, the running time of a randomized
algorithm.

**Definition (random variable).** A **random variable** on a sample space $\Omega$ is a
function $X:\Omega\to\mathbb{R}$ assigning a real number to each outcome. For discrete
$\Omega$ its **probability mass function** is $p_X(x)=P(X=x)=P(\{\omega:X(\omega)=x\})$; the
masses are non-negative and sum to $1$ over the possible values.

**Example.** For one die, $X(\omega)=\omega$ has $p_X(k)=\tfrac16$ for $k=1,\dots,6$. For two
dice, $S=$"sum" is a random variable with the mass function tabulated in Problem 2.

**Indicator variables.** The **indicator** of an event $A$ is
$\mathbf 1_A(\omega)=1$ if $\omega\in A$ and $0$ otherwise. It converts an event into a
$\{0,1\}$-valued random variable and is the bridge between events and expectations.

**Definition (expectation).** The **expected value (mean)** of a discrete random variable $X$
is the probability-weighted average of its values,

$$
E[X]=\sum_{x}x\,P(X=x)=\sum_{\omega\in\Omega}X(\omega)\,P(\{\omega\}).
$$

It is the "long-run average" the value of $X$ approaches when the experiment is repeated many
times (this is what the law of large numbers guarantees).

**Example (one die).** $E[X]=\sum_{k=1}^{6}k\cdot\tfrac16=\tfrac{1+2+3+4+5+6}{6}=\tfrac{21}{6}=3.5$.
The mean $3.5$ is not itself an attainable value — expectation is an average, not a
prediction of any single roll.

**Example (indicator).** $E[\mathbf 1_A]=1\cdot P(A)+0\cdot P(\overline A)=P(A)$. The expected
value of an indicator is just the probability of its event — the identity that makes the next
theorem so useful.

**Theorem (linearity of expectation).** For any random variables $X,Y$ on the same finite
$\Omega$ and constants $a,b\in\mathbb R$,

$$
E[aX+bY]=a\,E[X]+b\,E[Y].
$$

Crucially, this holds **whether or not $X$ and $Y$ are independent**.

*Proof.* Using the outcome-sum form of expectation and rearranging a finite sum,

$$
E[aX+bY]=\sum_{\omega\in\Omega}\big(aX(\omega)+bY(\omega)\big)P(\{\omega\}) =a\sum_{\omega}X(\omega)P(\{\omega\})+b\sum_{\omega}Y(\omega)P(\{\omega\})=a\,E[X]+b\,E[Y].
$$

The only facts used are the distributive law and that a finite sum can be split — no
independence anywhere. ∎

**Example (sum of two dice, via linearity).** Let $X_1,X_2$ be the two dice. Then
$E[X_1+X_2]=E[X_1]+E[X_2]=3.5+3.5=7$, instantly — no need to weight the $11$ sum-values by
the table in Problem 2 (though doing so also gives $252/36=7$). Linearity turns a messy
convolution into one line.

**Example (expected number of birthday matches).** Among $n$ people, let $X$ count the pairs
sharing a birthday. Writing $X=\sum_{\text{pairs }(i,j)}\mathbf 1_{ij}$, where $\mathbf 1_{ij}$
indicates that persons $i,j$ match, linearity and $E[\mathbf 1_{ij}]=P(\text{match})=\tfrac1{365}$
give

$$
E[X]=\binom{n}{2}\cdot\frac1{365}=\frac{n(n-1)}{2\cdot365}.
$$

For $n=23$, $E[X]=253/365\approx0.69$ — the very exponent that appeared in the birthday
approximation, now explained: matches become likely exactly when the *expected* number of
matching pairs reaches order $1$. (Note the pair-events are not independent, yet linearity
still applies — its great strength.)

**Bernoulli and binomial.** An event $A$ with $P(A)=p$ defines a **Bernoulli** variable
$\mathbf 1_A$ with $E[\mathbf 1_A]=p$. Repeating $n$ *independent* Bernoulli trials, the count
of successes $X$ is **binomial**, $P(X=k)=\binom{n}{k}p^k(1-p)^{n-k}$, and writing
$X=\mathbf 1_{A_1}+\cdots+\mathbf 1_{A_n}$ gives by linearity

$$
E[X]=\sum_{i=1}^n P(A_i)=np.
$$

For example, in $10$ fair coin flips the expected number of heads is $10\cdot\tfrac12=5$.

### Variance and standard deviation

The mean alone does not capture **spread**. The **variance** of $X$ is the expected
squared deviation from the mean,
$$\operatorname{Var}(X)=E\big[(X-E[X])^2\big]=E[X^2]-(E[X])^2\ \ge 0,$$
and the **standard deviation** $\sigma(X)=\sqrt{\operatorname{Var}(X)}$ is in the same
units as $X$. For the single die, $\operatorname{Var}=\tfrac{35}{12}\approx2.92$ and
$\sigma\approx1.71$. Two handy rules: $\operatorname{Var}(aX+b)=a^2\operatorname{Var}(X)$,
and for **independent** $X,Y$, $\operatorname{Var}(X+Y)=\operatorname{Var}(X)+\operatorname{Var}(Y)$.

For a **dataset** $x_1,\dots,x_N$ — the descriptive-statistics view used in **Lab 7** —
the same formula with equal weights $1/N$ gives the **population** mean, variance, and
standard deviation
$$\mu=\frac1N\sum_i x_i,\qquad \sigma^2=\frac1N\sum_i (x_i-\mu)^2,\qquad \sigma=\sqrt{\sigma^2};$$
the **sample** variance divides by $N-1$ instead of $N$ (an unbiased estimate when the
data are a sample, not the whole population). Variance also controls how fast averages
converge (Chebyshev's inequality, concentration bounds) — a theme of the next course, and
the reason randomized algorithms are *reliably* fast, not merely fast on average.

## A short history

Games of chance are ancient, but their *mathematics* is not. Gerolamo **Cardano**
(c. 1564) wrote the first analysis of dice odds. The subject proper was born in **1654** in
the correspondence between Blaise **Pascal** and Pierre de **Fermat**, prompted by exactly
the kind of gambling puzzle de Méré posed above. Christiaan **Huygens** wrote the first
textbook (1657); Jacob **Bernoulli** proved the first **law of large numbers** (published
1713), rigorously linking probability to long-run frequency; Thomas **Bayes**' essay on
inverse probability appeared posthumously (1763); and Pierre-Simon **Laplace** systematized
the classical definition around 1812. The modern **axiomatic** foundation — the three axioms
of this lecture, freeing probability from any reliance on symmetry or frequency — was laid by
Andrey **Kolmogorov** in 1933, and it is his framework we have used throughout.

## Chapter summary

- A **random experiment** has a **sample space** $\Omega$ of elementary outcomes; an
  **event** is a subset $A\subseteq\Omega$. Events *are* sets, so the union/intersection/
  complement algebra and De Morgan's laws of Lectures 1–2 transfer verbatim (the
  event–set dictionary).
- **Event types:** certain ($\Omega$), impossible ($\varnothing$), compatible vs.
  **incompatible** ($A\cap B=\varnothing$), complementary $A,\overline A$, a **complete
  group** (partition, cf. Lecture 3), and **independent** vs. **dependent**.
- **Classical probability** $P(A)=|A|/|\Omega|$ for equally likely outcomes reduces
  probability to counting; the **statistical** view estimates $P(A)$ by relative frequency
  (law of large numbers) when symmetry is unavailable.
- **Combinatorics.** Multiplication principle $\Rightarrow$ permutations $n!$, arrangements
  $P(n,k)=\dfrac{n!}{(n-k)!}$, combinations $\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}$ (derived via
  $P(n,k)=\binom{n}{k}k!$); Pascal's identity $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$.
- **Kolmogorov's axioms:** $P(A)\ge0$, $P(\Omega)=1$, additivity over incompatible events —
  from which we *proved* $P(\varnothing)=0$, $P(\overline A)=1-P(A)$, $0\le P(A)\le1$,
  monotonicity, the addition rule $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ (a probabilistic
  inclusion–exclusion), its three-event form, and Boole's inequality (union bound).
- **Conditional probability** $P(A\mid B)=\dfrac{P(A\cap B)}{P(B)}$ shrinks the sample space
  to $B$; the **multiplication rule** $P(A\cap B)=P(B)P(A\mid B)$ and its **chain rule**
  generalization follow.
- **Independence:** $P(A\cap B)=P(A)P(B)$, equivalently $P(A\mid B)=P(A)$. Incompatible
  events of positive probability are provably *dependent*.
- **Law of total probability** $P(A)=\sum_i P(H_i)P(A\mid H_i)$ (proved via a partition) and
  **Bayes' theorem** $P(H_i\mid A)=\dfrac{P(H_i)P(A\mid H_i)}{\sum_j P(H_j)P(A\mid H_j)}$
  (proved from it) turn priors + likelihoods into posteriors; the odds form multiplies prior
  odds by the likelihood ratio.
- **Three set pieces:** the **birthday problem** ($n=23\Rightarrow P\approx0.507$; models
  hash/birthday-attack collisions at $\sqrt N$), **Monty Hall** (switch to win $\tfrac23$),
  and the **medical-test** Bayes calculation ($P(D\mid+)\approx16.7\%$; base-rate neglect).
- **Random variables** $X:\Omega\to\mathbb R$ and **expectation** $E[X]=\sum_x xP(X=x)$;
  **linearity of expectation** $E[aX+bY]=aE[X]+bE[Y]$ holds without independence; a binomial
  count has $E[X]=np$.

## Exercises

### Warm-up

1. Roll one fair die. Write $\Omega$, and as subsets the events $A=$"odd," $B=$"at least
   $4$." Compute $P(A)$, $P(B)$, $P(A\cap B)$, $P(A\cup B)$ and verify the addition rule.
2. Give $\Omega$ for tossing three distinguishable coins and its size. Find the probability
   of exactly two heads.
3. Explain in one sentence each the difference between (a) incompatible and independent
   events, and (b) $P(A\mid B)$ and $P(A\cap B)$.
4. A committee of $4$ is chosen from $12$ people. How many committees are possible? If
   instead the four take *distinct* roles (chair, secretary, treasurer, webmaster), how many
   role-assignments are possible?
5. From a standard deck, find $P(\text{red})$, $P(\text{queen})$, and $P(\text{red or queen})$.

### Standard

6. **(Derive a rule.)** Using only Kolmogorov's axioms, prove $P(A\cup B)=P(A)+P(B)-P(A\cap B)$,
   and state where you use additivity.
7. Two fair dice are rolled. Find $P(\text{sum}=9)$, $P(\text{sum is even})$, and
   $P(\text{sum}=9\mid \text{sum is odd})$.
8. An urn has $5$ red, $3$ green, $2$ blue balls; draw $3$ without replacement. Find the
   probability of (a) all red, (b) one of each colour, (c&#41; at least one blue.
9. A box has $8$ good and $2$ defective chips; draw $2$ without replacement. Find the
   probability both are good, first via the multiplication rule and again via combinations,
   and confirm the answers agree.
10. Cards: two are drawn without replacement. Find $P(\text{both hearts})$ and
    $P(\text{second is a heart}\mid \text{first is a heart})$.
11. **(Total probability.)** Factory lines I, II, III make $50\%,30\%,20\%$ of output with
    defect rates $2\%,3\%,5\%$. Find the probability a random item is defective.
12. **(Bayes.)** For Exercise 11, a random item is found defective. Which line most probably
    produced it? Give all three posterior probabilities.
13. A test for a condition present in $2\%$ of people has sensitivity $95\%$ and
    false-positive rate $10\%$. Find $P(\text{condition}\mid+)$ by Bayes, and cross-check with
    a natural-frequency table of $10{,}000$ people.
14. Show, using indicators and linearity, that the expected number of sixes in $n$ rolls of a
    fair die is $n/6$. Evaluate for $n=30$.

### Challenge

15. **(Birthday variant.)** In a room of $n$ people, let $A=$"someone shares *your* birthday."
    Show $P(A)=1-(364/365)^{\,n-1}$ and find the smallest $n$ making $P(A)\ge\tfrac12$.
    Explain why this $n$ is far larger than $23$.
16. **(Monty Hall, $k$ doors.)** Generalize Monty Hall to $N$ doors (one car), where after
    your pick the host opens exactly one goat door and offers a single switch. Show switching
    wins with probability $\dfrac{N-1}{N(N-2)}$ for $N\ge3$, and compare staying's $1/N$.
17. **(Inclusion–exclusion.)** Three fair dice are rolled. Using the three-event addition
    rule, find the probability that at least one die shows a six.
18. **(De Méré, generalized.)** For how many rolls $r$ of a single die does
    $P(\text{at least one six in }r\text{ rolls})$ first exceed $\tfrac12$? Justify with the
    complement rule.
19. **(Prosecutor's fallacy.)** A DNA test declares a match with probability $1$ in
    $1{,}000{,}000$ for a random innocent person. In a database of $10$ million innocent
    people, a match is found. Use the union bound (or expectation) to explain why "one in a
    million" does *not* mean the matched person is almost surely guilty.
20. **(Pairwise vs. mutual independence.)** Toss two fair coins; let $A=$"first is heads,"
    $B=$"second is heads," $C=$"the two coins agree." Show $A,B,C$ are pairwise independent but
    **not** mutually independent.

## Selected answers & hints

- **1.** $\Omega=\{1,\dots,6\}$; $A=\{1,3,5\},B=\{4,5,6\}$; $P(A)=P(B)=\tfrac12$,
  $A\cap B=\{5\}$ so $P(A\cap B)=\tfrac16$, $A\cup B=\{1,3,4,5,6\}$ so $P(A\cup B)=\tfrac56$;
  check $\tfrac12+\tfrac12-\tfrac16=\tfrac56$. ✓
- **2.** $|\Omega|=2^3=8$; exactly two heads is $\binom{3}{2}=3$ outcomes, probability
  $\tfrac38$.
- **4.** Committees: $\binom{12}{4}=495$. Distinct roles: $P(12,4)=12\cdot11\cdot10\cdot9=11{,}880=495\cdot4!$.
- **5.** $\tfrac{26}{52}=\tfrac12$; $\tfrac{4}{52}=\tfrac1{13}$; red-or-queen
  $=\tfrac{26}{52}+\tfrac{4}{52}-\tfrac{2}{52}=\tfrac{28}{52}=\tfrac7{13}$.
- **7.** $P(\text{sum}=9)=\tfrac4{36}=\tfrac19$; $P(\text{even})=\tfrac{18}{36}=\tfrac12$;
  sum $9$ is odd, so $P(\text{sum}=9\mid\text{odd})=\tfrac{4/36}{18/36}=\tfrac{4}{18}=\tfrac29$.
- **8.** Total $\binom{10}{3}=120$. (a) $\binom53/120=10/120=\tfrac1{12}$. (b)
  $\binom51\binom31\binom21/120=30/120=\tfrac14$. (c&#41; complement (no blue)
  $=\binom83/120=56/120=\tfrac{7}{15}$, so $P(\ge1\text{ blue})=\tfrac{8}{15}$.
- **9.** $\tfrac{8}{10}\cdot\tfrac{7}{9}=\tfrac{56}{90}=\tfrac{28}{45}$; and
  $\binom82/\binom{10}2=28/45$. ✓
- **11.** $0.5(0.02)+0.3(0.03)+0.2(0.05)=0.010+0.009+0.010=0.029$.
- **12.** Posteriors $=$ each term over $0.029$: line I $\tfrac{0.010}{0.029}\approx0.345$,
  II $\tfrac{0.009}{0.029}\approx0.310$, III $\tfrac{0.010}{0.029}\approx0.345$. Lines I and
  III tie as most probable.
- **13.** $P(+)=0.02(0.95)+0.98(0.10)=0.019+0.098=0.117$;
  $P(\text{cond}\mid+)=0.019/0.117\approx0.162$. Cohort of $10{,}000$: $200$ affected → $190$
  true positives; $9{,}800$ unaffected → $980$ false positives; $190/(190+980)=190/1170\approx0.162$. ✓
- **15.** Each other person misses your birthday with probability $364/365$, independently, so
  $P(\overline A)=(364/365)^{n-1}$. Solve $(364/365)^{n-1}\le\tfrac12$: $n-1\ge\ln 2/\ln(365/364)\approx252.65$,
  so $n=254$. It is huge compared to $23$ because only $n-1$ comparisons target *your* fixed
  day, versus $\binom{n}{2}$ comparisons among *all* pairs in the classic problem.
- **17.** $P(\ge1\text{ six})=1-(5/6)^3=1-125/216=91/216\approx0.421$; the three-event
  inclusion–exclusion gives $3\cdot\tfrac{36}{216}-3\cdot\tfrac{6}{216}+\tfrac{1}{216}=\tfrac{108-18+1}{216}=\tfrac{91}{216}$, agreeing.
- **18.** $1-(5/6)^r>\tfrac12\iff(5/6)^r<\tfrac12\iff r>\ln2/\ln(6/5)\approx3.80$, so $r=4$
  (matching De Méré's Bet A, $P\approx0.518$).
- **20.** $P(A)=P(B)=P(C)=\tfrac12$; pairwise $P(A\cap B)=\tfrac14=P(A)P(B)$,
  $P(A\cap C)=P(\{HH\})=\tfrac14=P(A)P(C)$, likewise $B,C$. But
  $P(A\cap B\cap C)=P(\{HH\})=\tfrac14\ne\tfrac18=P(A)P(B)P(C)$, so not mutually independent.

## Further reading

- K. H. **Rosen**, *Discrete Mathematics and Its Applications* — chapters on Discrete
  Probability and Counting (the multiplication principle, permutations/combinations, Bayes'
  theorem, and expected value are developed at this level).
- S. **Ross**, *A First Course in Probability* — a fuller, rigorous treatment of axioms,
  conditional probability, independence, and random variables.
- C. M. **Grinstead** and J. L. **Snell**, *Introduction to Probability* (freely available) —
  excellent worked problems, including Monty Hall and the birthday problem.
- For the algorithmic side: M. **Mitzenmacher** and E. **Upfal**, *Probability and Computing*
  — the union bound, hashing, and randomized algorithms in depth.