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

If your browser has trouble rendering MathJaX, then use this PDF file

Administrivia

• Your assignment must be submitted as a single PDF file through cuLearn
• Late assignments will not be accepted under any circumstances. If you're unable to complete the assignment due to a valid and documented medical or personal situation then the weight of this assignment can be shifted to the weight of the remaining assignments.
• You are encouraged to collaborate on assignments, but at the level of discussion only. When writing your solutions, you must do so in your own words.
• Past experience has shown conclusively that those who do not put adequate effort into the assignments do not learn the material and have a probability near 1 of doing poorly on the exams.
• When writing your solutions:
  • You must justify your answers.
  • The answers should be concise, clear and neat.
  • When presenting proofs, every step should be justified.

Meat

1. ID

1. Make sure the first thing on page 1 of your assignment is your name and student number.

1. Probabilities of Poker Hands

These questions refer to a standard deck of 52 cards having 4 suits $\clubsuit, \spadesuit, \diamondsuit, \heartsuit$ and 13 ranks $2,3,4,5,6,7,8,9,10,J,Q,K,A$. You are dealt a 5-card hand from such a deck (so there are $\binom{52}{5}$ possible hands, each one is equally likely).

1. A flush is a hand consisting of 5 cards that all have the same suit. For example $\{2\spadesuit, 5\spadesuit, 10\spadesuit, J\spadesuit, A\spadesuit\}$ is a flush. What is the probability that your hand is a flush?
   Hint: The answer is $33/16660$
2. A straight is a hand consisting entirely of consecutive ranks. For example $\{8\spadesuit,9\diamondsuit,10\heartsuit,J\diamondsuit,Q\clubsuit\}$ is a straight. What is the probability that your hand is a straight?
   Hint: The answer is $192/54145$.
3. A pair is a hand that contains two (but not three) cards of the same rank. For example $\{2\diamondsuit, 3\spadesuit, 8\diamondsuit, 8\clubsuit, Q\heartsuit\}$ is a pair. What is the probability that your hand is a pair?
   Hint: The answer is $352/833$ or $1958/4165$ depending on whether or not you count hands that have 2 pairs in them.

Hint: Review the notes on uniform probability spaces (Oct 10, Section 5.4)

2. Drinking Warm Beer

We put 10 bottles of Molson Export and 3 bottles of Labatt 50 into the trunk of our black car on a hot summer day. We reach into the the cooler, pull out a random bottle $b_1$ and drink it. Then we reach into the cooler, pull out a second bottle $b_2$ and drink it.

1. Describe the sample space $S$ for this experiment.
2. For each outcome $\omega\in S$, determine $\Pr(\omega)$.
3. Let $A$ be the event "$b_1$ is a bottle of Molson Export" and let $B$ be the event "$b_2$ is a bottle of Labatt 50". Determine $\Pr(A)$ and $\Pr(B)$.
4. Are the events $A$ and $B$ independent? In other words, is $\Pr(A\mid B)=\Pr(A)$?

3. Three Dice of a Kind

Consider the following game: You roll six 6-sided dice $d_1,\ldots,d_6$ and you win if some number appears 3 or more times. For example, if you roll: $$(3, 3, 5, 4, 6, 6)$$ then you lose. If you roll $$(4, 1, 3, 6, 4, 4)$$ then you win.

1. What is the probability that you win this game?
   Hint: The answer is $119/324$

4. Dungeon and Pepys

For this problem you have a 12-sided die. Consider the following two games:

Game A. you roll the die 12 times and you win if you roll 12 at least once.
Game B. you roll the die 36 times and you win if you roll 12 at least three times.

1. What is the probability of winning Game A?
   Hint: The answer is $5777672071535/8916100448256$.
2. What is the probability of winning Game B?
   Hint: The answer is $$\frac{415770101669367370066325002723536855389}{708801874985091845381344307009569161216}$$
   Hint: Review the lecture on the Newton-Pepys Problem

5. Random pigeonholing

100 pigeons $p_1,\ldots,p_{100}$ fly into 500 labelled holes $h_1,\ldots,h_{500}$. Each pigeon picks a hole uniformly at random and independently from the choices of the other pigeons.

1. What is the probability that at least one hole contains at least 2 pigeons.
   Hint: The answer is approximately $0.9999758457295991$
2. What is the probability that at least one hole contains at least 3 pigeons.
   Hint: The answer is approximately $0.4361298523736379$.

Hint: Review the notes on the Birthday Paradox.

6. Rolling Snake Eyes

1. We roll two six-sided dice $d_1$ and $d_2$. What is the probability that we roll two ones. (i.e., the probability that $d_1=d_2=1$).
2. We roll two six-sided dice $d_1$ and $d_2$ and at least one of the dice comes up as a one. What is the (conditional) probability that we roll two ones.
3. We roll two six-sided dice $d_1$ and $d_2$ and at least one of the dice comes up as a one. What is the (conditional) probability that one of our dice came up 6.
4. We roll four six-sided dices $d_1,\ldots,d_4$ and at least one of these two events happened:
   X) $d_1=1$ and $d_3=1$; or
   Y) $d_2=1$ and $d_4=1$.
   What is the (conditional) probability that $d_1=1$ and $d_2=1$? (Hint: Review the lecture on Anil's two children (Oct 31st))

7. Randomized Leader Election

A group of $n$ people sit together and each one chooses a uniformly random integer in $\{1,\ldots,n\}$ independent of the others choices, so we have a sequence $(x_1,\ldots,x_n)\in \{1,\ldots,n\}^n$. Each person, $i$, announces their number $x_i$, and all people compute $m = \max\{x_i:i\in\{1,\ldots,n\}\}$. The algorithm succeeds if there is exactly one $i\in\{1,\ldots,n\}$ such that $x_i=m$. (In this case, person $i$ is declared the leader.)

Define $p_n$ as the probability that this algorithm succeeds with a group of $n$ people.

1. Compute $p_2$
2. Compute $p_3$
3. Derive a formula for $p_n$ that is valid for any integer $n\ge 1$. Use something like Python to evaluate $p_n$ for $n=100$.