Exercises — Lesson 14: Probability Models, Counting, Conditioning, and Bayes’ Rule
Exercise 14.1. [Hand] Three fair coin flips. List the sample space. Let \(A\) = “at least two heads” and \(B\) = “the first flip is heads.” Compute \(\mathbf{P}(A)\) and \(\mathbf{P}(A \mid B)\), and check whether \(A\) and \(B\) are independent.
Solution. Let \(0\) = “Tails” and \(1\) = “Heads”; flip attempts go right to left.
\[ \Omega = \{000,\, 001,\, 010,\, 011,\, 100,\, 101,\, 110,\, 111\}, \qquad |\Omega| = 2^3 = 8 \]
\[ \begin{aligned} A &= \text{"at least two heads"} = \{011,\, 101,\, 110,\, 111\}, & |A| &= \binom32 + \binom33 = \frac{3!}{2!\,1!} + \frac{3!}{3!\,0!} = 3 + 1 = 4 \\[8pt] B &= \text{"the first flip is heads"} = \{001,\, 011,\, 101,\, 111\}, & |B| &= 1 \cdot 2 \cdot 2 = 4 \end{aligned} \]
\[ \mathbf{P}(A) = \frac{|A|}{|\Omega|} = \frac48 = \frac12, \qquad \mathbf{P}(B) = \frac{|B|}{|\Omega|} = \frac48 = \frac12 \]
\[ A \cap B = \{011,\, 101,\, 111\},\quad |A \cap B| = 3, \qquad A \cup B = \{001,\, 011,\, 101,\, 110,\, 111\},\quad |A \cup B| = 5 \]
\[ \mathbf{P}(A \mid B) = \frac{\mathbf{P}(A \cap B)}{\mathbf{P}(B)} = \frac{|A \cap B| / |\Omega|}{|B| / |\Omega|} = \boxed{\;\frac34\;} \]
\(\mathbf{P}(A \mid B) \neq \mathbf{P}(A)\), so \(A\) and \(B\) are not independent.
Exercise 14.2. [Hand] A spam filter knows: \(30\%\) of email is spam, the word “free” appears in \(40\%\) of spam and \(5\%\) of non-spam. Apply Bayes’ rule to find \(\mathbf{P}(\text{spam} \mid \text{"free"})\). Then recompute with a prior of \(80\%\) spam and note how the posterior moves.
Solution. A spam filter knows:
\[ \mathbf{P}(\text{spam}) = 30\% = 0.3 = \frac{3}{10}, \qquad \mathbf{P}(\text{"free"} \mid \text{spam}) = 40\% = 0.4 = \frac25, \qquad \mathbf{P}(\text{"free"} \mid \neg\text{spam}) = 5\% = 0.05 = \frac{1}{20} \]
\[ \begin{aligned} \mathbf{P}(\text{spam} \mid \text{"free"}) &= \frac{\mathbf{P}(\text{"free"} \mid \text{spam})\,\mathbf{P}(\text{spam})} {\mathbf{P}(\text{"free"} \mid \text{spam})\,\mathbf{P}(\text{spam}) + \mathbf{P}(\text{"free"} \mid \neg\text{spam})\,\mathbf{P}(\neg\text{spam})} \\[8pt] &= \frac{(2/5)(3/10)}{(2/5)(3/10) + (1/20)(7/10)} \\[8pt] &= \frac{6/50}{(6/50) + (7/200)} = \frac{3/25}{(24/200) + (7/200)} = \frac{3}{25}\cdot\frac{200}{31} \\[8pt] &= \boxed{\;\frac{24}{31} \approx 0.77 = 77\%\;} \end{aligned} \]
Exercise 14.3. [Proof, \(\star\)] Prove the general union bound \(\mathbf{P}\big(\bigcup_{i=1}^n A_i\big) \le \sum_{i=1}^n \mathbf{P}(A_i)\) by induction from Proposition 14.2(c). (This one-line tool underlies half of the analyses in machine learning theory.)
Proof. By induction on \(n\).
Base cases \(n = 1\) and \(n = 2\): proven in Proposition 14.2(c).
Inductive hypothesis: assume the statement holds for \(k \in \mathbb{N}\), \(k < n\).
Inductive step: let \(\displaystyle S = \bigcup_{i=1}^{n-1} A_i\), and note \(\displaystyle \bigcup_{i=1}^{n} A_i = S \cup A_n\). Thus
\[ \begin{aligned} \mathbf{P}\Big(\bigcup_{i=1}^{n} A_i\Big) &= \mathbf{P}(S \cup A_n) \\[6pt] &= \mathbf{P}(S) + \mathbf{P}(A_n) - \mathbf{P}(S \cap A_n) && \text{[Proposition 14.2(c)]} \\[6pt] &\le \mathbf{P}(S) + \mathbf{P}(A_n) && \text{[}\mathbf{P}(S \cap A_n) \ge 0\text{]} \end{aligned} \]
Note \(\displaystyle \mathbf{P}(S) = \mathbf{P}\Big(\bigcup_{i=1}^{n-1} A_i\Big) \le \sum_{i=1}^{n-1} \mathbf{P}(A_i)\) by our inductive hypothesis. Thus
\[ \mathbf{P}\Big(\bigcup_{i=1}^{n} A_i\Big) \le \sum_{i=1}^{n} \mathbf{P}(A_i). \qquad \square \]
Exercise 14.4. [Proof] Verify that \(\mathbf{P}(\cdot \mid B)\) satisfies the three probability axioms. Then prove the “chain rule with a spectator”: \(\mathbf{P}(A \cap C \mid B) = \mathbf{P}(C \mid B)\,\mathbf{P}(A \mid B \cap C)\) whenever the conditioning events have positive probability.
Proof. Let \(A \subseteq \Omega\), and \(B \subseteq \Omega\) with \(\mathbf{P}(B) > 0\), and \(C \subseteq \Omega\).
(i) \(\displaystyle \mathbf{P}(A \mid B) = \frac{\mathbf{P}(A \cap B)}{\mathbf{P}(B)} \ge 0\) for all \(A \subseteq \Omega\), since \(\mathbf{P}(A \cap B) \ge 0\) and \(\mathbf{P}(B) \ge 0\). Nonnegativity ✓
(ii) Let \(A_1, A_2, \dots, A_n\) be disjoint events in \(\Omega\).
\[ \mathbf{P}(A_1 \cup A_2 \cup \cdots \mid B) = \frac{\mathbf{P}\big(\big(\bigcup_{i=1}^{n} A_i\big) \cap B\big)}{\mathbf{P}(B)} = \frac{\mathbf{P}\big(\bigcup_{i=1}^{n} (A_i \cap B)\big)}{\mathbf{P}(B)} = \frac{\sum_{i=1}^{n} \mathbf{P}(A_i \cap B)}{\mathbf{P}(B)} = \sum_{i=1}^{n} \mathbf{P}(A_i \mid B) \]
Additivity ✓
(iii) \(\displaystyle \mathbf{P}(\Omega \mid B) = \frac{\mathbf{P}(\Omega \cap B)}{\mathbf{P}(B)} = \frac{\mathbf{P}(B)}{\mathbf{P}(B)} = 1\). Normalization ✓
Prove \(\mathbf{P}(A \cap C \mid B) = \mathbf{P}(C \mid B)\,\mathbf{P}(A \mid B \cap C)\):
\[ \begin{aligned} \mathbf{P}(A \cap C \mid B) &= \frac{\mathbf{P}\big((A \cap C) \cap B\big)}{\mathbf{P}(B)} \\[6pt] &= \frac{\mathbf{P}(B \cap C \cap A)}{\mathbf{P}(B)} \\[6pt] &= \frac{\mathbf{P}(B)\,\mathbf{P}(C \mid B)\,\mathbf{P}(A \mid B \cap C)}{\mathbf{P}(B)} \\[6pt] &= \mathbf{P}(C \mid B)\,\mathbf{P}(A \mid B \cap C) \qquad \square \end{aligned} \]
Exercise 14.5. [Proof] Show that if \(A\) and \(B\) are independent, so are \(A\) and \(B^c\), and so are \(A^c\) and \(B^c\).
Proof.
\[ \begin{aligned} \mathbf{P}(A^c \cap B^c) &= 1 - \mathbf{P}(A \cup B) \\[6pt] &= 1 - \big(\mathbf{P}(A) + \mathbf{P}(B) - \mathbf{P}(A \cap B)\big) \\[6pt] &= 1 - \mathbf{P}(A) - \mathbf{P}(B) + \mathbf{P}(A \cap B) \\[6pt] &= 1 - 1 + \mathbf{P}(A^c) - 1 + \mathbf{P}(B^c) + 1 - \mathbf{P}(B^c) - \mathbf{P}(A^c) + \mathbf{P}(A^c)\mathbf{P}(B^c) && \text{[}\mathbf{P}(A \cap B) = \big(1 - \mathbf{P}(A^c)\big)\big(1 - \mathbf{P}(B^c)\big)\text{]} \\[6pt] &= \mathbf{P}(A^c)\,\mathbf{P}(B^c) \qquad \square \end{aligned} \]
\[ \begin{aligned} \mathbf{P}(A \cap B^c) &= \mathbf{P}(A)\,\mathbf{P}(B^c \mid A) \\[6pt] &= \mathbf{P}(A)\big(1 - \mathbf{P}(B \mid A)\big) \\[6pt] &= \mathbf{P}(A)\big(1 - \mathbf{P}(B)\big) && \text{[independence]} \\[6pt] &= \mathbf{P}(A) - \mathbf{P}(A)\mathbf{P}(B) \\[6pt] &= \mathbf{P}(A) - \mathbf{P}(A)\big(1 - \mathbf{P}(B^c)\big) \\[6pt] &= \mathbf{P}(A) - \mathbf{P}(A) + \mathbf{P}(A)\mathbf{P}(B^c) \\[6pt] &= \mathbf{P}(A)\,\mathbf{P}(B^c) \qquad \square \end{aligned} \]
Exercise 14.6. [Hand] A byte is a string of 8 bits. How many bytes are there? How many contain exactly three 1s? If a byte is chosen uniformly at random, what is the probability that it contains exactly three 1s? Exactly zero? Exactly eight?
Solution. A byte is a string of 8 bits.
\[ \begin{aligned} \#\text{ distinct 8-bit 0–1 patterns} &= 2^8 = 256 \\[8pt] \#\text{ patterns with exactly three 1s} &= \binom83 = \frac{8!}{3!\,5!} = \frac{8 \cdot 7 \cdot 6}{6} = 56 \end{aligned} \]
\[ \begin{aligned} \mathbf{P}(\text{byte contains exactly three 1s}) &= \frac{56}{256} = \frac{7}{32} \approx 21.88\% \\[8pt] \mathbf{P}(\text{exactly zero 1s}) &= \frac{1}{256} \\[8pt] \mathbf{P}(\text{exactly eight 1s}) &= \frac{1}{256} \end{aligned} \]
\[ \mathbf{P}(\text{exactly } k \text{ 1s}) = \frac{\binom8k}{2^8}, \qquad 0 \le k \le 8 \]
Exercise 14.7. [Hand] (a) How many distinct letter sequences can be formed by rearranging FILTER? By rearranging SIGNALS? (b) A committee of 4 is to be chosen from 10 people. How many committees are there? How many contain one designated person, and how many do not? Check that your three committee counts agree with Pascal’s rule, Proposition 14.6(b).
Solution.
(a) \(\#\) distinct sequences by rearranging:
\[ \begin{aligned} \text{FILTER} &= \binom{6}{1,1,1,1,1,1} = 6! = 720 \\[8pt] \text{SIGNALS} &= \binom{7}{2,1,1,1,1,1} = \frac{7!}{2!} = 2520 \end{aligned} \]
(b) Committee of 4 chosen from 10 people.
\[ \begin{aligned} \#\text{ committees} &= \binom{10}{4} = \frac{10!}{4!\,6!} = \frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210 \\[8pt] \#\text{ committees that contain one designated person} &= \binom93 = \frac{9!}{3!\,6!} = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84 \\[8pt] \#\text{ committees that do not contain one designated person} &= \binom94 = \frac{9!}{4!\,5!} = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} = 126 \end{aligned} \]
Check:
\[ \binom{10}{4} \;\overset{?}{=}\; \binom93 + \binom94, \qquad 210 = 84 + 126 = 210 \;\;\checkmark \]
\[ \binom nk = \binom{n-1}{k-1} + \binom{n-1}{k} \]
Exercise 14.8. [Proof] (The club identity.) From \(n\) people, form a club consisting of one leader plus any set (possibly empty) of additional members. Count the clubs in two ways — leader first, then members; and size-\(k\) club first, then its leader — and conclude that
\[ \sum_{k=1}^{n} k\binom nk = n\,2^{\,n-1}. \]
Proof. Suppose you have \(n\) people and you want to form a club with one leader plus any set (possibly empty) of additional members.
First we have \(n\) ways to choose a leader, and the \(2^{\,n-1}\) possible subsets from the remaining members to form additional members: \(n\,2^{\,n-1}\).
Alternatively this is the same as creating a size-\(k\) club — \(\binom nk\) ways to do that — and then making one of them a leader, \(k\) to choose from, so \(\sum \binom nk \cdot k\), \(1 \le k \le n\). Thus
\[ \sum_{k=1}^{n} k\binom nk = n\,2^{\,n-1}. \qquad \square \]
Exercise 14.9. [Proof, \(\star\)] (Stars and bars.) Show that the number of ways to place \(k\) indistinguishable balls into \(n\) labeled bins — equivalently, the number of unordered samples of size \(k\) drawn with replacement from \(n\) objects — is \(\binom{n+k-1}{k}\). (Encode a placement as a binary string: a 0 for each ball and a 1 for each of the \(n-1\) walls between adjacent bins; show that placements correspond one-to-one to strings with \(k\) 0s and \(n-1\) 1s. Note why the divide-by-duplicates trick behind Proposition 14.5 does not apply directly here: the number of ordered placements per unordered placement is not constant.)
Proof. Let’s encode each sample/placement of \(k\) balls into \(n\) bins as a binary string: \(0\) for each ball and \(1\) for each of the \(n-1\) walls between adjacent bins. Thus each sample/placement is a binary string with \(k\) zeros and \(n-1\) ones.
How many such strings are those with such a pattern? It’s a binary string of length \((n-1) + k\) and we choose exactly \(k\) of them to be zero, hence
\[ \binom{n+k-1}{k}. \qquad \square \]