$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$

Assignment 3 Solutions

Question 1

Three hats are on a table. One of the hats has $\$3$ under it, the others have nothing under them. You choose a hat uniformly at random and get to keep what you find there. Let $A$ be the event "the hat you picked has $\$3$ under it." What is $\Pr(A)$?
Nine hats are on a table. Three of the hats each have $\$1$ under them, the others have nothing under them. You choose three of the hats uniformly at random. For each $i\in\{0,1,2,3\}$, let $B_i$ be the event "the hats you picked have a total of $\$i$ under them." What are $\Pr(B_0)$, $\Pr(B_1)$, $\Pr(B_2)$, and $\Pr(B_3)$?

Answer 1

$\Pr(A)=1/3$
This is a uniform probability space of size $\binom{9}{3}=84$, so all we need to do is compute the size of each event. We start with the two easiest ones.
- There is only one way to get $\$3$, so $|B_3|=1$ therefore $\Pr(B_3)=1/\binom{9}{3}=1/84$.
- In order to get $\$0$, we have to choose our hats from the $6$ hats with nothing under them, so $|B_0|=\binom{6}{3}$, so $\Pr(B_0)=\binom{6}{3}/\binom{9}{3}=20/84=5/21$.
- To compute $|B_1|$ we use the Product Rule with this procedure: First choose one of the three hats with $\$1$ under it and then choose two of the $6$ hats with nothing under them. Therefore $|B_1|=\binom{3}{1}\cdot\binom{6}{2}=45$, so $\Pr(B_1)=45/84=15/28$.
- For $|B_2|$ we use the Product Rule again, and this time we get $|B_2|=\binom{3}{2}\cdot\binom{6}{1}=18$, so $\Pr(B_2)=18/84=3/14$

Question 2

A standard deck $\mathcal{D}$ of playing cards has $52$ cards, each of which has a suit in $\mathcal{S}=\{♠,♥,♦,♣\}$ and a rank in $\mathcal{R}=\{2,3,4,5,6,7,8,9,10,J,Q,K,A\}$. For each suit in $\mathcal{S}$ and each rank in $\mathcal{R}$, the deck has exactly one card with that suit and that rank, i.e., $\mathcal{D}=\mathcal{S}\times\mathcal{R}$.

A poker hand $H$ is a set of $5$ cards taken uniformly at random from a single deck.

A flush is a poker hand made up of cards all having the same suit. For example, $\{🃂,🃆,🃉,🃋,🃍\}$ is a flush (the suit is ♦). Let $A$ be the event "$H$ is a flush." What is $\Pr(A)$?
A straight is a poker hand made up of cards that appear sequentially in the order listed above. For example, $\{🂳,🃄,🂥,🂶,🂷\}$ is a straight. Let $B$ be the event "$H$ is a straight."" What is $\Pr(B)$.
A straight flush is a poker hand that is both a straight and a flush. For example, $\{🂧,🂨,🂩,🂪,🂫\}$ is a straight flush. What is $\Pr(A\cap B)$?

Answer 2

This is another uniform probability space, this time with size $\binom{52}{5}$.

We can compute $|A|$ with the Product Rule: Choose one of the $4$ suits and then choose $5$ of the $13$ cards with that suit. Therefore $|A|=4\cdot\binom{13}{5}$ and $\Pr(A)=|A|/\binom{52}{5}=33/16660$.
We can compute $|B|$ with the Product Rule: Choose the rank of the lowest card in the straight, which can be anything in $\{2,3,4,5,6,7,8,9,10\}$ and then choose one of the $4$ suits for each card in the straight. Therefore $|B|=9\cdot 4^5$ and $\Pr(B)=|B|/\binom{52}{5}=192/54145$.
Note: I will also accept answers that treat $A,2,3,4,5$ as a flush. In this case $|B|=10\cdot 4^5$ and $\Pr(B)=128/32487$.
The Product Rule works here again, but you only get to choose one suit for all the cards in the straight, so $|A\cap B|=9\cdot 4$ and $\Pr(A\cap B)=|A\cap B|/\binom{52}{5}=3/216580$.
Note: I will also accept answers that treat $A,2,3,4,5$ as a flush. In this case $|A\cap B|=10\cdot 4$ and $\Pr(A\cap B)=1/64974$.

Question 3

Blackjack (also called 21) is a card game where the me and the dealer each receive two cards from a standard deck of playing cards. I see both my cards but only see the dealer's second card. The cards or ranks $2,3,4,5,6,7,8,9,10$ have the obvious values; the cards of ranks $J,Q,K$ each count as $10$. The cards with rank $A$ can count as $1$ or $11$ depending on which value helps the hand the most. The winner is the player who gets a hand closest to $21$ without going over.

If the two cards I am dealt have a total value of $21$ then I get a blackjack, and I win! For example, if I am dealt $\{🃝,🂱\}$ or $\{🂺,🃑\}$ then I get a blackjack. Let $B$ be the event "I am dealt a blackjack." What is $\Pr(B)$?
In the casino version of blackjack, the rules for the dealer are simple. As long as the value of their hand is less than $17$ they must take another card. Sometimes this causes the dealer's hand to exceed $21$ in which case the dealer busts and I win. Suppose that my hand is currently $\{🂢,🂤\}$. The dealer has two cards, one of which is 🃆 and the other I can't see. Even though I am certain that the dealer's hand beats mine right now, I decide to do nothing else and hope that the rules cause the dealer to bust.
(Keep in mind that the dealer's hidden card and any other cards the dealer is forced to take now come from a deck of $49$ cards that does not include 🂢,🂤, or 🃆.)
1. Let $D$ be the event, "the dealer is forced to take at least one more card." For example, this happens when the dealer's hidden card is 🃝, so their hand has a value of $6+10<17$. What is $\Pr(D)$?
2. Let $X$ be the event, "the dealer is forced to take one more card and this card causes the dealer to bust." For example, this happens when the dealer's hidden card 🃝 and then they draw a 🃈, so their hand has a value of $6+10+8>21$. What is $\Pr(X)$?

Answer 3

For this question the only thing that matters is the two cards I am dealt, so this is a uniform probability space of size $\binom{52}{2}$. We can compute $|B|$ using the Product Rule and the observation that one of the cards I am dealt must be one of the $4$ aces and the other card must be in $\{10,J,Q,K\}\times \{♠,♥,♦,♣\}$. Therefore, $|B|=4\cdot 4\cdot 4=64$ and $\Pr(B)=64/\binom{52}{2}=32/663$.
For these two parts, three cards are already showing so any remaining choices come from a set of $49$ cards that are not showing.
1. The event $D$ occurs precisely when the dealer's hidden card has value $10$ or less. We can count these directly (remembering to not count the three cards that are already showing), but it's easier to use the Complement Rule. The only cards of rank greater than $10$ are the four aces, so there $49-4=45$ options for the dealer's hidden card that will force the dealer to draw another card. There $|D|=45$ and $\Pr(D)=45/49$.
2. The event $X$ depends on two cards: The dealer's hidden card and the next card to be drawn from the deck. There are $49$ choices for the hidden card and, once that is revealed, there are $48$ choices for the next card, so the sample space has size $49\cdot 48$.
  - The event $X$ can only occur if the value of the dealer's hand is currently at least $12$ and at most $16$. For each $i\in\{12,\ldots,16\}$, let $X_i$ be the event "The value of the dealer's hand is currently $X_i$ and the next card the dealer draws will make the dealer bust." By the Sum Rule, $|X|=\sum_{i=12}^{16}|X_i|$.
  - Consider $X_{12}$, which implies the dealer's hidden card is one of the $3$ remaining cards of rank $6$. In this case, the dealer will bust if the next card has a value of $10$. There are $3$ choices for the hidden card (it's one of the $3$ remaining rank-$6$ cards) and $4\times 4=16$ choices for the next card the dealer draws (anything in $\{10,J,Q,K\}\times \{♠,♥,♦,♣\}$ will make the dealer bust). Therefore $|X_{13}|=3\cdot 16=48$.
  - The analysis of $X_{13}$ is similar: the hidden card has to have rank $7$ and the next card can be anything in $\{9,10,J,Q,K\}\times \{♠,♥,♦,♣\}$. Therefore $|X_{13}|=4\cdot 5\cdot 4=80$.
  - The analysis of $X_{14}$ has another thing to look out for. The dealer's hidden card must have rank $8$ and then the dealer will bust if they take any card in $\{8,9,10,J,Q,K\}\times \{♠,♥,♦,♣\}$. This latter set has size $6\cdot 4$ but, by now, one of the rank-$8$ cards is missing. This means that $|X_{14}|=4\cdot(6\cdot 4-1)=92$
  - The analysis of $X_{15}$ is similar to $X_{14}$, but we get $|X_{15}|=4\cdot(7\cdot 4-1)=108$.
  - For $X_{16}$ things change again. The event $X_{16}$ occurs when the dealer's hidden card is one of the $16$ rank-$10$ cards and the next card has rank at least $6$. By the time we get to the second step there is a missing rank-$10$ card and a missing rank-$6$ card. Therefore, $|X_{16}|=16\cdot (8\cdot 4-2)= 480$. So now we finish up with $|X|=\sum_{i=12}^{16}|X_i|=48+80+92+108+480=808$ and $\Pr(X)=808/(49\cdot 48)=101/294$

Question 4

I have a cooler containing $20$ bottles of beer: $18$ identical bottles of Hoegaarden and $2$ identical bottles of Grolsch. I reach into the cooler, remove a random bottle and pass it to my friend Michiel and then I reach into the cooler again, remove a random bottle and keep it for myself.

Describe the sample space $S$ for this experiment.
For each elementary event $\omega\in S$, determine $\Pr(\omega)$.
Let $A$ be the event "Michiel gets a bottle of Grolsch" and let $B$ be the event "I get a bottle of Hoegaarden."
What is $\Pr(A\cap B)$?
What is $\Pr(A\cup B)$?
Are the events $A$ and $B$ independent?

Answer 4

There is more than one answer for this question, but here one possible sample space. Let $X:=\{h_1,\ldots,h_{18},g_1,g_2\}$ be the set $18$ Hoegaarden and $2$ Grolsch bottles. Let $S:=\{(a,b):a,b\in X,\, a\neq b\}$ where $a$ denotes the bottle that Michiel gets and the $b$ denotes the bottle that I get.
The probability distribution in this sample space is uniform, so $\Pr(\omega)=1/|S|=1/(20\cdot 19)$ for each $\omega\in S$.
$A\cap B=\{(a,b):a\in\{g_1,g_2\}, b\in\{h_1,\ldots,h_{18}\}$. By the Product Rule, $|A\cap B|=2\cdot 18$, so \[ \Pr(A\cap B)=|A\cap B|/|S|=2\cdot 18/20\cdot 19=9/95 \enspace . \]
By the Product Rule, $|A|=2\cdot 19$ and $|B|=18\cdot 19$. By the principle of inclusion-exclusion, \[ |A\cup B|=|A|+|B|-|A\cap B| = 2\cdot 19 + 18\cdot 19 - 2\cdot 18 = 344 \] so $\Pr(A\cup B)= |A\cup B|/|S|=344/(20\cdot 19)=86/95$
We have everything we need to check if $\Pr(A\cap B)=\Pr(A)\cdot\Pr(B)$. When we do, we find that \[ Pr(A\cap B) = \frac{9}{95} \neq \frac{9}{100} = \frac{1}{10}\cdot\frac{9}{10} = \Pr(A)\cdot\Pr(B) \enspace . \] Therefore $A$ and $B$ are not independent.

Question 5

Let $(S,\Pr)$ be a probability space and let $A,B\subseteq S$ be two events, with $\Pr(A)>0$ and $\Pr(B)>0$.

Suppose you are told that $\Pr(A\cup B)=\Pr(A) + \Pr(B)$. Prove that $A$ and $B$ are not independent.
Suppose you are told that $\Pr(A\cap B) < \Pr(A)\cdot\Pr(B)$. What can you say about the relationship between $\Pr(A\cap\overline{B})$ and $\Pr(A)\cdot\Pr(\overline{B})$?

Answer 5

By the Principle of inclusion-exclusion, $\Pr(A\cup B)=\Pr(A)+\Pr(B)-\Pr(A\cap B)$. But we are told that $\Pr(A\cup B)=\Pr(A)+\Pr(B)$ so it must be that $\Pr(A\cap B)=0$. But $\Pr(A)>0$ and $\Pr(B)>0$ so $\Pr(A)\cdot\Pr(B)>0$. Therefore \[ \Pr(A)\cdot\Pr(B)>0=\Pr(A\cap B) \enspace , \] so $A$ and $B$ are not independent.
$A=(A\cap B)\cup (A\cap\overline{B})$ and the two sets on the right hand side of this equation are disjoint. So, by the Sum Rule $\Pr(A)=\Pr(A\cap B) +\Pr(A\cap\overline{B})$. Rearranging this we get \begin{align*} \Pr(A\cap\overline{B}) & = \Pr(A)-\Pr(A\cap B) \\ & > \Pr(A)-\Pr(A)\cdot\Pr(B) \\ & = \Pr(A)(1-\Pr(B)) \\ & = \Pr(A)\cdot\Pr(\overline{B}) \enspace , \end{align*} so we conclude that $\Pr(A\cap\overline{B}) > \Pr(A)\cdot\Pr(B)$.

Question 6

Consider the following game. Four players $P_1,\ldots,P_4$ each have a bag with one red hat and one blue hat in it. They turn off the lights and each player $P_i$ chooses a random hat $h_i$ (red or blue) from their own bag and puts it on. Then they turn the lights back on. No player knows the colour of the hat they are wearing but they can see the colours of the other three players' hats.

This is a cooperative game in which all the players win if at least two of the four players correctly guess the colour of their own hat.

(Before answering Part 2 of this question, make a guess about whether the answer will be different than the answer for Part 1.)

Suppose that each player $P_i$ independently and uniformly and randomly guesses a colour $g_i\in\{\text{red},\text{blue}\}$ and guesses that their hat has colour $g_i$.
If the players use this strategy, what is the probability that the players win the game?
Suppose that each player $P_i$ first looks at the colours of the three hats the other players are wearing and then guesses that their hat has the same colour as the majority. For example, if $P_1$ sees that hats $h_2$, $h_3$, and $h_4$ are red, blue, and red, then $P_1$ guesses that their own hat $h_1$ is red.
If the players use this strategy, then what is the probability that the players win the game?

Answer 6

For each $j\in\{0,\ldots,4\}$, let $A_j$ be the event "exactly $j$ players correctly guess their own hat colour". Then the probability that the players win the game is \begin{align*}
\Pr(A_2\cup A_3\cup A_4) & = \Pr(A_2)\cup\Pr(A_3)\cup\Pr(A_4) \\ & = \binom{4}{2}/16 + \binom{4}{3}/16 + \binom{4}{4}/16 \\ & = \frac{11}{16} \end{align*}
To analyze this strategy, carefully check the rules and realize that the only way the players can lose is if there are exactly two red hats and two blue hats. The probability that this happens is $\binom{4}{2}/16=6/16$. Therefore, by the Complement Rule, the probablity that the players win using this strategy is $1-6/16 = 10/16$.

Question 7

When studying probability, we usually define an experiment and then study the probability of one or more possible outcomes of the experiment. In maximum likelyhood estimation, we observe the outcome of an experiment and then try to determine which experiment is most likely to have produced that outcome. Here is a simple example.

We have a coin and two hypotheses about that coin:

H1: The coin has a head on one side and a tail on the other side
H2: The coin has tails both sides

We are clumsy and every time we try to turn the coin over to see the other side we drop it. When this happens, the coin lands on one of its two sides uniformly at random, so we're never sure if we're seeing the other side or the same side we were just looking at.

Suppose we toss the coin and observe that it comes up heads. What is the probability of this outcome under H1? What is the probability of this outcome under H2?
Suppose we toss the coin and observe that it comes up tails. What is the probability of this outcome under H1? What is the probability of this outcome under H2?
Assuming that H1 or H2 is the correct hypothesis, describe and analyze a procedure (that may involve tossing the coin many times) that identifies the correct hypothesis, H1 or H2 with probability at least $999999/1000000$. More precisely, if the experiment is taking place under the rules of H1, then your procedure should output H1 with probability at least $999999/1000000$. If the experiment is taking place under the rules of H2, then your procedure should output H2 with probability at least $999999/1000000$

Answer 7

For each $i\in\{1,2\}$, we let $\Pr_i$ denote the probability function on hypothesis H$i$. If $A$ is the event "a coin toss comes up heads" then $\Pr_1(A)=1/2$ and $\Pr_2(A)=0$.
$\Pr_1(\overline{A})=1/2$ and $\Pr_2(\overline{A})=1$.
Toss the coin $n$ times. If all the tosses came up tails then output H2, otherwise output H1. Under hypothesis H1, this algorithm only outputs H2 if all $n$ coin tosses come up tails, which happens with probability $1/2^n$. Therefore, $\Pr_1(\text{output H2}) = 1/2^n$ and $\Pr_1(\text{output H1})=1-1/2^n$.
Under hypothesis H2, the algorithm always outputs H2, so $\Pr_2(\text{output H2}) = 1$ and $\Pr_2(\text{output H1}) = 0$.
Therefore, under hypothesis H2, the algorithm is correct with probability $1$ and under hypothesis H1, the algorithm is correct with probability $1-1/2^n$. Therefore, under either hypothesis, the algorithm is correct with probability at least $1-1/2^n$.

Question 8

Update: The first sentence of this question has been updated. The value of $n$ is odd, so the number of heads and number of talks are always different.

Let $n$ be an odd integer. In this question we want to prove the identity \[
\sum_{k=\lceil n/2\rceil}^n \binom{n}{k}/2^n=1/2 \] using a combinatorial proof, but when we do this with probability, we call it the probabilistic method. In particular, we'll define an experiment and an event $E$ such that \[
\sum_{k=\lceil n/2\rceil}^n \binom{n}{k}/2^n=\Pr(E)=1/2 \]

Suppose we toss a fair coin $n$ times. Each coin toss comes up heads or tails with equal probability and indepedently of all other coin tosses. Let $E$ be the event "the number of heads is greater than the number of tails".

Explain, in a sentence or two, why $\Pr(E)=1/2$.
For each $i\in\{0,\ldots,n\}$, let $E_i$ be the event "the coin came up heads exactly $E_i$ times". What is $\Pr(E_i)$?
Explain why $\Pr(E)=\sum_{k=\lceil n/2\rceil}^n \binom{n}{k}/2^n$

Answer 8

Since $n$ is odd the number of heads is never equal to the number of tails. Furthermore, there is complete symmetry between heads and tails in this question, so any argument you could make for one also applies to the other. In other words, $\Pr(E)=\Pr(\overline{E})$. By the Complement Rule $\Pr(E)+\Pr(\overline{E}) = 1$, so $\Pr(E)=\Pr(\overline{E})=1/2$.
The number of outcomes in which the coin comes up exactly $i$ times is the same as the number of bitstrings of length $n$ that contain exactly $i$ 1s, which is $\binom{n}{i}$. Therefore $|E_i|=\binom{n}{i}$ and $\Pr(E_i)=\binom{n}{i}/2^n$.
The event $E$ occurs precisely when we get $k>n/2$ heads. Therefore, by the Sum Rule $\Pr(E)=\sum_{k=\lceil n/2\rceil}^n\Pr(E_k)= \sum_{k=\lceil n/2\rceil}^n\binom{n}{k}/2^n$. Therefore, \[ \tfrac{1}{2} = \Pr(E) = \sum_{k=\lceil n/2\rceil}^n\binom{n}{k}/2^n \enspace . \]