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

Administrivia

Meat

ID

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

1. Coin Flips

You flip a fair coin, independently, six times. Consider the events
$A$ = “the coin comes up heads at least four times”,
$B$ = “the number of heads is equal to the number of tails”,
$C$ = “there are at least four consecutive heads”.

Compute the following probabilities:

  1. $\Pr(A)$
  2. $\Pr(B)$
  3. $\Pr(C)$
  4. $\Pr(A\mid B)$
  5. $\Pr(C\mid A)$

2. Probability of 5 before 7

Consider the following model, which corresponds to repeatedly rolling two dice $d_1$ and $d_2$ and stopping the first time $d_1+d_2\in\{5,7\}$.

You roll two 6-sided dice $d_1$ and $d_2$. Consider the events
$A$ = “$d_1+d_2=7$”
$B$ = “$d_1+d_2=5$”
$C=A\cup B$

  1. What is $\Pr(A\mid C)$?

3. Four-Door Monte Hall

Consider the following version of the Monte Hall Problem:

Answer the following questions

  1. Suppose you decide to stick with your first choice, $i$. What is the probability that you win the sports car?
  2. Suppose you decide to choose one of three unopened doors $\{1,2,3,4\}\setminus\{j\}$ uniformly at random. What is the probability that you win the sports car?
  3. Suppose you decide to choose one of the two unopened and unmarked doors $\{1,2,3,4\}\setminus\{i,j\}$ uniformly at random. What is the probability that you win the sports car?

4. Estimating Genetic Diseases

One out of 25 healthy people carries a single gene for cystic fibrosis (CF), these people are called carriers and healthy people without a CF gene are called non-carriers. A uniformly-chosen random healthy person has probability $1/25$ of being a carrier.

A person with two CF genes is not healthy; they are sick (with cystic fibrosis). The child of a carrier has probability $1/2$ of inheriting a CF gene from that parent. The child of two carriers inherits each of their parents CF genes independently, so the child has probability $1/4$ of having CF.

  1. Two uniformly-chosen random healthy people have a child together. What is the probability that the child has CF?
  2. Two uniformly-chosen random healthy people have a child together. What is the probability that the child is a healthy non-carrier?
  3. A carrier has a child with a uniformly-chosen random healthy person. What is the probability that the child has CF?
  4. A carrier has a child with a uniformly-chosen random healthy person. What is the probability that the child is a (healthy) carrier?
  5. Two uniformly-chosen healthy people have a baby. A quick blood test, administered minutes after birth, shows that the baby has at least one CF gene, but gives no other information. What is the probability that the baby has CF?

(This question is based a personal story during which I learned that there are genetic counsellors, a big part of whose job is computing these conditional probabilities to help guide prospective parents in making informed decisions.)

5. Sampling With and Without Replacement

We have a cooler containing $2$ cider bottles and $n-2$ beer bottles. We can sample from this cooler in two different ways:

Suppose we repeatedly sample from the cooler and let $X$ be the number of samples up to and including the first cider bottle.

  1. What is $\E(X)$ if we use sampling with replacement?
  2. What is $\E(X)$ if we use sampling without replacement?

(This question highlights a fact that beer, whisky, and wine connoisseurs know intuitively: sampling without replacement is more fun, but makes things harder to compute!)

6. Finding a Healthy Subring

A group of $n$ people $p_0,\ldots,p_{n-1}$ are standing around in a circle holding hands. When we talk about these people, we take indices modulo $n$ so that, for example $p_{n+5}=p_5$. $s$ of these people are sick, the rest are healthy.

  1. Let $k<100$ be an integer. Pick a uniformly random $i\in\{0,\ldots,n-1\}$ and let $X$ denote the number of sick people among the $k$ people $p_{i},p_{i+1},\ldots,p_{i+k-1}$. What is $\E(X)$?
  2. Argue that if we have $n=70$ people standing around in a circle and $s=39$ of them are sick, then there always exists $7$ consecutive people $p_i,\ldots,p_{i+6}$ at least 4 of whom are healthy. (This should be a bit surprising, since $4/7>1/2$ of these people are healthy but $39/70>1/2$ of all people are sick.)

7. $N$th Head Wins

Recall the games “First Head Wins” and “Second Head Wins” discussed in class on March 10th. Consider the natural extension of these games to “$N$th Head Wins” for some integer $N\ge 1$.

  1. Find the probability that Player 1 wins the game of “$N$th Head Wins”

Hint: Watch the entire March 10th Lecture, including the final 10 minutes, which shows how to analyze “Second Head Wins” in terms of the analysis already done for “First Head Wins”