$\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

ID

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

1. Rolling two D20

Consider what hapens when we roll two 20-sided dice $d_1$ and $d_2$ (so the sample space is $S=\{(d_1,d_2):d_1,d_2\in\{1,2,3,\ldots,20\}\}$ and $Pr(\omega)=1/|S|$ for each $\omega\in S$). Consider the following events:

• $A$ is the event "$d_1=13$"
• $B$ is the event "$d_1+d_2=15$"
• $C$ is the event "$d_1+d_2=21$"

Use the definitions of independence and conditional probability to answer these two questions:

1. Are the events $A$ and $B$ independent?
2. Are the events $A$ and $C$ independent?

2. Randomized Leader Election

A group of $n\ge 3$ people $x_0,\ldots,x_{n-1}$ stand around forming a circle facing inward so that $x_{(i+1)\bmod n}$ is standing to the right of $x_i$ for each $i\in\{0,\ldots,n-1\}$. They play the following game, called "Leader Election" that repeats the following two steps until only one or two people, "The Leaders" remain:

• For each $i\in\{0,\ldots,n-1\}$, person $i$, tosses a fair coin $c_i$.
• If $c_i=H$ and $c_{(i-1)\bmod n}=c_{(i+1)\bmod n} = T$ then person $i$ leaves the circle.

The two steps above are called a round of the game.

1. What is the maximum number of people who leave the game at the end of the first round?
2. We say that a person playing the game survives the first round if they don't leave. For a particular person $x_i$, what is the probability that $x_i$ survives the first round?
3. For a particular person $x_i$, what is the probability that Person $i$ survives the first $r$ rounds, for some integer $r <\log_2 (n/3)$? What is the expected number of people who survive the first $r$ rounds?

3. Sampling With Replacement

We have a biased coin that, when we toss it, comes up tails ($T$) with probability $2/n$ and comes up heads ($H$) with probability $1-2/n$. Imagine we toss this coin infinitely many times resulting in an infinite sequence $\pi_1,\pi_2,\ldots,\pi_\infty\in \{H,T\}^\infty$.

1. Let $X$ be the index of the first head in the sequence. That is, $\pi_1=\pi_2=\cdots=\pi_{X-1}=T$ and $\pi_X=H$. What is $\E[X]$?
2. Let $Y$ be the index of the first tail in the sequence. That is $\pi_1=\pi_2=\cdots=\pi_{X-1}=H$ and $\pi_X=T$. What is $\E[Y]$?

4. Sampling Without Replacement

We have $n-2$ beer bottles $b_1,\ldots,b_{n-2}$ and 2 cider bottles $c_1$ and $c_2$. Consider a uniformly random permutation $\pi_1,\ldots,\pi_{n}$ of these $n$ bottles (so that each of the $n!$ permutations is equally likely).

1. Let $X$ be the index of the first beer bottle in the permutation. That is, $\{\pi_1,\ldots,\pi_{X-1}\}\subseteq\{c_1,c_2\}$ and $\pi_X\in\{b_1,\ldots,b_n\}$. What is $\E[X]$?
2. Let $Y$ be the index of the first cider bottle in the permutation. That is $\{\pi_1,\ldots,\pi_{Y-1}\}\subseteq\{b_1,\ldots,b_n\}$ and $\pi_X\in\{c_1,c_2\}$. What is $\E[Y]$?

5. Doing (much) Better by Taking the Min

Let $X$ be a random variable that takes on the values in the set $\{1,\ldots,n\}$ that satisfies the inequality $\Pr(X\ge i)\le a/i$ for some value $a>0$ and all $i\in\{1,\ldots,n\}$.

Recall that (or convince yourself that) \[ \E(X) = \sum_{i=1}^n i\Pr(X=i) = \sum_{i=1}^n\Pr(X\ge i) \enspace . \]

1. Given what little you know so far, give the best upper bound you can on $\E(X)$.
2. Let $X_1$ and $X_2$ be two independent copies of $X$ and let $Z=\min\{X_1,X_2\}$. What can you say about $\Pr(Z \ge i)$?
3. Give the best upper bound you can on $\E(Z)$.
4. Use Euler's result on the Basel Problem to show that $\E(Z)$ has an upper bound that depends only on $a$ (and not on $n$).