University of Washington
Department of Mathematics
Homework 2 Solution
MATH 394: Probability I
Instructor: Arman Jahangiri
Submission: Single PDF on Gradescope
Deadline: 10:00 PM Pacific Time on the listed due date
This homework is worth 50 points.
Across the quarter, there are eight homework assignments, worth 400 points total. Homework assignments together account for 40% of the final course grade. Further course policies can be seen in the MATH 394 syllabus.
Please:
Each student is allotted six late days for the quarter. A late day extends a homework deadline by up to 24 hours without penalty. For example, submitting an assignment anytime between 10:01 PM on the due date and 10:00 PM the following day counts as one late day.
The following rules apply:
Once all late days have been exhausted, additional late submissions will incur a penalty of 10% per day, up to a maximum deduction of 50%. Assignments submitted more than five days late, or after solutions have been released, will not be accepted.
If a serious technical issue prevents a timely Gradescope submission, students may temporarily submit their assignment by email to the instructor at armanjg@uw.edu. In such cases:
Email submissions are intended only for genuine technical emergencies and should not be used as a substitute for timely Gradescope submission.
Problem 1.
Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 8.
Solution
(a) First choose the team of 2 people. This can be done in \[ \binom {12}{2} \] ways. After those two people have been chosen, there are 10 people left, and we need to divide them into two teams of 5. If we choose 5 of them for one team, the remaining 5 automatically form the other team. This gives \(\binom {10}{5}\) choices, but the two teams of size 5 have no labels, so this counts each split twice. Therefore the number of possible splits is \[ \binom {12}{2}\frac {\binom {10}{5}}{2} = 66\cdot \frac {252}{2} = 8316. \]
(b) Now all three teams have the same size, so none of the teams is distinguished by its size. If the teams were labeled, we could choose 4 people for the first team, then 4 of the remaining 8 for the second team, and then the last 4 people would form the third team. This gives \[ \binom {12}{4}\binom {8}{4}\binom {4}{4}. \] Since the three teams are not labeled, each actual split has been counted \(3!\) times. Thus the desired number is \[ \frac {1}{3!}\binom {12}{4}\binom {8}{4}\binom {4}{4} = \frac {12!}{(4!)^3 3!} = 5775. \]
Problem 2.
Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 20.
Show using a story proof that \[ { k \choose k} + { k+1 \choose k} + { k+2 \choose k} + \cdots + { n \choose k} = { n+1 \choose k+1}, \] where \(n\) and \(k\) are positive integers with \(n\ge k\). This is called the hockey stick identity.
Hint: Imagine arranging a group of people by age, and then think about the oldest person in a chosen subgroup.
Solution
Imagine \(n+1\) people arranged from youngest to oldest. We want to choose a subgroup of \(k+1\) people. If we ignore the order of the people, the number of possible subgroups is simply \[ \binom {n+1}{k+1}. \]
Now count the same subgroups according to who the oldest chosen person is. If the oldest chosen person is the \((j+1)\)-st person in the age order, then the remaining \(k\) members of the subgroup must all be chosen from the \(j\) people younger than that person. This can be done in \[ \binom {j}{k} \] ways. The oldest chosen person must have at least \(k\) people younger than them, and can range up to the oldest person in the whole group. Hence \(j\) ranges from \(k\) to \(n\). Summing over all possible choices of the oldest selected person gives \[ \binom {k}{k} + \binom {k+1}{k} + \binom {k+2}{k} + \cdots + \binom {n}{k}. \]
Both expressions count the same collection of subgroups of size \(k+1\). Therefore
Problem 3.
Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 43.
Show that for any events \(A\) and \(B\), \[ P(A)+P(B)-1 \le P(A\cap B) \le P(A\cup B) \le P(A)+P(B). \]
For each of these three inequalities, give a simple criterion for when the inequality is actually an equality. For example, give a simple condition such that \(P(A\cap B)=P(A\cup B)\) if and only if the condition holds.
Solution
The addition rule gives \[ P(A\cup B)=P(A)+P(B)-P(A\cap B). \] Since \(P(A\cup B)\le 1\), this identity implies \[ P(A)+P(B)-P(A\cap B)\le 1. \] Rearranging gives \[ P(A)+P(B)-1\le P(A\cap B). \] Equality holds here exactly when \(P(A\cup B)=1\), meaning that \(A\cup B\) occurs with probability one.
Next, since \[ A\cap B\subseteq A\cup B, \] monotonicity of probability gives \[ P(A\cap B)\le P(A\cup B). \] Equality holds exactly when the part of \(A\cup B\) outside \(A\cap B\) has probability zero. This part is the symmetric difference \[ (A-B)\cup (B-A). \] Thus equality holds exactly when \[ P\big ((A-B)\cup (B-A)\big )=0. \]
Finally, from the addition rule and the fact that \(P(A\cap B)\ge 0\), we get \[ P(A\cup B) = P(A)+P(B)-P(A\cap B) \le P(A)+P(B). \] Equality holds exactly when \[ P(A\cap B)=0. \]
Therefore all three inequalities hold, and the equality cases are as described above.
Problem 4.
Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 44.
Let \(A\) and \(B\) be events. The difference \(B-A\) is defined to be the set of all elements of \(B\) that are not in \(A\). Show that if \(A\subseteq B\), then \[ P(B-A)=P(B)-P(A), \] directly using the axioms of probability.
Solution
Since \(A\subseteq B\), the event \(B\) can be decomposed into two disjoint pieces, \[ B=A\cup (B-A). \] These two events are disjoint because \(B-A\) consists exactly of the outcomes in \(B\) that are not in \(A\). Therefore, by finite additivity, \[ P(B) = P(A\cup (B-A)) = P(A)+P(B-A). \] Rearranging this identity gives \[ P(B-A)=P(B)-P(A). \]
This proves the desired formula directly from the additivity axiom of probability.
Problem 5.
Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 50.
A card player is dealt a 13-card hand from a well-shuffled, standard deck of cards.
What is the probability that the hand is void in at least one suit? Here, “void in a suit” means having no cards of that suit.
Solution
There are \[ \binom {52}{13} \] equally likely 13-card hands. For each suit \(s\), let \(A_s\) be the event that the hand has no cards of suit \(s\). We want \[ P(A_{\spadesuit }\cup A_{\heartsuit }\cup A_{\diamondsuit }\cup A_{\clubsuit }). \]
We count this union by inclusion-exclusion. If one specified suit is missing, then all 13 cards must come from the remaining 39 cards, giving \[ \binom {39}{13} \] hands. There are 4 choices for the missing suit.
If two specified suits are missing, then all 13 cards must come from the remaining 26 cards, giving \[ \binom {26}{13} \] hands. There are \(\binom {4}{2}\) choices for the two missing suits.
If three specified suits are missing, then all 13 cards must come from a single suit. This is possible in \[ \binom {13}{13}=1 \] way for each choice of the three missing suits. There are \(\binom {4}{3}\) such choices. It is impossible for all four suits to be missing, since the hand has 13 cards.
Therefore the probability that the hand is void in at least one suit is \[ \frac { 4\binom {39}{13} - \binom {4}{2}\binom {26}{13} + \binom {4}{3}\binom {13}{13} }{ \binom {52}{13} }. \] Equivalently, \[ \frac { 4\binom {39}{13} - 6\binom {26}{13} + 4 }{ \binom {52}{13} }. \]
Problem 6.
Source: Blitzstein and Hwang, Introduction to Probability, Chapter 1, Problem 55.
A club consists of 10 seniors, 12 juniors, and 15 sophomores. An organizing committee of size 5 is chosen randomly, with all subsets of size 5 equally likely.
Solution
There are \(10+12+15=37\) students in the club, so the total number of possible committees of size 5 is \[ \binom {37}{5}. \]
(a) To have exactly 3 sophomores, we choose 3 of the 15 sophomores and then choose the remaining 2 committee members from the 22 students who are not sophomores. This gives \[ \binom {15}{3}\binom {22}{2} \] committees. Hence the desired probability is \[ \frac {\binom {15}{3}\binom {22}{2}}{\binom {37}{5}}. \]
(b) Now the committee must contain at least one senior, at least one junior, and at least one sophomore. We count by the triple \[ (s,j,p), \] where \(s\), \(j\), and \(p\) are the numbers of seniors, juniors, and sophomores on the committee. We need \[ s+j+p=5, \qquad s,j,p\ge 1. \] Thus the favorable committees are counted by \[ \sum _{\substack {s+j+p=5\\ s,j,p\ge 1}} \binom {10}{s}\binom {12}{j}\binom {15}{p}. \] Writing this out explicitly gives \[ \binom {10}{1}\binom {12}{1}\binom {15}{3} + \binom {10}{1}\binom {12}{2}\binom {15}{2} + \binom {10}{1}\binom {12}{3}\binom {15}{1} \] \[ + \binom {10}{2}\binom {12}{1}\binom {15}{2} + \binom {10}{2}\binom {12}{2}\binom {15}{1} + \binom {10}{3}\binom {12}{1}\binom {15}{1}. \] Dividing by the total number of committees gives the probability \[ \frac { \binom {10}{1}\binom {12}{1}\binom {15}{3} + \binom {10}{1}\binom {12}{2}\binom {15}{2} + \binom {10}{1}\binom {12}{3}\binom {15}{1} + \binom {10}{2}\binom {12}{1}\binom {15}{2} + \binom {10}{2}\binom {12}{2}\binom {15}{1} + \binom {10}{3}\binom {12}{1}\binom {15}{1} }{ \binom {37}{5} }. \]