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

Assignment 3

Question 1

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)$?
2. 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)$?

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.

1. 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)$?
2. 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)$.
3. 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)$?

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.

1. 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)$?

2. 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)$?

Note: Actually computing the exact value of $\Pr(\text{"the dealer busts"})$ in this situation takes a fair bit of work (or a computer program). This is a good example of how a simple game can lead to a time-consuming probability question. Luckily, a number of blackjack strategy charts exist that tell you what your optimal move is for any given situation. In some casinos dealers will even give you one of these sheets if they see you struggling.

Caution: Most casinos don't use a single deck of cards. They use at least 6 decks all shuffled together and throw away all the decks after playing through about half of the cards.)

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.

1. Describe the sample space $S$ for this experiment.
2. 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."
3. What is $\Pr(A\cap B)$?
4. What is $\Pr(A\cup B)$?
5. Are the events $A$ and $B$ 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$.

1. Suppose you are told that $\Pr(A\cup B)=\Pr(A) + \Pr(B)$. Prove that $A$ and $B$ are not independent.
2. 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})$?

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.)

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?
2. 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?

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.

1. 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?
2. 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?
3. 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$

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".

1. Explain, in a sentence or two, why $\Pr(E)=1/2$.
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)$?
3. Explain why $\Pr(E)=\sum_{k=\lceil n/2\rceil}^n \binom{n}{k}/2^n$