# Latex代写 | COMP2804: Discrete Structures

COMP2804: Discrete Structures
Assignment 4
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
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.
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. Coin Flips
You flip a fair coin, independently, six times. Consider the events
A = “the coin comes up heads at least four times”,
3/31/2020 Assignment 4
https://cglab.ca/~morin/teaching/2804/assn4.html 2/5
= “the number of heads is equal to the number of tails”,
= “there are at least four consecutive heads”.
Compute the following probabilities:
1.
2.
3.
4.
5.
2. Probability of 5 before 7
Consider the following model, which corresponds to repeatedly rolling two dice and and
stopping the first time .
You roll two 6-sided dice and . Consider the events
= “ ”
= “ ”
1. What is ?
3. Four-Door Monte Hall
Consider the following version of the Monte Hall Problem:
There are four doors numbered . Three of these doors have goats behind them. One
door has a sports car. You want to win the sports car.
You pick one door, uniformly at random and put a chalk mark on it. That door stays closed
for now.
Monte Hall opens a door , with , showing you a goat.
You get to pick any of the three unopened doors in and keep whatever is
behind it.
B
C
Pr(A)
Pr(B)
Pr(C)
Pr(A ∣ B)
Pr(C ∣ A)
d1 d2
d1 + d2 ∈ {5, 7}
d1 d2
A d1 + d2 = 7
B d1 + d2 = 5
C = A ∪ B
Pr(A ∣ C)
1,…, 4
i
j j ≠ i
{1, 2, 3, 4} ∖ {j}
3/31/2020 Assignment 4
https://cglab.ca/~morin/teaching/2804/assn4.html 3/5
1. Suppose you decide to stick with your first choice, . What is the probability that you win the
sports car?
2. Suppose you decide to choose one of three unopened doors 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
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 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 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 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
i
{1, 2, 3, 4} ∖ {j}
{1, 2, 3, 4} ∖ {i, j}
1/25
1/2
1/4
3/31/2020 Assignment 4
https://cglab.ca/~morin/teaching/2804/assn4.html 4/5
We have a cooler containing cider bottles and beer bottles. We can sample from this
cooler in two different ways:
with replacement: We take a uniformly-random bottle from the cooler, look at it and put it
back.
without replacement: We take a uniformly-random bottle from the cooler, drink it, and throw
the empty bottle into the recyling bin.
Suppose we repeatedly sample from the cooler and let be the number of samples up to and
including the first cider bottle.
1. What is if we use sampling with replacement?
2. What is 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 people are standing around in a circle holding hands. When we talk
about these people, we take indices modulo so that, for example . of these people
are sick, the rest are healthy.
1. Let be an integer. Pick a uniformly random and let denote the
number of sick people among the people . What is ?
2. Argue that if we have people standing around in a circle and of them are sick,
then there always exists consecutive people at least 4 of whom are healthy.
(This should be a bit surprising, since of these people are healthy but
of all people are sick.)
7.
Recall the games “First Head Wins” and “Second Head Wins” discussed in class on March 10th.
Consider the natural extension of these games to “
th Head Wins” for some integer .
1. Find the probability that Player 1 wins the game of “
2 n − 2
X
E(X)
E(X)
n p0,…, pn−1
n pn+5 = p5 s
k < 100 i ∈ {0,…, n − 1} X k p , ,…, i pi+1 pi+k−1 E(X) n = 70 s = 39 7 p ,…, i pi+6 4/7 > 1/2
39/70 > 1/2
N
N N ≥ 1
N
3/31/2020 Assignment 4
https://cglab.ca/~morin/teaching/2804/assn4.html 5/5
Hint: Watch the entire March 10th Lecture, including the final 10 minutes, which shows how to