Contents / Probability / Foundations of Probability

Chapter 1

Foundations of Probability

Sample spaces and events, the Kolmogorov axioms and the rules derived from them, counting, conditional probability, independence, total probability and Bayes' theorem.

Introduction

Every other chapter in this subject rests on this one. A random variable is a function on a probability space, a distribution is an assignment of probabilities to its values, and an expectation is an average taken against those probabilities. The same is true one subject over: in the companion Statistics course an estimator is a random variable, a confidence interval is a statement about a probability, and a $p$ -value is a probability. None of those sentences means anything until "probability" has been given a precise definition, so that is what this chapter does.

The definition is surprisingly economical. Andrey Kolmogorov's 1933 formulation asks for only three things: probabilities are non-negative, the certain event has probability $1$ , and the probability of a union of non-overlapping events is the sum of their probabilities. That is the entire foundation. Everything else in this chapter — the complement rule, the addition rule, inclusion–exclusion, the law of total probability, Bayes' theorem — is derived, and this chapter derives them rather than asserting them. Where a rule needs a hypothesis, the proof is where you see the hypothesis being used, which is the only reliable way to remember that it is there.

Two ideas do more work than the rest. The first is conditional probability, which is not a formula to memorise but a definition: it says what it means to recompute a probability after learning something. The second is independence, which says what it means to learn nothing. Almost every modelling assumption you will make in later chapters — random sampling, independent errors, independent trials — is an independence assumption in disguise, and almost every catastrophic failure of a statistical model is an independence assumption that was false.

The chapter closes on Bayes' theorem and the base-rate effect, worked with real numbers on a medical test. The answer there is one that most readers, including most doctors in the studies that asked them, get badly wrong. It is worth arriving at it by proof rather than by intuition, which is the general argument for this chapter.

1.1Sample spaces, events, and the axioms

A probability model has three ingredients: a set of things that could happen, a collection of statements about what happened, and a rule assigning numbers to those statements. We take them in that order.

Definition 1.1 (Experiment, outcome, sample space). An experiment is any procedure whose result is not determined in advance. Each result it can produce is an outcome, and the set of all possible outcomes is the sample space, written $S$ (or $\Omega$ ).

The outcomes in $S$ must be mutually exclusive — exactly one of them occurs — and exhaustive: no other result is possible.

The two conditions are what make $S$ a usable bookkeeping device, and they are a modelling choice rather than a fact about the world. For a single roll of a die, $S = \{1,2,3,4,5,6\}$ . For two rolls, the outcomes are ordered pairs and $S = \{(i,j) : 1 \le i,j \le 6\}$ , which has $36$ elements. For "the number of emails arriving today", $S = \{0,1,2,\ldots\}$ is countably infinite. For "the time until a component fails", $S = [0,\infty)$ is uncountable, and that case is genuinely harder — the last part of this section says why.

Definition 1.2 (Event). An event is a subset $A \subseteq S$ . The event $A$ occurs when the outcome that actually happened is an element of $A$ .

An event containing exactly one outcome is an elementary or simple event. $S$ itself is the certain event and $\varnothing$ the impossible event.

Because events are sets, the logical operations you want to perform on statements are already available as set operations. This dictionary is worth learning once rather than re-deriving each time.

Notation (Events as sets). For events $A$ and $B$ in a sample space $S$ :

$A \cup B$ is " $A$ or $B$ " (inclusive: at least one occurs);
$A \cap B$ , often written $AB$ , is " $A$ and $B$ " (both occur);
$A^c$ , also written $\bar{A}$ or $A'$ , is "not $A$ " (the complement of $A$ in $S$ );
$A \setminus B = A \cap B^c$ is " $A$ but not $B$ ";
$A \subseteq B$ means " $A$ implies $B$ ": whenever $A$ occurs, so does $B$ ;
$A \cap B = \varnothing$ means $A$ and $B$ are mutually exclusive (disjoint): they cannot both occur.

De Morgan's laws transfer between them: $(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$ . In words, "not (A or B)" is "neither", and "not (A and B)" is "at least one fails".

Example 1.3 (Events from two dice). A red die and a blue die are rolled, so $S = \{(i,j) : 1 \le i, j \le 6\}$ with $|S| = 36$ . Let $A$ be "the sum is $7$ ", $B$ be "the red die shows $4$ ", and $C$ be "both dice show the same face". Write each as a set, and describe $A \cap B$ , $A \cap C$ and $B \cup C$ .

Solution. $A = \{(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)\}$ , so $|A| = 6$ .

$B = \{(4,1),(4,2),(4,3),(4,4),(4,5),(4,6)\}$ , so $|B| = 6$ .

$C = \{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)\}$ , so $|C| = 6$ .

$A \cap B = \{(4,3)\}$ : the sum is $7$ and the red die is $4$ , which pins the blue die to $3$ . One outcome.

$A \cap C = \varnothing$ : a double has an even sum, so it can never total $7$ . The events "sum is $7$ " and "doubles" are mutually exclusive.

$B \cup C$ contains the six outcomes of $B$ and the six of $C$ , but $(4,4)$ lies in both, so $|B \cup C| = 6 + 6 - 1 = 11$ . That correction is the addition rule in miniature, and it is proved below.□

Now the numbers. Kolmogorov's axioms say what a probability is by listing what it must satisfy, and nothing else. Note what is absent: no mention of frequencies, of symmetry, of degrees of belief. Those are interpretations, and the mathematics is the same under all of them.

Definition 1.4 (The Kolmogorov axioms). A probability measure on a sample space $S$ is a function $P$ assigning a real number $P(A)$ to each event $A$ , such that

(Non-negativity) $P(A) \ge 0$ for every event $A$ ;
(Normalisation) $P(S) = 1$ ;
(Countable additivity) if $A_1, A_2, A_3, \ldots$ are pairwise mutually exclusive — meaning $A_i \cap A_j = \varnothing$ whenever $i \neq j$ — then

P\!\left(\bigcup_{i=1}^{\infty} A_i\right) = \sum_{i=1}^{\infty} P(A_i).

The triple $(S, \mathcal{F}, P)$ , where $\mathcal{F}$ is the collection of events, is a probability space.

Three remarks on what the axioms do and do not say. First, the upper bound $P(A) \le 1$ is not an axiom: it is a theorem, proved below from the three axioms. Stating it as a fourth axiom is a common but redundant presentation. Second, axiom 3 requires the events to be pairwise disjoint; applied to overlapping events it is false, and the addition rule exists precisely to repair it. Third, additivity is stated for countably many events rather than finitely many, which is a genuine strengthening and is what makes limits behave.

Note (Why not every subset is an event). For a finite or countable $S$ you may take $\mathcal{F}$ to be all subsets of $S$ , and nothing goes wrong. For $S = [0,1]$ you cannot: there is no way to assign a length to every subset of the line while keeping countable additivity and translation invariance, a fact established by Vitali's construction of a non-measurable set. The fix is to restrict $\mathcal{F}$ to a $\sigma$ -algebra — a collection of subsets containing $S$ and closed under complements and countable unions — and to define $P$ only there. Every set you can describe in this course is in it. We will not mention $\mathcal{F}$ again, but it is the reason "event" is a technical term rather than a synonym for "subset".

The first consequences are immediate, and they show the machine working.

Proposition 1.5 (The impossible event and finite additivity). For any probability measure $P$ :

$P(\varnothing) = 0$ ;
if $A_1, \ldots, A_n$ are pairwise mutually exclusive, then $P(A_1 \cup \cdots \cup A_n) = P(A_1) + \cdots + P(A_n)$ .

Proof. (1) Take $A_i = \varnothing$ for every $i \ge 1$ . These are pairwise disjoint, since $\varnothing \cap \varnothing = \varnothing$ , and their union is $\varnothing$ . Countable additivity gives

P(\varnothing) = \sum_{i=1}^{\infty} P(\varnothing).

Write $c = P(\varnothing) \ge 0$ by non-negativity. If $c > 0$ the right-hand side diverges while the left is finite, a contradiction; so $c = 0$ .

(2) Given finitely many disjoint $A_1, \ldots, A_n$ , extend the list by setting $A_i = \varnothing$ for $i > n$ . The extended list is still pairwise disjoint and has the same union, so countable additivity applies and the tail contributes $\sum_{i>n} P(\varnothing) = 0$ by part (1).∎

So finite additivity is a consequence, not a separate assumption — and it needed $P(\varnothing) = 0$ , which in turn needed countable additivity. The axioms are more tightly interlocked than they look.

Proposition 1.6 (Complement rule). For any event $A$ , $\;P(A^c) = 1 - P(A)$ .

Proof. $A$ and $A^c$ are mutually exclusive, since no outcome is both in $A$ and outside it, and their union is $S$ . By finite additivity and normalisation,

P(A) + P(A^c) = P(A \cup A^c) = P(S) = 1.

Subtract $P(A)$ .∎

The complement rule is the single most useful computational trick in the chapter, because "at least one" is almost always harder to count than "none". Whenever a problem says at least one, compute the probability of none and subtract.

Proposition 1.7 (Monotonicity, and the upper bound). If $A \subseteq B$ then $P(A) \le P(B)$ , and moreover $P(B \setminus A) = P(B) - P(A)$ . Consequently $0 \le P(A) \le 1$ for every event $A$ .

Proof. Split $B$ along $A$ : since $A \subseteq B$ ,

B = A \cup (B \cap A^c),

and the two pieces are disjoint, because one lies inside $A$ and the other inside $A^c$ . Finite additivity gives $P(B) = P(A) + P(B \cap A^c)$ , which is the stated difference formula since $B \setminus A = B \cap A^c$ . Non-negativity makes $P(B \cap A^c) \ge 0$ , hence $P(B) \ge P(A)$ .

For the bound, every event satisfies $A \subseteq S$ , so $P(A) \le P(S) = 1$ ; and $P(A) \ge 0$ is axiom 1.∎

Remark. Monotonicity is the formal version of "a more demanding requirement is less likely". If every outcome that makes $A$ true also makes $B$ true, $A$ cannot be the more probable of the two. A probability estimate that violates this — the celebrated "Linda is a bank teller and a feminist is more likely than Linda is a bank teller" experiment of Tversky and Kahneman — is not merely implausible, it is inconsistent with the axioms.

Now the rule for events that do overlap. Additivity fails for them, and the proof shows exactly by how much.

Theorem 1.8 (Addition rule for two events). For any events $A$ and $B$ ,

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

Proof. Decompose $A \cup B$ into three pairwise disjoint pieces:

A \cup B = (A \cap B^c) \;\cup\; (A \cap B) \;\cup\; (A^c \cap B),

which are " $A$ only", "both", and " $B$ only". They are disjoint by construction, and every outcome in $A \cup B$ lies in exactly one of them. Finite additivity gives

P(A \cup B) = P(A \cap B^c) + P(A \cap B) + P(A^c \cap B).

Applying the same split to $A$ alone, $A = (A \cap B^c) \cup (A \cap B)$ with disjoint pieces, so $P(A \cap B^c) = P(A) - P(A \cap B)$ ; symmetrically $P(A^c \cap B) = P(B) - P(A \cap B)$ . Substituting,

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

∎

The subtraction is there because the outcomes in $A \cap B$ were counted once in $P(A)$ and again in $P(B)$ ; removing one copy leaves exactly one. When $A$ and $B$ are mutually exclusive, $P(A \cap B) = P(\varnothing) = 0$ and the correction vanishes, recovering additivity.

Corollary 1.9 (Boole's inequality). For any events $A_1, A_2, \ldots$ — disjoint or not —

P\!\left(\bigcup_i A_i\right) \le \sum_i P(A_i).

Proof. For two events, the addition rule gives $P(A \cup B) = P(A) + P(B) - P(A \cap B) \le P(A) + P(B)$ , since $P(A \cap B) \ge 0$ . Induction extends this to any finite union: if it holds for $n$ events, then $P(A_1 \cup \cdots \cup A_{n+1}) \le P(A_1 \cup \cdots \cup A_n) + P(A_{n+1}) \le \sum_{i=1}^{n+1} P(A_i)$ .

For a countable union, disjointify: set $B_1 = A_1$ and $B_i = A_i \setminus (A_1 \cup \cdots \cup A_{i-1})$ . The $B_i$ are pairwise disjoint with the same union as the $A_i$ , and $B_i \subseteq A_i$ , so monotonicity gives $P(B_i) \le P(A_i)$ . Countable additivity then yields $P(\bigcup_i A_i) = \sum_i P(B_i) \le \sum_i P(A_i)$ .∎

Boole's inequality is crude — it throws away every overlap — but it needs no assumptions whatsoever, which is what makes it usable when nothing is known about the dependence between the events. It reappears as the first step of the Borel-Cantelli lemmas, and in the companion Statistics course it is the whole of the Bonferroni correction for multiple testing.

Theorem 1.10 (Inclusion–exclusion for three events). For any events $A$ , $B$ , $C$ ,

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 addition rule to $(A \cup B)$ and $C$ :

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

Expand the first term by the addition rule again: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ .

For the last term, distributivity of intersection over union gives $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ , and a third use of the addition rule gives

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

because $(A \cap C) \cap (B \cap C) = A \cap B \cap C$ . Substituting both expansions and collecting signs gives the statement.∎

Intuition. Count everyone once. Adding $P(A)+P(B)+P(C)$ counts anybody in two of the sets twice and anybody in all three of them three times. Subtracting the three pairwise overlaps fixes the doubles, but it also strips the triple-overlap people three times, leaving them counted $3 - 3 = 0$ times — so the final $+P(A\cap B\cap C)$ puts them back. The alternating signs are not a mnemonic; they are the bookkeeping of over- and under-correction.

Example 1.11 (A survey with three overlapping groups). In a survey of students, $60\%$ take statistics, $45\%$ take economics, and $30\%$ take computing. Of the overlaps, $25\%$ take statistics and economics, $15\%$ take statistics and computing, $12\%$ take economics and computing, and $8\%$ take all three. What fraction take at least one of the three, and what fraction take none?

Solution. Write $A$ , $B$ , $C$ for the three subjects. Inclusion–exclusion gives

P(A \cup B \cup C) = 0.60 + 0.45 + 0.30 - 0.25 - 0.15 - 0.12 + 0.08 = 0.91.

So $91\%$ take at least one. By the complement rule, $P(\text{none}) = 1 - 0.91 = 0.09$ , or $9\%$ .

Sanity check by Boole's inequality: the sum $0.60 + 0.45 + 0.30 = 1.35$ exceeds $1$ , so the bound is vacuous here but not violated, and the true value $0.91$ must lie at or below it. A second check: the answer must be at least $\max(0.60, 0.45, 0.30) = 0.60$ by monotonicity, since $A \subseteq A \cup B \cup C$ . Both hold.□

Finally, the special case that most introductory problems live in. It is a model, not a law, and the axioms are what justify it.

Definition 1.12 (The equally likely model). A sample space $S$ with finitely many outcomes is equiprobable when every elementary event has the same probability.

Proposition 1.13 (Counting formula for equiprobable spaces). If $S$ is equiprobable with $|S| = n$ outcomes, then for every event $A$ ,

P(A) = \frac{|A|}{|S|}.

Proof. Let $p$ be the common probability of each elementary event $\{s\}$ . The $n$ elementary events are pairwise disjoint with union $S$ , so finite additivity and normalisation give $np = P(S) = 1$ , hence $p = 1/n$ . Now any event $A$ is the disjoint union of its $|A|$ elementary events, so finite additivity gives $P(A) = |A| \cdot p = |A|/n$ .∎

This is why counting matters, and it is the whole content of the next section: once the model is equiprobable, computing a probability means computing two cardinalities.

Pitfall. The formula $P(A) = |A|/|S|$ is a theorem about equiprobable spaces, not a definition of probability. Two routine ways to misuse it: applying it to a sample space whose outcomes are not equally likely, and choosing a sample space that quietly destroys the symmetry. Rolling two dice and taking $S = \{2,3,\ldots,12\}$ for the sum gives eleven outcomes, but $P(7) = 6/36$ and $P(2) = 1/36$ are not equal, so $P(\text{sum}=7) \ne 1/11$ . Use the $36$ ordered pairs, where the symmetry of the physical setup really does make the outcomes equiprobable, and count within that.

Exercises for §1.1 →

1.2Counting outcomes

Counting is not a separate subject here; it is how probabilities in equiprobable spaces get computed. The results below are the minimum needed for probability, and each is a consequence of one principle.

Theorem 1.14 (Multiplication principle). If a procedure consists of $k$ stages, where stage $1$ can be completed in $n_1$ ways and, for each way of completing stages $1$ through $i-1$ , stage $i$ can be completed in $n_i$ ways, then the whole procedure can be completed in

n_1 \times n_2 \times \cdots \times n_k

ways.

Proof. Induct on $k$ . For $k=1$ the claim is the hypothesis. Suppose it holds for $k-1$ stages, so there are $N = n_1\cdots n_{k-1}$ ways to complete them. Each of those $N$ partial outcomes extends to exactly $n_k$ full outcomes, and two full outcomes built on different partial outcomes are different. So the full outcomes are partitioned into $N$ groups of size $n_k$ , giving $N \cdot n_k = n_1 \cdots n_k$ in total.∎

The phrase "for each way of completing the earlier stages" matters: the number of options at stage $i$ must not depend on which earlier choices were made, though which options they are may. Dealing cards is the standard case — after any first card there are always $51$ possibilities for the second, even though the identity of those $51$ changes.

Example 1.15 (Licence plates). A plate is three letters from a $26$ -letter alphabet followed by four digits. How many plates are there if repetition is allowed, and how many if all seven characters must be distinct within their groups (no repeated letter, no repeated digit)?

Solution. With repetition: $26^3 \times 10^4 = 17{,}576 \times 10{,}000 = 175{,}760{,}000$ .

Without repetition: the letters contribute $26 \times 25 \times 24 = 15{,}600$ and the digits $10 \times 9 \times 8 \times 7 = 5040$ , giving $15{,}600 \times 5040 = 78{,}624{,}000$ .

Sanity check: the second count must be smaller, since every distinct-character plate is also a plate — and $78{,}624{,}000 < 175{,}760{,}000$ . The ratio is about $0.447$ , so fewer than half of all plates have all-distinct characters.□

Definition 1.16 (Permutation). A permutation of $k$ objects from a set of $n$ distinct objects is an ordered selection of $k$ of them, without repetition. The number of such permutations is written $P(n,k)$ .

Notation. The symbol $P$ is unfortunately overloaded: $P(A)$ is a probability and $P(n,k)$ a count. They are told apart by their arguments — a probability takes an event, a permutation count takes two integers. Some books write $_nP_k$ or $(n)_k$ to avoid the clash.

Proposition 1.17 (Permutation count). For $0 \le k \le n$ ,

P(n,k) = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}.

In particular $P(n,n) = n!$ : there are $n!$ orderings of $n$ distinct objects.

Proof. Build the ordered selection one position at a time. Position $1$ can be filled in $n$ ways; whichever object was used, position $2$ can be filled in $n-1$ ways, and in general position $i$ in $n-i+1$ ways. The count at each stage does not depend on the earlier choices, so the multiplication principle applies and gives the product $n(n-1)\cdots(n-k+1)$ , which has $k$ factors. Multiplying and dividing by $(n-k)! = (n-k)(n-k-1)\cdots 1$ turns the product into $n!/(n-k)!$ .∎

Definition 1.18 (Combination). A combination of $k$ objects from $n$ distinct objects is an unordered selection of $k$ of them, without repetition — that is, a $k$ -element subset. The number of them is the binomial coefficient $\binom{n}{k}$ , read " $n$ choose $k$ ".

Theorem 1.19 (Combination count). For $0 \le k \le n$ ,

\binom{n}{k} = \frac{n!}{k!\,(n-k)!}.

Proof. Count the ordered selections of $k$ objects in two ways. Directly, there are $P(n,k) = n!/(n-k)!$ of them.

Alternatively, build an ordered selection in two stages: first choose which $k$ objects to use, in $\binom{n}{k}$ ways by definition, then choose an order for them, in $k!$ ways by the permutation count with $k=n$ . Every ordered selection arises exactly once this way, so by the multiplication principle there are $\binom{n}{k}\cdot k!$ of them.

Equating the two counts, $\binom{n}{k} \cdot k! = n!/(n-k)!$ , and dividing by $k!$ gives the formula.∎

That argument — count one set two ways, equate — is called double counting, and it proves the next two facts more cleanly than algebra does.

Proposition 1.20 (Symmetry and Pascal's rule). For $0 \le k \le n$ ,

\binom{n}{k} = \binom{n}{n-k}, \qquad \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad (1 \le k \le n-1).

Proof. Symmetry: choosing the $k$ objects to include is the same act as choosing the $n-k$ objects to leave out, so the two collections of subsets are in one-to-one correspondence and have the same size.

Pascal's rule. Fix one particular object $x$ . Every $k$ -subset either contains $x$ or does not. Those containing $x$ are determined by the remaining $k-1$ elements drawn from the other $n-1$ objects, giving $\binom{n-1}{k-1}$ ; those not containing $x$ are $k$ -subsets of the other $n-1$ objects, giving $\binom{n-1}{k}$ . The two cases are exclusive and exhaustive, so the counts add.∎

Method 1.21 (Choosing the right count). Before computing anything, answer two questions about the selection.

Does order matter? If rearranging the chosen items gives a genuinely different outcome — offices, rankings, sequences, positions — order matters. If not — committees, hands of cards, subsets — it does not.
Is repetition allowed? Drawing with replacement, or filling slots from an unlimited supply, allows repetition; dealing from a deck does not.

Then: ordered with repetition gives $n^k$ ; ordered without repetition gives $P(n,k) = n!/(n-k)!$ ; unordered without repetition gives $\binom{n}{k}$ . (Unordered with repetition is $\binom{n+k-1}{k}$ , which probability needs only rarely.)

Use the same convention on top and bottom. In $P(A) = |A|/|S|$ , both cardinalities must count the same kind of object. Counting $|S|$ as ordered hands and $|A|$ as unordered hands is the most common arithmetic disaster in this chapter.

Example 1.22 (Ordered versus unordered from one pool). A club of $10$ people must (a) elect a president, a vice-president and a treasurer, all distinct offices, and (b) separately pick a $3$ -person social committee with no offices. Count each.

Solution. (a) Order matters, because being president is not the same job as being treasurer. This is a permutation:

P(10,3) = \frac{10!}{7!} = 10 \times 9 \times 8 = 720.

(b) Order does not matter. This is a combination:

\binom{10}{3} = \frac{10!}{3!\,7!} = \frac{720}{6} = 120.

Sanity check: the only difference between the two questions is whether the $3! = 6$ orderings of a chosen trio count as distinct, and indeed $720/6 = 120$ , exactly as the proof of the combination count predicts.□

Example 1.23 (Exactly two aces). Five cards are dealt from a well-shuffled standard deck. Find the probability that the hand contains exactly two aces.

Solution. Take $S$ to be the set of all $5$ -card hands, unordered. Because the deck is well shuffled, all hands are equally likely, so the counting formula applies with

|S| = \binom{52}{5} = 2{,}598{,}960.

A hand with exactly two aces is built in two stages: choose which $2$ of the $4$ aces appear, then choose the other $3$ cards from the $48$ non-aces. By the multiplication principle,

|A| = \binom{4}{2}\binom{48}{3} = 6 \times 17{,}296 = 103{,}776.

Therefore

P(A) = \frac{103{,}776}{2{,}598{,}960} \approx 0.0399.

Sanity check: both counts are unordered, as the recipe demands. Note that "exactly two" required choosing the remaining three cards from the non-aces; drawing them from all $50$ remaining cards would have counted hands with three or four aces as well, and would also have double counted.□

Example 1.24 (The birthday problem). In a room of $23$ people with birthdays independently uniform over $365$ days, what is the probability that at least two share a birthday?

Solution. "At least one shared birthday" is awkward to count directly — the shares can occur in many patterns — so use the complement rule and count the opposite: all $23$ birthdays distinct.

The sample space of birthday lists has $|S| = 365^{23}$ equally likely elements, by the multiplication principle with repetition allowed. Lists with all birthdays distinct are ordered selections without repetition, so there are $P(365, 23) = 365 \times 364 \times \cdots \times 343$ of them. Hence

P(\text{all distinct}) = \frac{365 \times 364 \times \cdots \times 343}{365^{23}} \approx 0.4927,

and by the complement rule

P(\text{at least one match}) = 1 - 0.4927 \approx 0.5073.

Sanity check on the surprise: the relevant count is not people but pairs, and $23$ people form $\binom{23}{2} = 253$ pairs, each matching with probability $1/365$ . Boole's inequality caps the answer at $253/365 \approx 0.693$ , and the true value sits comfortably below it. The intuition that fails here compares $23$ with $365$ ; the right comparison is $253$ with $365$ .□

Pitfall. Counting the same outcome twice is far more common than missing one. If you compute "the number of $5$ -card hands with at least one ace" as $4 \times \binom{51}{4}$ — pick an ace, then any four other cards — you have counted a two-ace hand twice, once for each ace that could have been "the" chosen one. The safe routes are the complement, $\binom{52}{5} - \binom{48}{5}$ , or a sum over disjoint cases by the exact number of aces.

Exercises for §1.2 →

1.3Conditional probability

Probabilities are not properties of events alone; they are properties of events relative to a state of information. Learning something changes them. The card you are about to draw is a heart with probability $1/4$ , but if you are told it is red, the probability becomes $1/2$ — nothing about the card changed, only what you know.

Conditioning formalises that. Learning that $B$ occurred means every outcome outside $B$ is now impossible, so $B$ becomes the new sample space. Probabilities must be recomputed inside it, and they must be rescaled so that the new sample space still has total probability $1$ . Dividing by $P(B)$ is exactly that rescaling.

Definition 1.25 (Conditional probability). Let $A$ and $B$ be events with $P(B) > 0$ . The conditional probability of $A$ given $B$ is

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

It is undefined when $P(B) = 0$ .

Two features of the definition repay attention. The numerator is $P(A \cap B)$ , not $P(A)$ : only the part of $A$ that survives inside $B$ counts. And the requirement $P(B) > 0$ is not a technicality to be waved past — you cannot condition on something that never happens, because the rescaling would divide by zero.

It is worth checking that this construction produces something that is itself a probability. If it did not, every theorem proved so far would have to be re-derived for conditional probabilities, and none of them would be safe to use.

Theorem 1.26 (Conditioning yields a probability measure). Fix an event $B$ with $P(B) > 0$ and define $Q(A) = P(A \mid B)$ for every event $A$ . Then $Q$ satisfies the Kolmogorov axioms on $S$ .

Proof. Non-negativity. $Q(A) = P(A \cap B)/P(B)$ is a quotient of a non-negative number by a strictly positive one, hence $Q(A) \ge 0$ .

Normalisation. $Q(S) = P(S \cap B)/P(B) = P(B)/P(B) = 1$ .

Countable additivity. Let $A_1, A_2, \ldots$ be pairwise disjoint. Then the sets $A_i \cap B$ are also pairwise disjoint, since $(A_i \cap B) \cap (A_j \cap B) \subseteq A_i \cap A_j = \varnothing$ , and $\left(\bigcup_i A_i\right) \cap B = \bigcup_i (A_i \cap B)$ by distributivity. So

Q\!\left(\bigcup_i A_i\right) = \frac{P\!\left(\bigcup_i (A_i \cap B)\right)}{P(B)} = \frac{\sum_i P(A_i \cap B)}{P(B)} = \sum_i Q(A_i),

using countable additivity of $P$ in the middle step.∎

Corollary 1.27 (Rules transfer to conditional probabilities). For any event $B$ with $P(B) > 0$ : $P(A^c \mid B) = 1 - P(A \mid B)$ , and

P(A_1 \cup A_2 \mid B) = P(A_1 \mid B) + P(A_2 \mid B) - P(A_1 \cap A_2 \mid B).

Proof. Both are the complement rule and the addition rule applied to the probability measure $Q(\cdot) = P(\cdot \mid B)$ , which is legitimate by Theorem Conditioning yields a probability measure: those rules were proved for an arbitrary probability measure, and $Q$ is one.∎

Pitfall. The transfer works on the event in front of the bar, never behind it. $P(A \mid B^c) = 1 - P(A \mid B)$ is false in general, and it is a favourite trap: complementing the condition throws you into a different sample space entirely, where the numerator has no relation to the one you started with. For the medical test later in this chapter, $P(+ \mid D) = 0.99$ while $P(+ \mid D^c) = 0.01$ , and those two happen to sum to $1$ only by coincidence of the numbers chosen; with sensitivity $0.99$ and false-positive rate $0.05$ they would sum to $1.04$ .

Example 1.28 (Conditioning inside a die roll). Two fair dice are rolled. Given that the first die shows $5$ , what is the probability that the total is at least $10$ ? Compare with the unconditional probability.

Solution. Let $A$ be "total at least $10$ " and $B$ be "first die is $5$ ".

Unconditionally, $A = \{(4,6),(5,5),(6,4),(5,6),(6,5),(6,6)\}$ , so $P(A) = 6/36 = 1/6 \approx 0.1667$ .

Now condition. $B$ has $6$ outcomes, so $P(B) = 6/36 = 1/6$ . The intersection $A \cap B = \{(5,5),(5,6)\}$ has $2$ outcomes, so $P(A \cap B) = 2/36 = 1/18$ . By the definition,

P(A \mid B) = \frac{1/18}{1/6} = \frac{6}{18} = \frac13 \approx 0.3333.

The same answer comes from the shrunken sample space directly: inside $B$ there are $6$ equally likely outcomes and $2$ of them qualify, giving $2/6$ . Knowing the first die is high doubled the probability, which is what it means for these events to be dependent.□

Rearranging the definition turns it into a rule for building joint probabilities out of sequential ones, which is how almost every multi-stage problem is actually computed.

Proposition 1.29 (Multiplication rule). If $P(A) > 0$ then $P(A \cap B) = P(A)\,P(B \mid A)$ , and symmetrically, if $P(B) > 0$ then $P(A \cap B) = P(B)\,P(A \mid B)$ .

Proof. Multiply both sides of the definition $P(B \mid A) = P(A \cap B)/P(A)$ by $P(A)$ , which is legitimate because $P(A) > 0$ . The second form is the same computation with the roles exchanged.∎

Theorem 1.30 (Chain rule). If $P(A_1 \cap \cdots \cap A_{n-1}) > 0$ , then

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. Induct on $n$ . The case $n = 2$ is the multiplication rule. Assume the identity for $n-1$ events and write $E = A_1 \cap \cdots \cap A_{n-1}$ , so that $P(E) > 0$ by hypothesis and the multiplication rule applies to $E$ and $A_n$ :

P(E \cap A_n) = P(E)\,P(A_n \mid E).

Every conditioning event appearing in the inductive hypothesis contains $E$ , hence has positive probability by monotonicity, so the hypothesis expands $P(E)$ into the first $n-1$ factors. Substituting gives the result.∎

Example 1.31 (Three hearts in a row). Three cards are dealt from a standard deck without replacement. Find the probability that all three are hearts.

Solution. Let $A_i$ be "the $i$ -th card is a heart". The draws are dependent: removing a heart changes what remains.

$P(A_1) = 13/52$ . Given the first card was a heart, $12$ hearts remain among $51$ cards, so $P(A_2 \mid A_1) = 12/51$ . Given the first two were hearts, $P(A_3 \mid A_1 \cap A_2) = 11/50$ . By the chain rule,

P(A_1 \cap A_2 \cap A_3) = \frac{13}{52}\cdot\frac{12}{51}\cdot\frac{11}{50} = \frac{1716}{132600} \approx 0.0129.

Sanity check two ways. With replacement the draws would be independent and give $(1/4)^3 = 0.0156$ ; removing hearts makes later hearts less likely, and indeed $0.0129 < 0.0156$ . Alternatively count unordered hands: $\binom{13}{3}/\binom{52}{3} = 286/22100 \approx 0.0129$ , the same number, as it must be — ordering conventions cancel when used consistently on top and bottom.□

Intuition. Conditional probability is narrowing the world. $P(\text{rain} \mid \text{cloudy})$ asks: among cloudy days only, what fraction had rain? Sunny days are not counted as evidence against rain — they are not counted at all. That is also why $P(A \mid B)$ and $P(B \mid A)$ are different questions: one restricts to cloudy days and looks for rain, the other restricts to rainy days and looks for cloud. The second is nearly $1$ ; the first is not.

Pitfall. Reversing the bar is the most consequential error in applied statistics, and it has a name in the courtroom: the prosecutor's fallacy. The probability that a randomly chosen innocent person matches the forensic evidence, $P(\text{match} \mid \text{innocent})$ , may be one in a million. The probability that a person is innocent given a match, $P(\text{innocent} \mid \text{match})$ , can still be large, because the match probability must be weighed against how many people were searched. Converting between the two is exactly what Bayes' theorem does, and it cannot be done without the prior.

Exercises for §1.3 →

1.4Independence

Dependence was the interesting case above: conditioning changed the number. Independence is the boundary case where it does not — where learning $B$ leaves the probability of $A$ exactly where it was.

Definition 1.32 (Independence of two events). Events $A$ and $B$ are independent when

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

Otherwise they are dependent.

The product form is the right definition even though the conditional form is the better intuition, for two reasons: it is symmetric in $A$ and $B$ , so "independent" needs no ordering, and it remains meaningful when $P(B) = 0$ , where conditioning is undefined. The two agree whenever both make sense.

Proposition 1.33 (Conditional characterisation). If $P(B) > 0$ , then $A$ and $B$ are independent if and only if $P(A \mid B) = P(A)$ .

Proof. Suppose $A$ and $B$ are independent. Then

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

Conversely, if $P(A \mid B) = P(A)$ , multiply through by $P(B) > 0$ and use the multiplication rule: $P(A \cap B) = P(B)P(A \mid B) = P(A)P(B)$ .∎

Proposition 1.34 (Independence passes to complements). If $A$ and $B$ are independent, so are $A$ and $B^c$ , $A^c$ and $B$ , and $A^c$ and $B^c$ .

Proof. Split $A$ along $B$ : $A = (A \cap B) \cup (A \cap B^c)$ , a disjoint union, so

P(A \cap B^c) = P(A) - P(A \cap B) = P(A) - P(A)P(B) = P(A)\big(1 - P(B)\big) = P(A)P(B^c),

using independence in the second step and the complement rule in the last. So $A$ and $B^c$ are independent. The case of $A^c$ and $B$ follows by symmetry of the definition, and applying the first result to the independent pair $(A^c, B)$ gives $A^c$ and $B^c$ .∎

This is the formal licence for a habit you will use constantly: if components fail independently, then they also survive independently, so $P(\text{all survive}) = \prod_i \big(1 - p_i\big)$ .

Now the confusion the chapter must pre-empt. "Mutually exclusive" and "independent" are opposite ideas that students routinely fuse, and they are not merely different — for events that can actually happen, they are incompatible.

Theorem 1.35 (Mutually exclusive and independent are incompatible). Let $A$ and $B$ be mutually exclusive events with $P(A) > 0$ and $P(B) > 0$ . Then $A$ and $B$ are not independent.

Proof. Since $A \cap B = \varnothing$ , we have $P(A \cap B) = P(\varnothing) = 0$ . Independence would require $P(A \cap B) = P(A)P(B)$ , and $P(A)P(B) > 0$ because both factors are strictly positive. So $0 = P(A)P(B) > 0$ , a contradiction.∎

Intuition. Mutual exclusivity is the strongest possible dependence, not a form of independence. If $A$ and $B$ cannot both occur, then learning that $A$ happened tells you something decisive about $B$ : it did not happen. Formally $P(B \mid A) = 0 \ne P(B)$ . Independence means learning $A$ tells you nothing; exclusivity means it tells you everything.

For more than two events, the product rule must hold for every subcollection, not merely for pairs — and the difference is real.

Definition 1.36 (Mutual independence). Events $A_1, \ldots, A_n$ are mutually independent when for every subset of indices $I \subseteq \{1, \ldots, n\}$ with $|I| \ge 2$ ,

P\!\left(\bigcap_{i \in I} A_i\right) = \prod_{i \in I} P(A_i).

They are pairwise independent when this holds for all $I$ with $|I| = 2$ .

Mutual independence implies pairwise independence by definition. The converse fails, and the counterexample is small enough to check by hand.

Example 1.37 (Pairwise but not mutually independent). Toss two fair coins. Let $A$ = "the first coin is heads", $B$ = "the second coin is heads", and $C$ = "the two coins match". Show that $A, B, C$ are pairwise independent but not mutually independent.

Solution. The sample space $\{HH, HT, TH, TT\}$ is equiprobable, each outcome having probability $1/4$ . Then $A = \{HH, HT\}$ , $B = \{HH, TH\}$ and $C = \{HH, TT\}$ , so $P(A) = P(B) = P(C) = 1/2$ .

Each pairwise intersection is the single outcome $HH$ :

P(A \cap B) = P(A \cap C) = P(B \cap C) = \tfrac14 = \tfrac12 \cdot \tfrac12,

so all three pairs are independent.

The triple intersection is also $\{HH\}$ , so $P(A \cap B \cap C) = 1/4$ , whereas $P(A)P(B)P(C) = 1/8$ . Since $1/4 \ne 1/8$ , the three events are not mutually independent.

The failure is intelligible: any two of these events determine the third. Knowing the first coin is heads and that the coins match forces the second coin to be heads, so $P(B \mid A \cap C) = 1 \ne P(B)$ . Independence survives being checked two at a time and dies at three.□

Definition 1.38 (Conditional independence). Events $A$ and $B$ are conditionally independent given $C$ , where $P(C) > 0$ , when

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

Remark. Conditional independence neither implies nor is implied by ordinary independence. Two tests of the same patient are conditionally independent given disease status — the errors are made by the instrument, not by the patient — yet they are strongly dependent unconditionally, because a first positive result raises the chance of disease and therefore the chance of a second positive. That is precisely the structure that makes a repeated test informative, and it is used at the end of this chapter.

Example 1.39 (A redundant system). A system has three components that fail independently, each working with probability $0.9$ . Find the probability the system works if the components are wired in series (all must work) and if they are wired in parallel (at least one must work).

Solution. Let $W_i$ be "component $i$ works", with $P(W_i) = 0.9$ and the $W_i$ mutually independent.

Series. The system works exactly when $W_1 \cap W_2 \cap W_3$ occurs, so by mutual independence

P(\text{works}) = 0.9^3 = 0.729.

Parallel. "At least one works" is awkward directly, so take the complement: the system fails only if all three fail. By Proposition Independence passes to complements, the events $W_i^c$ are mutually independent with $P(W_i^c) = 0.1$ , so

P(\text{all fail}) = 0.1^3 = 0.001, \qquad P(\text{works}) = 1 - 0.001 = 0.999.

Sanity check: redundancy should help and duplication should hurt, and indeed $0.729 < 0.9 < 0.999$ . Note how much both answers rest on independence — if all three components share a power supply, the failures are positively dependent and $0.999$ is an overstatement, possibly a large one.□

Pitfall. Independence is an assumption to be justified, never a default. It is justified by the physical setup — separate coin tosses, separately sampled individuals, a randomised assignment — and not by the events merely feeling unrelated. Multiplying probabilities of dependent events is the error behind the Sally Clark case, in which two infant deaths in one family were treated as independent, producing a "one in $73$ million" figure that a shared genetic or environmental cause makes meaningless.

Exercises for §1.4 →

1.5The law of total probability

Some probabilities are hard to compute directly but easy to compute within each of several scenarios. A factory's overall defect rate is awkward; the defect rate of each machine is on a datasheet. The technique is to break the sample space into cases, work inside each, and recombine — and the recombination is a weighted average, with the weights being how likely each case is.

Definition 1.40 (Partition). Events $B_1, B_2, \ldots$ form a partition of the sample space $S$ when they are pairwise mutually exclusive, $B_i \cap B_j = \varnothing$ for $i \ne j$ ; collectively exhaustive, $\bigcup_i B_i = S$ ; and each has $P(B_i) > 0$ .

All three conditions earn their place. Exclusivity is what lets the pieces be added; exhaustiveness is what stops probability leaking out of the cases; positivity is what makes each conditional probability defined. The simplest partition is $\{B, B^c\}$ for any $B$ with $0 < P(B) < 1$ , and it is the one used most often.

Theorem 1.41 (Law of total probability). If $B_1, B_2, \ldots$ is a partition of $S$ , then for every event $A$ ,

P(A) = \sum_i P(A \cap B_i) = \sum_i P(A \mid B_i)\,P(B_i).

Proof. Because the $B_i$ cover $S$ , intersecting with $A$ gives

A = A \cap S = A \cap \bigcup_i B_i = \bigcup_i (A \cap B_i),

using distributivity. The pieces are pairwise disjoint, since $(A \cap B_i) \cap (A \cap B_j) \subseteq B_i \cap B_j = \varnothing$ for $i \ne j$ . Countable additivity therefore gives $P(A) = \sum_i P(A \cap B_i)$ , which is the first equality.

For the second, each $B_i$ has $P(B_i) > 0$ by the definition of a partition, so the multiplication rule applies term by term: $P(A \cap B_i) = P(A \mid B_i)P(B_i)$ .∎

Intuition. To find the overall chance of $A$ , split the world into non-overlapping cases that cover everything, find the chance of $A$ inside each case, then blend those numbers by how likely each case is. It is exactly a course grade computed as a weighted average of homework, midterm and final — and as there, the weights $P(B_i)$ must sum to $1$ , which is what "partition" guarantees.

Corollary 1.42 (Weighted-average bounds). With $B_1, \ldots, B_n$ a finite partition, $P(A)$ lies between $\min_i P(A \mid B_i)$ and $\max_i P(A \mid B_i)$ .

Proof. Write $m = \min_i P(A \mid B_i)$ and $M = \max_i P(A \mid B_i)$ . Since every weight satisfies $P(B_i) > 0$ and $\sum_i P(B_i) = P(S) = 1$ by finite additivity,

P(A) = \sum_i P(A \mid B_i)P(B_i) \le \sum_i M\,P(B_i) = M,

and the same argument with $m$ gives the lower bound.∎

That corollary is the free sanity check on every total-probability computation: an answer outside the range of the conditional rates is arithmetic error, not a subtle effect.

Example 1.43 (Two machines, one defect rate). A factory runs two machines. Machine $A$ makes $60\%$ of the parts with a $3\%$ defect rate; machine $B$ makes the other $40\%$ with a $5\%$ defect rate. What fraction of all parts are defective?

Solution. Every part comes from exactly one machine, so $\{A, B\}$ partitions the sample space, with $P(A) = 0.6$ , $P(B) = 0.4$ and $0.6 + 0.4 = 1$ as required. The conditional defect rates are $P(D \mid A) = 0.03$ and $P(D \mid B) = 0.05$ .

By the law of total probability,

P(D) = P(D \mid A)P(A) + P(D \mid B)P(B) = 0.03 \times 0.6 + 0.05 \times 0.4 = 0.018 + 0.020 = 0.038.

So $3.8\%$ of parts are defective.

Sanity check via Corollary Weighted-average bounds: the answer must lie in $[0.03, 0.05]$ , and it does, sitting nearer $0.03$ because machine $A$ carries the larger weight.□

Example 1.44 (Drawing from a randomly chosen urn). Urn I holds $3$ red and $7$ white balls; urn II holds $6$ red and $4$ white. A fair coin selects the urn, and one ball is drawn from it. Find the probability the ball is red.

Solution. Let $U_1, U_2$ be the events "urn I chosen", "urn II chosen". They partition the sample space with $P(U_1) = P(U_2) = 0.5$ , and $P(R \mid U_1) = 3/10 = 0.3$ , $P(R \mid U_2) = 6/10 = 0.6$ .

P(R) = 0.3 \times 0.5 + 0.6 \times 0.5 = 0.15 + 0.30 = 0.45.

Sanity check: with equal weights the answer is the plain average of $0.3$ and $0.6$ , namely $0.45$ , and it lies between them. Note that pooling the urns into one bag of $20$ balls would give $9/20 = 0.45$ too — but only because the two urns hold equally many balls and the coin is fair. Change the urn sizes and the pooled calculation breaks while the law of total probability does not.□

Pitfall. The cases must partition the sample space, not merely be a list of interesting possibilities. Two failures recur. If the cases overlap, the shared outcomes are counted twice and the total can exceed $1$ . If they miss something — "the customer is a student, or a pensioner" leaves out everyone else — the weights sum to less than $1$ and the answer is silently too small. Before summing, check that the weights add to exactly $1$ ; it costs one line and catches both errors.

Exercises for §1.5 →

1.6Bayes' theorem and base rates

Conditional probabilities come in pairs pointing opposite ways, and the one you can measure is usually not the one you want. A laboratory can measure $P(+ \mid D)$ : take people known to have the disease and see how often the test fires. A patient holding a positive result wants $P(D \mid +)$ . Bayes' theorem converts between the two, and the conversion requires one extra ingredient — the prevalence — which is exactly the ingredient intuition leaves out.

Theorem 1.45 (Bayes' theorem). If $P(A) > 0$ and $P(B) > 0$ , then

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

Proof. The multiplication rule computes $P(A \cap B)$ in two ways, both legitimate because both conditioning events have positive probability:

P(A \cap B) = P(A \mid B)P(B) \qquad\text{and}\qquad P(A \cap B) = P(B \mid A)P(A).

Equate the right-hand sides and divide by $P(A) > 0$ .∎

Corollary 1.46 (Bayes' theorem with a partition). If $B_1, B_2, \ldots$ is a partition of $S$ and $P(A) > 0$ , then for each $j$ ,

P(B_j \mid A) = \frac{P(A \mid B_j)P(B_j)}{\sum_i P(A \mid B_i)P(B_i)}.

Proof. Apply Bayes' theorem to $B_j$ and $A$ , then replace the denominator $P(A)$ by its expansion from the law of total probability, which applies because the $B_i$ form a partition.∎

So Bayes' theorem is two lines from the definition of conditional probability, and its denominator is the law of total probability. There is nothing else in it.

Notation (Prior, likelihood, posterior). In $P(B \mid A) = P(A \mid B)P(B)/P(A)$ , read $B$ as a hypothesis and $A$ as data:

$P(B)$ is the prior — what you believed before seeing the data;
$P(A \mid B)$ is the likelihood — how probable the data would be if the hypothesis held;
$P(A)$ is the evidence or marginal likelihood, computed by total probability;
$P(B \mid A)$ is the posterior — the updated belief.

The whole formula says: posterior is proportional to likelihood times prior.

The next figure lays out the computation we are about to do. A probability tree makes the two routes to a positive result visible, and the base-rate effect is the observation that the lower branch carries more probability than the upper one.

Figure 1.47. The two routes to a positive test, with prevalence

0.001

, sensitivity

0.99

and specificity

0.99

. Multiplying along each path gives the leaf probability. The false-positive leaf,

0.00999

, is more than ten times the true-positive leaf,

0.00099

— which is the whole of the base-rate effect.

Example 1.48 (A rare disease and an accurate test). A disease affects $1$ in $1000$ people. A screening test has sensitivity $P(+ \mid D) = 0.99$ and specificity $P(- \mid D^c) = 0.99$ , so its false-positive rate is $P(+ \mid D^c) = 0.01$ . A randomly chosen person tests positive. What is the probability they have the disease?

Solution. Write $D$ for "has the disease". The prior is $P(D) = 0.001$ , so $P(D^c) = 0.999$ by the complement rule. The events $\{D, D^c\}$ partition the sample space, both having positive probability, so the law of total probability gives the evidence:

P(+) = P(+ \mid D)P(D) + P(+ \mid D^c)P(D^c) = 0.99 \times 0.001 + 0.01 \times 0.999,

that is $P(+) = 0.00099 + 0.00999 = 0.01098$ . Now Bayes' theorem:

P(D \mid +) = \frac{P(+ \mid D)P(D)}{P(+)} = \frac{0.00099}{0.01098} \approx 0.0902.

About $9\%$ . Roughly nine out of ten positive results from this screen are false alarms, despite a test that is right $99\%$ of the time in both directions.

Sanity check by counting people. Among $100{,}000$ screened, about $100$ have the disease and $99$ of them test positive; about $99{,}900$ do not, and $1\%$ of them — $999$ people — test positive anyway. Of the $99 + 999 = 1098$ positives, $99$ are genuine, and $99/1098 \approx 0.0902$ , matching. The two pieces also sum to the denominator: $0.00099 + 0.00999 = 0.01098$ .□

The number people guess is usually close to $99\%$ , and the gap between $99\%$ and $9\%$ is the base rate doing its work. The reason is visible in the tree: the healthy branch starts with a thousand times more probability than the diseased one, so even a small error rate applied to it produces more positives than a near-perfect detection rate applied to the tiny diseased branch. Ignoring $P(D)$ and reading the posterior off the sensitivity is the base-rate fallacy.

Figure 1.49. Prior against posterior for the screening example. A positive result multiplies the probability of disease by about

90

, from

0.001

0.0902

— a large update in relative terms that still leaves the disease unlikely in absolute terms.

The update is enormous and the conclusion is still "probably not diseased". Both statements are true at once, and holding them together is the skill. In practice the resolution is a second, different test: the positive screen has moved the prior from $0.001$ to $0.09$ , and a confirmatory test now starts from that much more favourable base rate.

Proposition 1.50 (Odds form of Bayes' theorem). Define the odds of an event $B$ as $\mathrm{odds}(B) = P(B)/P(B^c)$ . Then for any data $A$ with $P(A) > 0$ ,

\underbrace{\frac{P(B \mid A)}{P(B^c \mid A)}}_{\text{posterior odds}} = \underbrace{\frac{P(A \mid B)}{P(A \mid B^c)}}_{\text{likelihood ratio}} \times \underbrace{\frac{P(B)}{P(B^c)}}_{\text{prior odds}}.

Proof. Apply Bayes' theorem to $B$ and to $B^c$ separately:

P(B \mid A) = \frac{P(A \mid B)P(B)}{P(A)}, \qquad P(B^c \mid A) = \frac{P(A \mid B^c)P(B^c)}{P(A)}.

Divide the first by the second. The common denominator $P(A)$ cancels, leaving the stated product — which is why the odds form needs no total-probability computation at all.∎

Example 1.51 (The screening result in odds form). Redo the disease calculation using odds, and then find the posterior after a second independent positive test.

Solution. Prior odds: $0.001/0.999 = 1/999 \approx 0.001001$ . Likelihood ratio for a positive: $0.99/0.01 = 99$ .

Posterior odds after one positive: $99/999 = 11/111 \approx 0.09910$ . Converting back with $P = \text{odds}/(1 + \text{odds})$ ,

P(D \mid +) = \frac{0.09910}{1.09910} \approx 0.0902,

agreeing with the direct computation.

Now a second test, assumed conditionally independent of the first given disease status. Independence given $D$ and given $D^c$ makes the likelihood ratio of the pair the product of the individual ratios, $99 \times 99 = 9801$ , so

\text{posterior odds} = 9801 \times \frac{1}{999} \approx 9.811, \qquad P(D \mid ++) = \frac{9.811}{10.811} \approx 0.9075.

The direct check: $0.99^2 \times 0.001 = 0.0009801$ and $0.01^2 \times 0.999 = 0.0000999$ , and $0.0009801/0.00108 = 0.9075$ .

Sanity check on the structure: each positive multiplies the odds by $99$ , so evidence accumulates multiplicatively on the odds scale — which is precisely why the odds form is the one used in practice. Two positives take the patient from $0.1\%$ to $91\%$ .□

Pitfall. The second-test calculation rests on conditional independence given disease status, and that assumption fails when the two tests share a mechanism. Running the same assay twice on the same sample, on a patient whose blood chemistry is what confuses the assay, gives two positives that carry barely more information than one. The multiplicative update then overstates the evidence badly. A confirmatory test must be a different test for the arithmetic above to mean anything.

The posterior depends on the prevalence, and it is worth seeing how strongly. The figure below holds the test fixed — sensitivity and specificity both $0.99$ , as in the example — and sweeps the prevalence.

Figure 1.52. Posterior probability of disease after one positive test, as a function of prevalence, for a test with sensitivity and specificity both

0.99

. The screening example sits at prevalence

0.001

, marked, where the posterior is only

0.0902

; the same test applied to a symptomatic population with prevalence

0.05

returns a posterior above

0.8

. The test never changed — the base rate did.

Example 1.53 (Spam filtering). A filter flags $95\%$ of spam messages and wrongly flags $2\%$ of legitimate ones. If $40\%$ of incoming mail is spam, what is the probability that a flagged message really is spam?

Solution. Let $S$ be "spam", $F$ be "flagged". Then $P(S) = 0.4$ , $P(F \mid S) = 0.95$ , $P(F \mid S^c) = 0.02$ .

Total probability: $P(F) = 0.95 \times 0.4 + 0.02 \times 0.6 = 0.38 + 0.012 = 0.392$ .

Bayes: $P(S \mid F) = 0.38/0.392 \approx 0.9694$ .

Compare with the medical test, where a more accurate instrument gave a posterior of $0.09$ . The difference is entirely the base rate: spam is common, so the prior odds $0.4/0.6 = 2/3$ start high, and the likelihood ratio $0.95/0.02 = 47.5$ pushes them to $31.67$ , giving $31.67/32.67 \approx 0.969$ . A rare event needs a far stronger likelihood ratio to reach the same posterior.□

Summary. Axioms. A probability measure satisfies $P(A) \ge 0$ , $P(S) = 1$ , and countable additivity over pairwise disjoint events. Everything below is derived from those three, so every one of them holds in any probability model.

Derived rules, no hypotheses needed. $P(\varnothing) = 0$ ; finite additivity; $P(A^c) = 1 - P(A)$ ; monotonicity, $A \subseteq B \Rightarrow P(A) \le P(B)$ , hence $0 \le P(A) \le 1$ ; the addition rule $P(A \cup B) = P(A) + P(B) - P(A\cap B)$ ; Boole's inequality $P(\bigcup A_i) \le \sum P(A_i)$ ; and inclusion–exclusion for three events with its $+P(A\cap B\cap C)$ correction.

Requires equally likely outcomes. $P(A) = |A|/|S|$ holds only on a finite equiprobable sample space. Counting then uses the multiplication principle, $P(n,k) = n!/(n-k)!$ for ordered selections without repetition, $n^k$ with repetition, and $\binom{n}{k} = n!/(k!(n-k)!)$ for unordered selections — with the same ordering convention used for $|A|$ and $|S|$ .

Requires $P(B) > 0$ . $P(A \mid B) = P(A \cap B)/P(B)$ , which is itself a probability measure in $A$ , so the complement and addition rules apply in front of the bar but never behind it. The multiplication rule $P(A \cap B) = P(A)P(B \mid A)$ and the chain rule follow.

Requires independence. $P(A \cap B) = P(A)P(B)$ is the definition; when $P(B) > 0$ it is equivalent to $P(A \mid B) = P(A)$ . Independence passes to complements. Mutually exclusive events of positive probability are never independent. Mutual independence of $n$ events requires the product rule on every subcollection, not just on pairs.

Requires a partition. With $B_i$ disjoint, exhaustive and each of positive probability, the law of total probability gives $P(A) = \sum_i P(A \mid B_i)P(B_i)$ , and $P(A)$ must lie between the smallest and largest $P(A \mid B_i)$ .

Requires $P(A) > 0$ . Bayes' theorem, $P(B \mid A) = P(A \mid B)P(B)/P(A)$ , with the denominator supplied by total probability. Equivalently, posterior odds equal the likelihood ratio times the prior odds. The posterior depends on the prior: a $99\%$ -accurate test on a disease of prevalence $0.001$ gives a posterior of only $0.0902$ , and a second conditionally independent positive raises it to $0.9075$ .

Exercises for §1.6 →

Common Mistakes

Forgetting to subtract the overlap in $P(A \cup B)$ . Additivity is an axiom only for mutually exclusive events; for any others the correction $-P(A \cap B)$ is compulsory.
Confusing mutually exclusive with independent. For events of positive probability they are incompatible: exclusivity forces $P(A \cap B) = 0$ while independence forces $P(A)P(B) > 0$ .
Assuming independence rather than justifying it. Independence comes from the design — separate tosses, random sampling, randomised assignment — never from the events feeling unrelated.
Checking independence only in pairs. Three events can be pairwise independent and still fail mutual independence, as two coins and the event "they match" show.
Swapping $P(A \mid B)$ and $P(B \mid A)$ . These answer different questions, and converting between them requires the prior; doing it without one is the prosecutor's fallacy.
Applying the complement rule behind the bar. $P(A \mid B^c) = 1 - P(A \mid B)$ is false; the correct identity is $P(A^c \mid B) = 1 - P(A \mid B)$ .
Reading a posterior off the sensitivity. With a rare disease the false positives from the large healthy group outnumber the true positives, which is why $99\%$ accuracy can yield a $9\%$ posterior.
Using $P(A) = |A|/|S|$ on a sample space whose outcomes are not equally likely, such as the eleven possible sums of two dice.
Mixing ordered and unordered counts in the same fraction. Both $|A|$ and $|S|$ must use one convention.
Double counting in "at least one" problems. Use the complement, or sum over disjoint cases by exact number.
Choosing permutations when order does not matter, or combinations when it does. Ask whether rearranging the selection produces a genuinely different outcome.
Conditioning on an event of probability zero. $P(A \mid B)$ is undefined when $P(B) = 0$ ; the definition divides by it.
Using cases that do not partition the sample space in the law of total probability. Overlapping cases double count; incomplete cases lose probability. Check that the weights sum to $1$ .
Multiplying likelihood ratios for repeated tests that are not conditionally independent. Two runs of the same assay on the same sample are not two pieces of evidence.
Treating a large relative update as a large absolute probability. Multiplying a probability by $90$ is dramatic and still leaves $0.001$ below $0.1$ .

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Random Variables and Discrete Distributions →

Helpful?