# Latex代写 | COMP2804: Discrete Structures

这个作业是用Latex完成离散概率和蒙特霍尔问题

COMP2804: Discrete Structures

Assignment 4

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

Answer the following questions

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.

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 “

th Head Wins” for some integer .

1. Find the probability that Player 1 wins the game of “

th Head Wins”

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

analyze “Second Head Wins” in terms of the analysis already done for “First Head Wins”