1.2 Probability Spaces, Conditioning and Bayes’ Theorem
Kolmogorov's axioms and everything that follows from them: σ-fields, inclusion–exclusion, classical and geometric probability, conditional probability, Bayes' theorem, independence and the Borel–Cantelli lemmas, together with the birthday, matching, Pólya urn and gambler's ruin problems.
For three centuries probability was a collection of clever solutions to gambling problems: Cardano on dice, Pascal and Fermat on the division of stakes, Bernoulli on long runs of trials, Bayes and Laplace on reasoning from effects back to causes. The solutions were brilliant, but the foundations were shaky. "Choose a chord of a circle at random" gave three different answers depending on how one chose, and nobody could say which was right. In 1933 Andrei Kolmogorov resolved this by axiomatising the subject inside measure theory. A probability is a countably additive measure of total mass $1$ on a σ-field of subsets of a sample space. Every rule of probability then becomes a theorem, and every paradox reveals an unstated choice of probability space.
This section builds that framework and uses it. From the axioms we derive inclusion–exclusion, classical and geometric probabilities, conditional probability, the law of total probability and Bayes' theorem, which governs medical diagnosis, spam filtering and the reliability of forensic evidence. We then study independence, where the gap between pairwise and mutual independence is a favourite CSIR trap, and the Borel–Cantelli lemmas, which decide whether infinitely many of a sequence of events occur. The classic problems (birthdays, matchings, Pólya's urn, the gambler's ruin) are worked in full. They are short, they reward exactly the right conditioning argument, and they appear in the exam in many disguises.
Sample Spaces, σ-Fields and Kolmogorov's Axioms
When $\Omega$ is finite or countable, every subset can be an event. For $\Omega=[0,1]$ this is impossible: there is no way to assign a "length" to every subset of $[0,1]$ that is countably additive and invariant under translation (the Vitali set, studied in the sister course on Unit 1). So we must specify which subsets are events, and the collection must be closed under the operations we use.
A collection $\mathcal{F}$ of subsets of $\Omega$ is a field (algebra) if (i) $\Omega\in\mathcal{F}$; (ii) $A\in\mathcal{F}\Rightarrow A^c\in\mathcal{F}$; (iii) $A,B\in\mathcal{F}\Rightarrow A\cup B\in\mathcal{F}$. It is a σ-field (σ-algebra) if (iii) is strengthened to
(iii′) $\ A_1,A_2,\ldots\in\mathcal{F}\ \Rightarrow\ \bigcup_{n=1}^\infty A_n\in\mathcal{F}$.
For any collection $\mathcal{C}$ of subsets, the σ-field generated by $\mathcal{C}$, written $\sigma(\mathcal{C})$, is the smallest σ-field containing $\mathcal{C}$. The Borel σ-field $\mathcal{B}(\mathbb{R})$ is the σ-field generated by the open intervals. It contains every interval, every open or closed set and every countable set.
Let $\mathcal{F}$ be a σ-field on $\Omega$.
- $\varnothing\in\mathcal{F}$, and $\mathcal{F}$ is closed under countable intersections, finite unions and intersections, and differences $A\setminus B$.
- Any intersection of σ-fields on $\Omega$ (indexed by any set) is a σ-field; hence $\sigma(\mathcal{C})$ exists and equals the intersection of all σ-fields containing $\mathcal{C}$.
- If $\Omega$ is partitioned into $k$ nonempty sets $B_1,\dots,B_k$ (the atoms), then $\sigma(\{B_1,\dots,B_k\})$ consists of all unions of atoms and has exactly $2^k$ elements. In particular, every finite σ-field has $2^k$ elements for some $k$.
- The union of two σ-fields need not be a σ-field.
Proof. (1) $\varnothing=\Omega^c$. By De Morgan, $\bigcap A_n=\left(\bigcup A_n^c\right)^c$. Finite unions are countable unions with $A_n=\varnothing$ from some point on, and $A\setminus B=A\cap B^c$.
(2) If every $\mathcal{F}_i$ contains $\Omega$ and is closed under complements and countable unions, so is $\bigcap_i\mathcal{F}_i$. The power set $\mathcal{P}(\Omega)$ is a σ-field containing $\mathcal{C}$, so the family of such σ-fields is nonempty, and its intersection is the smallest one.
(3) Let $\mathcal{U}$ be the collection of unions $\bigcup_{j\in J}B_j$, $J\subseteq\{1,\dots,k\}$. It contains $\Omega$ ($J$ = everything), it is closed under complements (the complement of $\bigcup_{J}B_j$ is $\bigcup_{J^c}B_j$, because the atoms partition $\Omega$), and it is closed under unions (unions of index sets). So $\mathcal{U}$ is a σ-field containing the atoms, and any σ-field containing the atoms contains their finite unions, so $\mathcal{U}=\sigma(\{B_j\})$. Distinct $J$ give distinct unions because the atoms are disjoint and nonempty, so $|\mathcal{U}|=2^k$. If $\mathcal{F}$ is any finite σ-field, its atoms are the nonempty sets of the form $\bigcap_{A\in\mathcal{F}}A^{\pm}$ (each $A$ or its complement). They partition $\Omega$, and $\mathcal{F}$ is generated by them.
(4) On $\Omega=\{1,2,3\}$, $\mathcal{F}_1=\{\varnothing,\{1\},\{2,3\},\Omega\}$ and $\mathcal{F}_2=\{\varnothing,\{2\},\{1,3\},\Omega\}$ are σ-fields. Their union contains $\{1\}$ and $\{2\}$ but not $\{1,2\}$. ∎
(A1) $P(A)\ge0$ for every $A\in\mathcal{F}$; (A2) $P(\Omega)=1$;
(A3) countable additivity: if $A_1,A_2,\ldots\in\mathcal{F}$ are pairwise disjoint, then $P\left(\bigcup_nA_n\right)=\sum_nP(A_n)$.
The triple $(\Omega,\mathcal{F},P)$ is a probability space. An event with $P(A)=1$ is said to happen almost surely (a.s.).For events $A,B,A_n$ in a probability space:
- $P(\varnothing)=0$, and $P$ is finitely additive;
- $P(A^c)=1-P(A)$; if $A\subseteq B$ then $P(B\setminus A)=P(B)-P(A)$ and $P(A)\le P(B)$; hence $0\le P(A)\le1$;
- $P(A\cup B)=P(A)+P(B)-P(A\cap B)$;
- (Boole's inequality) $P\left(\bigcup_nA_n\right)\le\sum_nP(A_n)$ for any sequence of events;
- (continuity) if $A_1\subseteq A_2\subseteq\cdots$ then $P\left(\bigcup A_n\right)=\lim P(A_n)$; if $A_1\supseteq A_2\supseteq\cdots$ then $P\left(\bigcap A_n\right)=\lim P(A_n)$.
Proof. (1) Apply (A3) to $\Omega,\varnothing,\varnothing,\dots$: $P(\Omega)=P(\Omega)+\sum_{n\ge2}P(\varnothing)$. The series must converge, which forces $P(\varnothing)=0$. Finite additivity is (A3) with $A_n=\varnothing$ beyond some index.
(2) $\Omega=A\cup A^c$ is a disjoint union, so $1=P(A)+P(A^c)$. If $A\subseteq B$, then $B=A\cup(B\setminus A)$ disjointly, so $P(B)=P(A)+P(B\setminus A)\ge P(A)$.
(3) $A\cup B=A\cup(B\setminus A)$ disjointly, and $P(B\setminus A)=P(B)-P(A\cap B)$ by (2) applied to $A\cap B\subseteq B$.
(4) Put $B_1=A_1$ and $B_n=A_n\setminus(A_1\cup\cdots\cup A_{n-1})$. The $B_n$ are disjoint, $B_n\subseteq A_n$, and $\bigcup B_n=\bigcup A_n$. So $P(\bigcup A_n)=\sum P(B_n)\le\sum P(A_n)$.
(5) For increasing $A_n$, the sets $B_n$ of (4) are $A_n\setminus A_{n-1}$, and $$P\Big(\bigcup A_n\Big)=\sum_{k=1}^\infty P(B_k)=\lim_{n\to\infty}\sum_{k=1}^nP(B_k)=\lim_{n\to\infty}P(A_n).$$ For decreasing $A_n$, apply this to the increasing complements $A_n^c$ and use (2). ∎
Continuity is exactly where countable additivity is needed: a merely finitely additive "probability" can fail it. It is the property behind the right-continuity of distribution functions (§1.3) and behind the Borel–Cantelli lemmas below.
Proof. For each $J\subseteq\{1,\dots,n\}$ let the atom $C_J$ be the event that exactly the $A_i$ with $i\in J$ occur. The $2^n$ atoms are disjoint and cover $\Omega$, and $A_{i_1}\cap\cdots\cap A_{i_k}$ is the union of the atoms $C_J$ with $J\supseteq\{i_1,\dots,i_k\}$. An atom with $|J|=m$ lies in $\binom mk$ of the $k$-fold intersections, so by finite additivity $$S_k=\sum_JP(C_J)\binom{|J|}{k},\qquad P\Big(\bigcup A_i\Big)=\sum_{|J|\ge1}P(C_J).$$ So it suffices to compare coefficients atom by atom. For $m=|J|\ge1$, the identity $\sum_{k=0}^{j}(-1)^k\binom mk=(-1)^j\binom{m-1}{j}$ (proved by induction on $j$ using Pascal's rule) gives $$\sum_{k=1}^{j}(-1)^{k+1}\binom mk=1-(-1)^j\binom{m-1}{j}.$$ For $j=n\ge m$ the last binomial coefficient vanishes, so each atom with $m\ge1$ is counted exactly once: this is inclusion–exclusion. For $j\lt n$ the coefficient is $\ge1$ when $j$ is odd and $\le1$ when $j$ is even, which gives the Bonferroni inequalities. Atoms with $m=0$ contribute $0$ to both sides. ∎
Classical, Combinatorial and Geometric Probability
(a) Classical model. If $\Omega$ is finite and all outcomes are equally likely, then $P(A)=|A|/|\Omega|$ for every $A\subseteq\Omega$.
(b) Geometric model. If $\Omega\subseteq\mathbb{R}^d$ has finite positive volume (length, area) $|\Omega|$ and the outcome is "uniformly distributed" in $\Omega$, then $P(A)=|A|/|\Omega|$ for Borel sets $A\subseteq\Omega$. Single points, and even countable sets, then have probability $0$ without being impossible.
Proof. Let $A_i$ be the event that letter $i$ is in envelope $i$. For $i_1\lt\cdots\lt i_k$, the arrangements fixing these $k$ letters number $(n-k)!$, so $P(A_{i_1}\cdots A_{i_k})=\frac{(n-k)!}{n!}$ and $S_k=\binom nk\frac{(n-k)!}{n!}=\frac1{k!}$. By inclusion–exclusion, $P(\bigcup A_i)=\sum_{k=1}^n\frac{(-1)^{k+1}}{k!}$, and the complement is the first formula. Its limit is the exponential series at $-1$. Writing $D_m=m!\sum_{j=0}^m\frac{(-1)^j}{j!}$ for the number of arrangements of $m$ letters with no match (derangements), an arrangement with exactly $k$ matches is a choice of the $k$ matched letters followed by a derangement of the other $n-k$. So the probability is $\binom nk\frac{D_{n-k}}{n!}=\frac{1}{k!}\cdot\frac{D_{n-k}}{(n-k)!}$, which is the second formula. ∎
The convergence is remarkably fast: $P(\text{no match})=\tfrac38=0.375$ for $n=4$, $\tfrac{11}{30}\approx0.3667$ for $n=5$, and agrees with $1/e$ to six decimals for $n=10$. The limit $e^{-1}/k!$ is the Poisson distribution with mean $1$ (§2.1): many rare, nearly independent events.
Conditional Probability, Total Probability and Bayes' Theorem
Information changes probabilities. If we learn that $B$ has occurred, the outcomes outside $B$ are ruled out, and the outcomes inside $B$ keep their relative weights. This is the definition.
Proof. (a) $P(A\mid B)\ge0$; $P(\Omega\mid B)=P(B)/P(B)=1$; and for disjoint $A_n$ the sets $A_n\cap B$ are disjoint, so $P(\bigcup A_n\mid B)$ $=\sum P(A_n\cap B)/P(B)$ $=\sum P(A_n\mid B)$. Finally $P(B^c\mid B)=0$. (b) The hypothesis makes every conditioning event have positive probability, since $A_1\cdots A_k\supseteq A_1\cdots A_{n-1}$. The right side telescopes: $P(A_1)\cdot\frac{P(A_1A_2)}{P(A_1)}\cdots\frac{P(A_1\cdots A_n)}{P(A_1\cdots A_{n-1})}$. ∎
Proof. $A=\bigcup_i(A\cap B_i)$ is a disjoint union, so by countable additivity $P(A)=\sum_iP(A\cap B_i)=\sum_iP(A\mid B_i)P(B_i)$. Then $P(B_j\mid A)=P(A\cap B_j)/P(A)$, with numerator $P(A\mid B_j)P(B_j)$ and the denominator just computed. ∎
In Bayes' theorem the $P(B_j)$ are the prior probabilities of the "causes" $B_j$, the $P(A\mid B_j)$ are the likelihoods of the observed evidence $A$, and the $P(B_j\mid A)$ are the posterior probabilities. In odds form, for two causes, $$\frac{P(B_1\mid A)}{P(B_2\mid A)}=\frac{P(A\mid B_1)}{P(A\mid B_2)}\cdot\frac{P(B_1)}{P(B_2)}:$$ posterior odds equal the likelihood ratio times the prior odds. This is the seed of Bayesian inference (§4.3) and of the Neyman–Pearson lemma (§5.1).
Proof. We prove by induction on $n$ that the statement holds for every initial composition $(r,b)$. For $n=1$ it is the classical probability of drawing red. Assume it holds for $n$ and all compositions. Condition on the first draw. Given $R_1$, the urn holds $(r+c,b)$ and the process continues from there, so draw $n+1$ of the original urn is draw $n$ of an urn started at $(r+c,b)$, and by the induction hypothesis $P(R_{n+1}\mid R_1)=\frac{r+c}{r+b+c}$. Similarly $P(R_{n+1}\mid R_1^c)=\frac{r}{r+b+c}$. By total probability, $$P(R_{n+1})=\frac{r}{r+b}\cdot\frac{r+c}{r+b+c}+\frac{b}{r+b}\cdot\frac{r}{r+b+c}=\frac{r(r+c+b)}{(r+b)(r+b+c)}=\frac{r}{r+b}.$$ For dependence, $P(R_2\mid R_1)=\frac{r+c}{r+b+c}\gt\frac{r}{r+b}=P(R_2)$ when $c\ge1$. ∎
In fact, the probability of any particular colour sequence depends only on how many reds and blacks it contains, not on their order. (Multiply the successive conditional probabilities: the numerators run through $r,r+c,\dots$ and $b,b+c,\dots$ in some interleaving, and the denominators are always $r+b,\ r+b+c,\dots$.) Sequences with this property are called exchangeable. Consequently $P(R_1\mid R_n)=P(R_n\mid R_1)=\frac{r+c}{r+b+c}$ for every $n\ge2$: a later draw is as informative about an earlier one as the other way round.
Proof. Condition on the first bet. After a win the gambler is in the same situation as one who started with $i+1$, and after a loss as one who started with $i-1$, because the future bets are independent of the first. (The precise justification is the Markov property of §3.1.) By total probability, $$P_i=pP_{i+1}+qP_{i-1}\quad(1\le i\le N-1),\qquad P_0=0,\ P_N=1.$$ Since $p+q=1$, this reads $p(P_{i+1}-P_i)=q(P_i-P_{i-1})$, so the differences $\Delta_i=P_{i+1}-P_i$ satisfy $\Delta_i=\rho^{\,i}\Delta_0$. Summing, $$P_i=\Delta_0\left(1+\rho+\cdots+\rho^{\,i-1}\right),\qquad 1=P_N=\Delta_0\left(1+\rho+\cdots+\rho^{\,N-1}\right).$$ Dividing these two equations gives $P_i=\frac{1-\rho^i}{1-\rho^N}$ if $\rho\ne1$, and $P_i=i/N$ if $\rho=1$. Applying the same argument to the opponent (who wins each bet with probability $q$ and starts with $N-i$) gives a ruin probability that is exactly $1-P_i$, so the probability that the game goes on for ever is $0$. ∎
Small biases matter enormously. Starting with $3$ out of $N=10$, the probability of reaching $10$ is $0.3$ for a fair game but only about $0.128$ when $p=0.45$. Starting from the middle ($i=5$), it is about $0.268$ for $p=0.45$ and $0.732$ for $p=0.55$. For a fair game the expected duration is $i(N-i)$ bets, a result we prove in §3.1.
Independence and the Borel–Cantelli Lemmas
Events $A$ and $B$ are independent if $P(A\cap B)=P(A)P(B)$. (If $P(B)\gt0$ this says $P(A\mid B)=P(A)$, but the product form needs no positivity and is symmetric.)
A family $\{A_i:i\in I\}$ is (mutually) independent if $P(A_{i_1}\cap\cdots\cap A_{i_k})=P(A_{i_1})\cdots P(A_{i_k})$ for every finite set of distinct indices $i_1,\dots,i_k$. It is pairwise independent if this holds for $k=2$. For $n$ events, mutual independence consists of $2^n-n-1$ product conditions.
- If $\{A_i\}$ is independent, so is the family obtained by replacing any of the $A_i$ by their complements.
- An event with $P(A)\in\{0,1\}$ is independent of every event; $A$ is independent of itself iff $P(A)\in\{0,1\}$.
- If $A\cap B=\varnothing$, $P(A)\gt0$ and $P(B)\gt0$, then $A$ and $B$ are not independent.
- If $A,B,C$ are mutually independent, then $A$ is independent of $B\cup C$, $B\cap C$ and $B\setminus C$.
Proof. (1) It suffices to replace one event, say $A_1$, by $A_1^c$, and then repeat. For distinct indices $i_2,\dots,i_k$ other than $1$, write $C=A_{i_2}\cap\cdots\cap A_{i_k}$. Then $$P(A_1^c\cap C)=P(C)-P(A_1\cap C)=P(C)\left(1-P(A_1)\right)=P(A_1^c)P(C),$$ using the product rule for $C$ and for $A_1\cap C$. Products not involving $A_1$ are unchanged.
(2) If $P(A)=0$, then $P(A\cap B)\le P(A)=0=P(A)P(B)$. If $P(A)=1$, apply this to $A^c$ and use (1). Self-independence means $P(A)=P(A)^2$.
(3) $P(A\cap B)=0\ne P(A)P(B)$.
(4) $$P(A\cap(B\cup C))=P(AB)+P(AC)-P(ABC)$$ $$=P(A)\left[P(B)+P(C)-P(B)P(C)\right]=P(A)P(B\cup C).$$ The intersection is the definition, and $B\setminus C=B\cap C^c$ follows with (1). ∎
To speak about infinitely many events "eventually" or "infinitely often", we need two limit sets.
(a) (First lemma) If $\sum_nP(A_n)\lt\infty$, then $P(\limsup A_n)=0$: almost surely only finitely many $A_n$ occur. No independence is needed.
(b) (Second lemma) If the $A_n$ are mutually independent and $\sum_nP(A_n)=\infty$, then $P(\limsup A_n)=1$: almost surely infinitely many $A_n$ occur.
Proof. (a) For each $n$, $\limsup A_k\subseteq\bigcup_{k\ge n}A_k$, so by Boole's inequality $P(\limsup A_k)\le\sum_{k\ge n}P(A_k)$, which is the tail of a convergent series and tends to $0$.
(b) It suffices to show that $P\left(\bigcap_{k\ge n}A_k^c\right)=0$ for every $n$, because the complement of $\limsup A_k$ is the countable union of these sets. The complements $A_k^c$ are independent (Theorem 1.21(1)), so for $m\ge n$, using $1-x\le e^{-x}$, $$P\Big(\bigcap_{k=n}^mA_k^c\Big)=\prod_{k=n}^m\left(1-P(A_k)\right)\le\exp\Big(-\sum_{k=n}^mP(A_k)\Big)\xrightarrow[m\to\infty]{}0.$$ By continuity from above (Theorem 1.14(5)), $P\left(\bigcap_{k\ge n}A_k^c\right)=0$. ∎
For independent events the two lemmas together give a zero–one law: $P(A_n\text{ i.o.})$ is $0$ or $1$ according as $\sum P(A_n)$ converges or diverges. For example, if independent events have $P(A_n)=1/n^2$, only finitely many occur almost surely; with $P(A_n)=1/n$, or even $1/(n\log n)$, infinitely many occur. In an infinite sequence of fair coin tosses, any fixed pattern such as $HHH$ occurs infinitely often almost surely: apply (b) to the independent events "tosses $3k-2,3k-1,3k$ are $HHH$", each of probability $\tfrac18$. Borel–Cantelli is the main tool for proving almost-sure convergence in §2.3.
- Probability zero is not impossible. For a point chosen uniformly in $[0,1]$, every single point, and even all of $\mathbb{Q}\cap[0,1]$, has probability $0$, yet some point occurs. Likewise "almost surely" is weaker than "surely".
- No uniform distribution on $\mathbb{N}$. Equal probabilities $c$ on all of $\mathbb{N}$ would give total mass $0$ or $\infty$ by countable additivity. "A random positive integer" needs a specified non-uniform law.
- A union of σ-fields need not be a σ-field (Theorem 1.13(4)), although an intersection always is. A field need not be a σ-field: the finite and cofinite subsets of $\mathbb{N}$ form a field but not a σ-field (Exercise I.2).
- Pairwise does not imply mutual independence (two coins and "they agree"). Nor does $P(ABC)=P(A)P(B)P(C)$ imply pairwise independence (Example 7(b)).
- Disjoint is the opposite of independent. Disjoint events with positive probabilities are always dependent: one occurring rules out the other.
- Independent of $B$ and of $C$, but not of $B\cup C$ (Example 7(a)). Theorem 1.21(4) needs mutual independence of all three events.
- $P(A\mid B)\ne P(B\mid A)$. A test with $95\%$ sensitivity can have under $9\%$ positive predictive value (Example 5). Ignoring the prior is the base-rate fallacy.
- "At random" must be specified. Bertrand's paradox: the probability that a "random chord" of a circle is longer than the side of the inscribed equilateral triangle is $\tfrac13$, $\tfrac12$ or $\tfrac14$, depending on whether the chord's endpoints, its distance from the centre, or its midpoint is chosen uniformly (Exercise II.8).
- The second Borel–Cantelli lemma needs independence. With the uniform probability on $(0,1)$, $A_n=(0,\tfrac1n)$ has $\sum P(A_n)=\infty$, yet $\limsup A_n=\varnothing$.
- Exchangeable is not independent. Pólya-urn draws all have the same marginal probability $\tfrac{r}{r+b}$, and order does not matter, but $P(R_2\mid R_1)\gt P(R_2)$.
- Birthday wording. "Some two of $23$ people share a birthday" has probability $0.507$. "Someone among $22$ others shares my birthday" has probability $0.059$, and needs $253$ others to pass $\tfrac12$.
- Occupancy patterns are not equally likely. Two distinct balls in two boxes give the patterns "both in box 1", "one each", "both in box 2" with probabilities $\tfrac14,\tfrac12,\tfrac14$, not $\tfrac13$ each.
Exercises
- 1 On $\Omega=\{1,2,3,4,5\}$, list the atoms of $\sigma(\{\{1,2\},\{2,3\}\})$ and find the number of its elements.
- 2 Show that the collection of subsets of $\mathbb{N}$ that are finite or have finite complement is a field but not a σ-field.
- 3 Prove that $P(A\cap B)\ge P(A)+P(B)-1$ and, more generally, $P\left(\bigcap_{i=1}^nA_i\right)\ge1-\sum_{i=1}^nP(A_i^c)$.
- 4 $P(A)=0.6$, $P(B)=0.5$, $P(C)=0.4$, $P(AB)=0.3$, $P(AC)=P(BC)=0.2$ and $P(ABC)=0.1$. Find the probability that at least one, exactly one, and at least two of the events occur.
- 5 Let $P$ be any probability on $(\mathbb{R},\mathcal{B}(\mathbb{R}))$. Show that $P\left((-\infty,x+\tfrac1n]\right)\to P\left((-\infty,x]\right)$ and $P\left((-\infty,x-\tfrac1n]\right)\to P\left((-\infty,x)\right)$.
- 6 Prove that there is no probability measure on $(\mathbb{N},\mathcal{P}(\mathbb{N}))$ that gives every singleton the same probability.
- 7 An integer is chosen at random from $1,\dots,1000$. Find the probability that it is divisible by none of $2,3,5,7$.
- 8 Prove that if $P(A_n)=1$ for every $n$, then $P\left(\bigcap_nA_n\right)=1$, and if $P(A_n)=0$ for every $n$, then $P\left(\bigcup_nA_n\right)=0$.
- 1 A committee of $4$ is chosen at random from $6$ men and $5$ women. Find the probability that it contains exactly $2$ women.
- 2 In the birthday problem, find the smallest $n$ for which $p_n\gt0.9$.
- 3 For $n=5$ letters in random envelopes, find the probabilities of $0,1,2,3,4,5$ matches. Why is the probability of exactly $4$ matches zero?
- 4 How many solutions does $x_1+x_2+x_3=10$ have in nonnegative integers, and how many in positive integers? If one nonnegative solution is chosen uniformly at random, what is $P(x_1=0)$?
- 5 A stick is broken at a uniformly chosen point. Find the probability that the longer piece is at least twice as long as the shorter.
- 6 (Buffon's needle) A needle of length $\ell$ is dropped on a floor ruled with parallel lines a distance $d\ge\ell$ apart. The distance $y\in[0,\tfrac d2]$ of its centre from the nearest line and its angle $\theta\in[0,\pi)$ with the lines are uniform on the rectangle. Show that $P(\text{the needle crosses a line})=\frac{2\ell}{\pi d}$.
- 7 The point $(x,y)$ is uniform on $[0,1]^2$. Find $P\left(\max(x,y)\le2\min(x,y)\right)$.
- 8 Compute the three answers of Bertrand's paradox: the probability that a random chord of the unit circle is longer than $\sqrt3$ when (a) its two endpoints are independent and uniform on the circle; (b) its distance from the centre is uniform on $[0,1]$; (c) its midpoint is uniform in the disc.
- 1 Machines $M_1,M_2,M_3$ make $50\%,30\%,20\%$ of a factory's output, with defect rates $2\%,3\%,5\%$. A random item is defective. Find the posterior probability of each machine.
- 2 A family has two children, each independently a boy or a girl with probability $\tfrac12$. Find $P(\text{two boys}\mid\text{at least one boy})$ and $P(\text{two boys}\mid\text{the elder is a boy})$.
- 3 (Monty Hall) A prize is behind one of three doors, uniformly at random. You pick door 1. The host, who knows where the prize is, opens a door other than yours that hides no prize, choosing at random if he has a choice. He opens door 3. Show that switching to door 2 wins with probability $\tfrac23$.
- 4 For events with $0\lt P(A),P(B)\lt1$, prove that $P(A\mid B)\gt P(A)\iff P(B\mid A)\gt P(B)\iff P(A\mid B)\gt P(A\mid B^c)$.
- 5 Three cards are drawn without replacement from a standard deck. Use the multiplication rule to find the probability that all three are aces.
- 6 A coin is either fair or two-headed, each with prior probability $\tfrac12$. It is tossed $n$ times and shows heads every time. Find the posterior probability that it is two-headed, and its value for $n=3$.
- 7 In Pólya's urn with $r=2$, $b=3$, $c=1$, find $P(R_1R_2R_3)$ and $P(R_1\mid R_3)$.
- 8 In the gambler's ruin with $p=0.6$, $i=2$ and $N=5$, find the probability of reaching $5$.
- 1 $A$ and $B$ are independent with $P(A)=0.3$ and $P(B)=0.4$. Find $P(A\cup B)$ and the probability that exactly one of them occurs.
- 2 Two fair dice are rolled. Let $A$ = "the first is odd", $B$ = "the second is odd", $C$ = "the sum is odd". Are $A,B,C$ pairwise independent? Mutually independent?
- 3 Prove directly that if $A$ and $B$ are independent, then so are $A^c$ and $B^c$.
- 4 Each of $n$ independent components fails with probability $0.01$. Find the smallest $n$ such that at least one failure has probability at least $0.95$.
- 5 Independent events have $P(A_n)=1/n^2$. Show that almost surely only finitely many occur. What changes if $P(A_n)=1/n$?
- 6 In an infinite sequence of fair coin tosses, show that the pattern $HTH$ occurs infinitely often with probability $1$.
- 7 Give events $A_n$ with $\sum P(A_n)=\infty$ but $P(\limsup A_n)=0$, and events with $P(A_n)\to0$ but $P(\limsup A_n)=1$.
- 8 Show that $\limsup A_n\supseteq\liminf A_n$, and compute both for $A_n=[0,1]$ ($n$ odd), $A_n=[1,2]$ ($n$ even).
E1. CSIR Part B Let $P(A)=0.6$, $P(B)=0.5$ and $P(A\cup B)=0.8$. Which of the following is true? (A) $A$ and $B$ are mutually exclusive; (B) $A$ and $B$ are independent; (C) $P(A\mid B)=0.5$; (D) $P(A^c\cap B^c)=0.3$.
E2. CSIR Part B GATE ST A fair die is rolled. If it shows $1$ or $2$, a coin with $P(\text{head})=\tfrac13$ is tossed; otherwise a fair coin is tossed. Given that the toss shows a head, the probability that the die showed $1$ or $2$ is (A) $\tfrac14$; (B) $\tfrac13$; (C) $\tfrac29$; (D) $\tfrac19$.
E3. CSIR Part B Let $A,B,C$ be subsets of $\Omega$ such that all eight sets $A^{\pm}\cap B^{\pm}\cap C^{\pm}$ are nonempty. The number of sets in the σ-field generated by $\{A,B,C\}$ is (A) $8$; (B) $16$; (C) $64$; (D) $256$.
E4. CSIR Part C Which of the following statements are true for events in a probability space? (One or more options may be correct.) (A) Pairwise independent events are mutually independent. (B) If $A$ is independent of itself, then $P(A)\in\{0,1\}$. (C) Two disjoint events, each of positive probability, cannot be independent. (D) If $A$ is independent of $B$ and $A$ is independent of $C$, then $A$ is independent of $B\cup C$.
E5. CSIR Part C Let $A_1,A_2,\dots$ be events with $p_n=P(A_n)$. Which of the following are true? (A) If $p_n=1/n^2$, then $P(\limsup A_n)=0$. (B) If the $A_n$ are independent and $p_n=\frac{1}{n\log n}$ for $n\ge2$, then $P(\limsup A_n)=1$. (C) If $p_n=1/n$, then $P(\limsup A_n)=1$. (D) If the $A_n$ are independent, then $P(\limsup A_n)\in\{0,1\}$.
E6. CSIR Part C Which of the following are true? (A) In Pólya's urn (start with $r$ red and $b$ black, add $c\ge1$ of the drawn colour), the second draw is red with the same probability as the first. (B) In Pólya's urn with $c\ge1$, the colours of the first two draws are independent. (C) For $n$ letters placed at random in $n$ envelopes, $P(\text{no letter is correctly placed})\to1/e$ as $n\to\infty$. (D) Among $22$ other people, with $365$ equally likely birthdays, the probability that at least one shares your birthday exceeds $\tfrac12$.
Suggested plan: 3 lectures × 60 min.
- Axioms. Open with Bertrand's chord (Exercise II.8) to motivate the need for a precise probability space. Definitions 1.9–1.11; Theorem 1.13 with Example 1 (count atoms on the board); Theorem 1.14 (prove continuity: it is the one non-obvious consequence); inclusion–exclusion through atoms (Theorem 1.15) and Example 2.
- Counting and conditioning. Birthday problem (ask for guesses first), matching (Theorem 1.16), the geometric Example 4 drawn on squared paper. Project Interactive 1 for the birthday and matching modes. Conditional probability, total probability, Bayes; Example 5 with Interactive 2. Let students set prevalence to 0.1% and then 30%, and ask them to explain why the posterior changes so much.
- Pólya, ruin, independence. Theorem 1.19 by induction, Example 6, gambler's ruin (Theorem 1.20), with Interactive 1 in the ruin mode at $p=0.45$ and $0.5$. Independence, Example 7 (let students check the four products themselves), lim sup of events and both Borel–Cantelli lemmas with proofs. Finish with E4 and E5 done live.
Discussion questions. (1) A forensic match occurs by chance in 1 person in a million, and a city has 5 million people. A suspect matches. What is missing before we can say how likely guilt is? (2) Is "independent" a property of events alone, or of events together with a probability measure? Find two events that are independent under one $P$ and dependent under another. (3) Why can't we just define probability on all subsets of $[0,1]$?
Misconceptions to watch for. Confusing "disjoint" with "independent"; equating $P(A\mid B)$ with $P(B\mid A)$; believing that pairwise independence suffices; treating occupancy patterns as equally likely; applying the second Borel–Cantelli lemma without independence; reading "probability $0$" as "impossible"; forgetting that $P(B)\gt0$ is needed in Definition 1.13.
Suggested homework. I(1, 3, 4, 7), II(2, 4, 6, 8), III(1, 3, 6, 8), IV(2, 4, 5, 7); Exam corner E2, E3, E6.
Research question. When is a positive screening result worth acting on, and how much does a second, confirmatory test help?
Why it matters. Mass screening programmes for tuberculosis, cervical and breast cancer, diabetic retinopathy and, recently, infectious diseases test large populations in which the condition is rare. Health ministries and the WHO publish sensitivities and specificities for the tests they recommend. Whether a programme helps or overwhelms clinics with false alarms is decided by Bayes' theorem, applied to the actual prevalence in each district.
What to do.
- Find published sensitivity and specificity figures for one screening test (for example a rapid diagnostic test or a sputum test for tuberculosis) and prevalence estimates for two populations, such as general screening versus symptomatic patients.
- Compute and plot the positive and negative predictive values $P(D\mid+)$ and $P(D^c\mid-)$ as functions of the prevalence from $0.1\%$ to $50\%$. Find the prevalence at which $P(D\mid+)=\tfrac12$ and prove that it equals $\dfrac{1-\text{spec}}{\text{sens}+1-\text{spec}}$.
- Model a two-stage strategy: confirm every positive with a second test, assumed conditionally independent given disease status. Compute the overall sensitivity, specificity and predictive value of "positive on both".
- Check your formulas by simulating 100,000 people with a seeded random number generator, and use Interactive 2 to cross-check single cases.
Tools: a spreadsheet or Python; Interactive 2 on this page.
Hand in: A one-page brief for a district health officer: the two predictive-value curves, the break-even prevalence, and a recommendation on whether to confirm positives before treatment.
Going further. Conditional independence of repeated tests is often false: the same patient characteristics that fool one test fool the next. Read about how correlated errors reduce the benefit of retesting, and model this with a third variable.
🧪 Self-check quiz
Q1. If $\varnothing\ne A\ne\Omega$, the σ-field generated by the single set $A$ has
Q2. A disease has prevalence $2\%$, and a test has sensitivity $90\%$ and specificity $90\%$. Approximately, $P(\text{disease}\mid\text{positive})$ is
Q3. $A$ and $B$ are independent with $P(A)=P(B)=\tfrac12$. Then $P(A^c\cap B^c)$ equals
Q4. Which hypothesis does the second Borel–Cantelli lemma need that the first does not?
Q5. As $n\to\infty$, the probability that a random permutation of $\{1,\dots,n\}$ has no fixed point tends to