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.

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.

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.

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:

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.

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)}.$$

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$$