COMP2804: Discrete Structures II
$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$

Assignment 3

The 5-107 Lottery

In the 5-107 Lottery you choose a set of $6$ distinct integers $\{x_1,\ldots,x_5,y\}$ from the set $\{1,2,3,\ldots,107\}$. $x_1,\ldots,x_5$ are called your main numbers and $y$ is your bonus number. On Friday night, the lottery machine draws a uniformly random $5$-number subset $\{z_1,\ldots,z_5\}$ from $\{1,\ldots,107\}$. You buy one lottery ticket with your favourite $6$ numbers.

Big Jackpot

You win a Big Jackpot if $\{x_1,\ldots,x_5\}=\{z_1,\ldots,z_5\}$. What is the probability that you win the Big Jackpot?

Solution: The sample space for this question is the set $S$ of all $\binom{107}{5}$ $5$-element subsets of $\{1,\ldots,107\}$. An element in $S$ represents the numbers $\{z_1,\ldots,z_5\}$ chosen by the machine. This is a uniform sample space, so $\Pr(\omega)=1/|S|=1/\binom{107}{5}$ for each $\omega\in S$. Let $A$ be the event "you win the Big Jackpot". Then $\Pr(A)=\Pr(\{x_1,\ldots,x_5\})=1/\binom{107}{5}$.

Grading: Five marks for a correct answer, which mainly implies that the size of the sample space was computed correctly. It's hard to offer part marks here since that's really the only thing one needs to solve the question.

Little Jackpot

You win a Little Jackpot if $|\{x_1,\ldots,x_5\}\cap\{z_1,\ldots,z_5\}|=4$. What is the probability that you win a Little Jackpot?

Solution: Let $B$ be the event "you win a Little Jackpot" and, for each $i\in\{1,\ldots,5\}$, let $B_i$ be the event "$\{x_1,\ldots,x_5\}\cap\{z_1,\ldots,z_5\}=\{x_1,\ldots,x_5\}\setminus\{x_i\}$. In words, $B_i$ is the event "all your numbers matched except for $x_i$". Clearly the events $B_1,\ldots,B_5$ are pairwise disjoint. Therefore $\Pr(B)=\Pr(\bigcup_{i=1}^5 B_i)=\sum_{i=1}^5 \Pr(B_i)$, by the Sum Rule.

Now we just need to figure out $\Pr(B_i)=|B_i|/|S|=|B_i|/\binom{107}{5}$. Without loss of generality, we focus on $\Pr(B_5)$. In words, the event $B_5$ happens when $\{z_1,\ldots,z_5\}$ is a $5$-element subset of $\{1,\ldots,107\}\setminus\{x_5\}$ that contains $\{x_1,\ldots,x_4\}$. In other words $\{z_1,\ldots,z_5\}=\{x_1,\ldots,x_4,z_5\}$, where $z_5$ is any integer in the $102$-element set $\{1,\ldots,107\}\setminus\{x_1,\ldots,x_5\}$. Therefore $|B_5|=\binom{102}{1}=102$. There is nothing special about $x_5$ in this argument, so \[ \Pr(B_1)=\Pr(B_2)=\cdots=\Pr(B_5)=|B_5|/\binom{107}{5}=102/\binom{107}{5} \enspace . \] Now we can finish off what we started with \[ \Pr(B)=\Pr\left(\bigcup_{i=1}^5 B_i\right)=\sum_{i=1}^5 \Pr(B_i)=5\cdot\Pr(B_5)=510/\binom{107}{5} \enspace . \]

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error.

Bonus Jackpot

If you win a Little Jackpot and $y\in\{z_1,\ldots,z_5\}$, then you win a Bonus Jackpot. What is the probability that you win a Bonus Jackpot?

Solution:
Let $C$ be the event "you win a Bonus Jackpot" and, for each $i\in\{1,\ldots,5\}$, let $C_i$ be the event "$\{z_1,\ldots,z_5\}=\{x_1,\ldots,x_5,y\}\setminus\{x_i\}$. In words, $C_i$ is the event "you win the Bonus Jackpot because all your numbers matched except for $x_i$ and the machine picked your bonus number $y$". Just like the last question, $C_1,\ldots,C_5$ are pairwise disjoint, so $\Pr(C)=\Pr(\bigcup_{i=1}^5 C_i)=\sum_{i=1}^5 \Pr(C_i)$, by the Sum Rule. Also, like the last question, we can focus on $\Pr(C_5)$ since there is nothing special about $x_5$.

But now, $C_5$ is easy to describe. It happens precisely when $\{z_1,\ldots,z_5\}=\{x_1,\ldots,x_4,y\}$. Therefore, $|C_5|=1$ and $\Pr(C_5)=1/\binom{107}{5}$. Therefore, \[ \Pr(C)=\Pr\left(\bigcup_{i=1}^5 C_i\right)=\sum_{i=1}^5 \Pr(C_i)=5\cdot\Pr(C_5)=5/\binom{107}{5} \enspace . \]

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error.

Question 2

I have a card game with $100$ cards. For each $i\in\{1,\ldots,100\}$ there is a card with the number $i$ printed on it. I take 5 cards from the deck and get: $\{56, 55, 46, 1, 33\}$. You take a uniformly random $5$-element subset from the remaining cards.

Highest card wins

What is the probability that my highest card (56) is higher than your highest card?

Solution: The sample space $S$ here represents the $5$ cards in your hand, and it's a uniformly random $5$-element subset of the $95$-element set $\{1,\ldots,100\}\setminus \{56, 55, 46, 1, 33\}$. Therefore $|S|=\binom{95}{5}$ and $\Pr(\omega)=1/|S|=1/\binom{95}{5}$ for each $\omega\in S$.

Let $A$ be the event "your highest card is lower than $56$". Then $A$ occurs if and only if your cards are a $5$-element subset of the $51$-card set $\{1,\ldots,54\}\setminus\{1,46,33\}$. The number of such subsets is $|A|=\binom{51}{5}$, so \[ \Pr(A)=\frac{|A|}{|S|}=\frac{\binom{51}{5}}{\binom{95}{5}} = \frac{55930}{1107249} \approx 0.040542612329723865 \enspace . \]

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error.

Highest versus lowest

What is the probability that my highest card (56) is lower than your lowest card?

Solution: This is similar to the last question. Let $B$ be the event "your lowest card is higher than $56$". Then $B$ contains every $5$-element subset of $44$-element set $\{57,\ldots,100\}$, so $|B|=\binom{44}{5}$ and \[ \Pr(B)=\frac{\binom{44}{5}}{\binom{95}{5}} = \frac{155144}{8277217} \approx 0.018743497965560164 \enspace . \]

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error.

Second-highest versus second-highest

What is the probability that my second-highest card ($55$) is higher than your second highest card?

Solution: Let $C$ be the event "your second highest card is lower than $55$". We break $C$ up into two disjoint events, so that we can use hte Sum Rule:

  1. $C_0$ is the event "all your cards are lower than $55$". This is actually the same as the event $A$ in the first part of the problem, so $\Pr(C_0)=\Pr(A)=\binom{51}{5}/\binom{100}{5}$.
  2. $C_1$ is the event "one of your cards is higher than $55$ and the other $4$ are lower than $55$". We can compute $|C_1|$ using the Product Rule. We can choose one number $z_1$ from the set $44$-element set $\{57,\ldots,100\}$ and then choose $z_2,\ldots,z_5$ to be a $4$-element subset of the $51$-element set $\{1,2,\ldots,54\}\setminus\{1,33,46\}$. Therefore, $|C_1|=44\cdot\binom{51}{4}$.

Therefore \begin{align*} \Pr(C) & = \Pr(C_0\cup C_1) \\ & = \Pr(C_0)+\Pr(C_1) & \text{(Sum Rule)} \\ & = \frac{\binom{51}{5}}{\binom{100}{5}} + \frac{|C_1|}{|S|} \\ & = \frac{\binom{51}{5}}{\binom{95}{5}} + \frac{44\cdot\binom{51}{4}}{\binom{95}{5}} \\ & = \frac{1906380}{8277217} & \text{(Using Python)} \\ & \approx 0.2303165423837505 & \text{(Using a calculator)} \end{align*}

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error.

National-Public redux

NPR-1

You play a game where you roll an $8$-sided die $8$ times and you win if you roll $8$ at least once. What is the probability that you win?

Solution: For this question, the sample space $S:=\{1,\ldots,8\}^8$, $|S|=8^8$ and this is a uniform probability space, so $\Pr(\omega)=1/|S|=1/8^8$ for each $\omega\in S$. Let $E$ be the event "I win the game". The easiest thing to do here is to compute $\Pr(\overline{E})$ and use the Complement Rule. If we never roll an $8$, then each of the $8$ roles is in $\{1,\ldots,7\}$, so $\overline{E}=\{1,\ldots,7\}^8$ and $\Pr(\overline{E})=|\overline{E}|/|S|=(7/8)^8$. Therefore \[ \Pr(E)=1-\Pr(\overline{E}) = 1-\frac{|\overline{E}|}{|S|}= 1-\left(\frac{7}{8}\right)^8 = \frac{11012415}{16777216}\approx 0.6563910841941833 \]

NPR-2

You play a game where you roll an $8$-sided die $16$ times and you win if you roll $8$ at least twice. What is the probability that you win?

Solution: For this question, the sample space $S:=\{1,\ldots,8\}^{16}$, $|S|=8^{16}$ and this is a uniform probability space, so $\Pr(\omega)=1/|S|=1/8^{16}$ for each $\omega\in S$. Let $E$ be the event "I win the game". The easiest thing to do here is to compute $\Pr(\overline{E})$ and use the Complement Rule. To compute $\Pr(\overline{E})$, we will partition $\overline{E}$ into two disjoint events and use the Sum Rule:

  1. Let $\overline{E}_0$ be the event "I roll 8 zero times". Then $|\overline{E}_0|=7^{16}$.
  2. Let $\overline{E}_1$ be the event "I roll 8 exactly once". We can compute $|\overline{E}_1|$ using the Product Rule: First choose which of the $16$ rolls will be an $8$ and then a value in $\{1,\ldots,7\}$ for each of the $15$ other rolls. Therefore, $|\overline{E}_1|=16\cdot 7^{15}$.

We finish with \begin{align*} \Pr(E) & =1-\Pr(\overline{E}) & \text{(Complement Rule)} \\ & = 1-(\Pr(\overline{E}_0) + \Pr(\overline{E}_1)) & \text{(Sum Rule)} \\ & = 1-\left(\frac{|\overline{E}_0| + |\overline{E}_1|}{|S|}\right) & \text{(Uniform probability space)} \\ & = 1-\left(\frac{7^{16} + 16\cdot 7^{15}}{8^{16}}\right) \\ & = 1-\left(\frac{172281061981967}{281474976710656}\right) & \text{(Python)} \\ & \approx 0.6120652855016111 \end{align*}

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error.

A Drinking Game

Michiel and Pat are on the balcony with a cooler that has 20 bottles of beer in it: ten bottles of lager and ten bottles of IPA. They play a game where Pat takes a random beer from the cooler, drinks it, and throws the bottle off the balcony, then Michiel does the same. They do this for two rounds, until the neighbours call the police.

First IPA Wins (Pat)

In the game of First IPA wins, the person who drinks the first bottle of IPA is the winner (this game can end in a draw if no one drinks an IPA). What is the probability that Pat wins this game?

Solution: There are different ways to setup the sample space here, but one of the easiest is to define the bottle set $B=\{I_1,\ldots,I_{10},L_1,\ldots,L_{10}\}$. Then playing the game corresponds to choosing an ordered $4$-element subset of $B$ which represents the order in which four bottles of beer are drank (drunk?). The size of the resulting sample space $S$ is then $20\cdot 19\cdot 18\cdot 17=20!/16!$. (We showed this when proving that $\binom{n}{k}=n!/(k!(n-k)!)$.) This is a uniform sample space, which will make things easier.

Let $P$ be the event "Pat wins the game of First IPA Wins". Partition $P$ into the two disjoint events:

  1. $P_1$ is the event "Pat wins in the first round". Then $|P_1|=10\cdot 19\times 18\times 17=\tfrac{1}{2}|S|$ since $P_1$ occurs precisely when Pat chooses one of the $10$ IPA bottles in the first round, after which anything goes.
  2. $P_2$ is the event "Pat wins in the second round". Then $|P_2|=10\cdot 9\cdot 10\cdot 17$ since $P_2$ happens when Pat drinks one of the 10 lagers, then Michiel drinks one of the 9 remaining lagers, then Pat drinks one of the 10 IPA, after which anything goes.

Since $P_1$ and $P_2$ are disjoint and $P=P_1\cup P_2$, \begin{align*} \Pr(P) & =\Pr(P_1\cup P_2) \\ & = \frac{|P_1\cup P_2|}{|S|} \\ & = \frac{|P_1|+|P_2|}{|S|} \\ & = 1/2 + \frac{10\cdot 9\cdot 10\cdot 17}{20\cdot 19\cdot 18\cdot 17} \\ & = 12/19 \approx 0.6315789 \end{align*}

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error.

First IPA wins (Michiel)

What is the probability that Michiel wins the game of First IPA wins?

Solution: Let $M$ be the event "Michiel wins the game of First IPA Wins". We partition $M$ into two events so that we can use the Sum Rule.

  1. $M_1$ is the event "Michiel wins in the first round". Then $|M_1|=10\cdot 10\cdot 18\cdot 17$ since $M_1$ occurs when Pat drinks one of the 10 lagers, then Michiel drinks one of the ten IPA, after which anything goes.
  2. $M_2$ is the event "Michiel wins in the second round". Then $|M_2|=10\cdot 9\cdot 8\cdot 10$ since $M_2$ occurs when Pat drinks one of the 10 lagers then Michiel drinks one of the $9$ remaining lagers, then Pat drinks one of the $8$ remaining lagers, then Michiel drinks one of the $10$ IPA.

Since $M_1$ and $M_2$ are disjoint and $M=M_1\cup M_2$, we proceed as above to get \[ \Pr(M)=\frac{|M_1|+|M_2|}{|S|} = \frac{10\cdot 10\cdot 18\cdot 17+10\cdot 9\cdot 8\cdot 10}{20\cdot 19\cdot 18\cdot 17} = 105/323 \approx 0.32507 \]

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error. For this, and the next couple of questions, students may have defined (even implicitly) a different sample space in which the game ends as soon as there is a winner. Then they use a ``decision-tree'' argument in which they derive that $\Pr(P_1)=10/20$ since with probability $10/20$ the first beer Pat drinks is an IPA. This kind of argument is ok too, provided that they get the correct answer.

Second IPA Wins (Pat)

In the game of Second IPA wins, the person who drinks the second bottle of IPA is the winner. What is the probability that Pat wins this game?

Solution:

Let $P$ be the event "Pat wins the game of Second IPA Wins". We will use the Sum Rule again, with the following two events:

  1. $P_1$ is the event "Pat drinks the first IPA and the second IPA". Then $|P_1|=10\cdot 10\cdot 9\cdot 17$ since $A_1$ occurs when Pat drinks one of the 10 IPA, then Michiel drinks one of the ten lagers, then Pat drinks one of the 9 remaining IPAs, then anything goes.
  2. $P_2$ is the event "Michiel drinks the first IPA and Pat drinks the second IPA". Then $|P_2|=10\cdot 10\cdot 9\cdot 17$ since $A_2$ occurs when Pat drinks one of the 10 lagers, then Michiel drinks one of the 19 IPAs then Pat drinks one of the 9 remaining IPAs then anything goes.

Then, \[ \Pr(P) = \Pr(P_1\cup P_2) =\frac{|P_1\cup P_2|}{|S|} =\frac{10\cdot 10\cdot 9\cdot 17+10\cdot 10\cdot 9\cdot 17}{20\cdot 19\cdot 18\cdot 17} = \frac{5}{19} \approx 0.2631578947368421 \enspace . \]

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error.

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error. A decision-tree style of argument is also acceptable here, provided that it gives the correct answer.

Second IPA Wins (Michiel)

What is the probability that Michiel wins the game of Second IPA Wins?

Solution: Let $M$ be the event "Michiel wins the game of Second IPA Wins". We will use the Sum Rule again, with the following two events:

  1. $M_0$ is the event "Michiel wins in the first round". Then $|M_0|=10\cdot 9\cdot 18\cdot 17$ since $M_0$ occurs when Pat drinks one of the $10$ IPA, then Michiel drinks one of the $9$ remaining IPA, after which anything goes.
  2. $M_1$ is the event "Michiel drinks the first IPA and the second IPA". Then $|M_1|=10\cdot 10\cdot 9\cdot 9$.
  3. $M_2$ is the event "Pat drinks the first IPA and Michiel drinks the second IPA". We can further partition $M_2$ into two events $M_{2,1}$ and $M_{2,2}$ depending on whether Pat drinks the IPA in the first or second round.
  4. $|M_{2,1}|=10\cdot 10\cdot 9\cdot 9$ since $M_{2,1}$ occurs when Pat drinks one of the 10 IPAs, then Michiel drinks one of the 10 lagers, then Pat drinks one of the 9 remaining lagers, then Michiel drinks one of the 9 remaining IPAs.
  5. $|M_{2,2}|=10\cdot 9\cdot 10\cdot 9$ since $M_{2,2}$ occurs when Pat drinks one of the 10 lagers, then Michiel drinks one of the $9$ remaining lagers, then Pat drinks one of the 10 IPAs, then Michiel drinks one of the 9 remaining IPAs.

(Notice that $|M_1|=|M_{2,1}|=|M_{2,2}|$.) Then \begin{align*} \Pr(M) & = \Pr(M_0\cup M_1\cup M_{2,1}\cup M_{2,2}) \\ & = \frac{|M_0\cup M_1\cup M_{2,1}\cup M_{2,2}|}{|S|} \\ & = \frac{|M_0|+|M_1|+|M_{2,1}|+|M_{2,2}|}{|S|} & \text{(Sum Rule)} \\ & = \frac{10\cdot 9\cdot 18\cdot 17 + 3\cdot 10\cdot 10\cdot 9\cdot 9}{20\cdot 19\cdot 18\cdot 17} \\ & = 144/323 \approx 0.4458204334365325 \\ \end{align*}

Grading: Five marks for a complete and correct answer, with justification. You may give partial marks if the reasoning was correct but they made some calculation error. A decision-tree style of argument is also acceptable here, provided that it gives the correct answer.

Are Most Horses Red?

I imported a state of the art gashapon machine from Japan that contains $1000$ capsules, each with a toy horse in it. When I put a dollar into the machine it gives me a random capsule that I can open and check the colour of the horse inside it. The seller claims that half capsules contain a red horse and half the capsules contain a brown horse, but I've read reviews from people complaining that their machines contain 900 red horses and only 100 brown horses.

This leads to two hypotheses:

  1. $H_0$: My machine contains 500 red horses and 500 brown horses.
  2. $H_1$: My machine contains 900 red horses and 100 brown horses.

For any experiment I do, the hypothesis $H_0$ defines a probability function $\Pr_0$ and the hypothesis $H_1$ defines a different probability function $\Pr_1$.

I only have $\$3$ to figure out which of these hypotheses is more likely.

A dumb test

Suppose I buy three capsules from the machine. Let $A$ be the event "the three capsules I bought contain more red horses than brown horses". Compute $\Pr_0(A)$ and $\Pr_1(A)$.

Solution: The event $A$ is equivalent to "the three capsules I bought contain $2$ or $3$ red horses".

The complementary event $\overline{A}$ is "the three capsules I bought contain $2$ or $3$ brown horses". Under hypothesis 0, there is complete symmetry between red and brown, so $\Pr_0(A)=\Pr_0(\overline{A})$. Since $\Pr_0(A)+\Pr_0(\overline{A})=1$, this means $\Pr_0(A)=\Pr_0(\overline{A})=1/2$.

The analysis under hypothesis $H_1$ takes a bit more work. Split $A$ into the two events $A_2$ and $A_3$ depending on whether I get $2$ or $3$ red horses, respectively. Then \[ \Pr_1(A_2)=\frac{3\times 900\times 899\times 100}{1000\times 999\times 998} \] and \[ \Pr_1(A_3) = \frac{900\times 899\times 898}{1000\times 999\times 998} \] so \[ \Pr_1(A)=\Pr_1(A_2) + \Pr_1(A_3) = \frac{3\times 900\times 899\times 100+900\times 899\times 898}{1000\times 999\times 998} = \frac{538501}{553890} \approx 0.9722165050822366 \]

A better test

Describe and analyze an experiment I can run that costs only $\$3$ and has the following properties:

Solution: There's really only one reasonable test. Buy three capsules. If they all contain red horses, guess $H_1$, otherwise guess $H_0$. In the language of the previous answer, if event $A_3$ occurs then guess $H_1$, otherwise guess $H_0$.

If $H_1$ is correct, then we're running the experiment with probability function $\Pr_1$, and we already know: \[ \Pr_1(A_3) = \frac{900\times 899\times 898}{1000\times 999\times 998} = \frac{403651}{553890} \approx 0.7287566123237466 > 1/2 \enspace . \]

If $H_0$ is correct, then we're running the experiment with probability function $\Pr_0$ and we get \[ \Pr_0(A_3) = \frac{500\times 499\times 498}{1000\times 999\times 998} = \frac{83}{666} \approx 0.12462462462462462 < 1/2 \enspace . \] so $\Pr_0(\overline{A}_3)=1-\Pr_0(A_3)>1/2$.

Grading: Full marks if they describe and analyze the test given in the sample solution, showing that the probability that the test gives the correct answer under hypothesis 0 is greater than $1/2$ and the probability that the test gives the correct answer under hypothesis $1$ is also greater than $1/2$. Note: Some thrifty students have noticed that there is an even cheaper test: Buy two horses: If they're both red, guess $H_1$, otherwise guess $H_0$. In this case, the probability of being correct under hypothesis $H_0$ is $1-(500\cdot 499)/(1000\cdot999)\approx 3/4$ and the probability of being correct under hypothesis $H_1$ is $(900\cdot899) / (1000\cdot 999)\approx 81/100$. Any student with this answer should also receive full marks.

Three events

Let $A,B,C\subseteq S$ be three events in a probability space $(S,\Pr)$ where

  1. $S=A\cup B$,
  2. $\Pr(A)=\Pr(B)=2/3$,
  3. $\Pr(C)=2/5$,
  4. $\Pr(A\cap C)=\Pr(B\cap C)=1/3$, and
  5. $\Pr(A\cap B\cap C)=1/6$.

Notice: This question is broken because
\begin{align*} \Pr(C) & \ge \Pr(C\cap (A\cup B)) & \text{(since $C\cap (A\cup B)\subseteq C$)}\\ & = \Pr((C\cap A)\cup (C\cap B)) \\ & = \Pr(A\cap C)+\Pr(B\cap C)-\Pr(A\cap B\cap C) & \text{(principle of inclusion-exclusion)}\\ & = 1/3+1/3-1/6 \text{(given in the question)}\\ & = 1/2 \\ & > \Pr(C) & \text{(given in the question)} . \end{align*}

All students should receive $5/5$ for each of the two parts of this question, even if they didn't complete them. That is, they should receive 10 free marks.

$A$ versus $C$ and $B$ versus $C$

Are the events $A$ and $C$ independent? Are the events $B$ and $C$ independent?

$(A\cup B)$ versus $C$

Are the events $(A\cup B)$ and $C$ independent?

image/svg+xml