Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science November 21, 2000 Professors Nancy Lynch and Srinivas Devadas

Problem Set 10

Due: 2:35pm in lecture, Tuesday, November 28, 2000.

Be sure to indicate your TA’s name clearly on the solutions you turn in.

————————————————————————————————————–

Self-study Read: Lecture notes, Rosen Sections 4.4 and 4.5. Self-study problems (not to be handed in): 4.4: 13, 33. 4.5: 19, 23. ————————————————————————————————————–

Policy on collaboration If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.

Problem 1 Suppose that 5 men out of 100, and 25 women out of 10,000 are colorblind. A colorblind person is chosen at random from a population with equal numbers of males and females. What is the probability of this person being male?

Solution: Let M be the event the person is male, F female, C colorblind. We are given Pr {C | M} =

\frac{5}{100} and Pr \{C | F \} = \frac{25}{10,000}. Since the population consists of equal numbers of males and females, Pr \{M\} = Pr \{F \} = \frac{1}{2}. So,

Pr \{M | C\} = \frac{Pr \{C | M\} × Pr \{M\}}{Pr \{C\}} = \frac{Pr \{C | M\} × Pr \{M\}}{Pr \{C | M\} × Pr \{M\} + Pr \{C | F \} × Pr \{F \}} =

\frac{(5/100) × (1/2)}{(5/100) × (1/2) + (25/10000) × (1/2)} = 20/21.

Problem 2 Suppose that a resident of Boston chosen at random is a Red Sox fan (The Curse notwithstanding) with probability 0.90. Also suppose that a resident chosen at random is a Celtics fan (probably still living in the Bird-McHale-Parish era) with probability 0.75, and that a resident Red Sox fan chosen at random is a Celtics fan with probability 0.80. Now suppose that a resident is chosen at random from among those that are not Red Sox fans. What is the probability that such a resident is a Celtics fan?

Solution: Let C represent the event that a resident is a Celtics fan, and S represent the event

that the resident is a Red Sox fan. Then:

Pr \{C\} = Pr \{C | S\} Pr \{S\} + Pr \{C | \overline{S}\} Pr \{\overline{S}\}
Pr \{C | \overline{S}\} = \frac{Pr \{C\} − Pr \{C | S\} ∗ Pr \{S\}}{Pr \{\overline{S}\}}
= \frac{0.75 − 0.80 · 0.90}{1 − 0.9}
= 0.3

Problem 3 A population consists of c_{1} members of type 1, c_{2} members of type 2, ⋯, c_{n} members of type n. A set of k members is drawn from the population without replacement.

(a) Find the probability that exactly i members of type 1 were chosen.

Solution: Let N_{1i} be the event that exactly i members of class 1 were chosen. Pr {N_{1i}} =

\frac{\binom{c_{1}}{i}×\binom{c_{2}+···+cn}{k−i}}{\binom{c_{1}+···+cn}{k}}.

(b) Find the probability that exactly i members of class 1 and exactly j members of class 2 were chosen.

Solution: Let N_{2j} be the event that exactly j members of class 2 were chosen. Then Pr {N_{1i} ∩ N_{2j}} =

\begin{matrix}\binom{c_{1}}{i} & \binom{c_{2}}{j} & \binom{c_{3}+···+cn}{k−i−j} \\ ( & {c_{1}+···+cn \atop k} & ) \end{matrix}

Problem 4 In London, half of the days have some rain. The weather forecaster is correct 2/3 of the time – i.e. the probability that it rains, given that she has predicted that it will rain, and the probability that it does not rain given that she has predicted that it does not rain, are both equal to 2/3. When rain is forecast, Mr. Pickwick takes his umbrella. When rain is not forecast, he takes it with probability 1/3.

(a) Find the probability that Pickwick has no umbrella, given that it rains.

(b) Find the probability that it doesn’t rain, given that he brings his umbrella.

Solution:

We construct a tree as in lecture notes #19. For part (a), we wish to find

Pr {no umbrella | rain} = Pr {no umbrella ∧ rain} ; Pr {rain}
= \frac{1/9}{1/2} = 2/9.

For part (b), we wish to find

Pr {no rain | umbrella} = Pr {no rain ∧ umbrella} ; Pr {umbrella}
= \frac{1/6 + 1/9}{1/9 + 1/6 + 1/3 + 1/18} = 5/12

Problem 5 Let A, B, C be events of some experiment. For each of the following statements, prove it if it is true or give a counterexample if it is false:

(a) If C is independent of A, and C is independent of B, then C is independent of A ∪ B.

Solution: The statement is false. For example, let A and B be unbiased independent bits, and

let C = A ⊕ B. Then C is independent from both A and B, but it is not independent from A ∪ B = A or B .

(b) If C is independent of A, and C is independent of B, and C is independent of A ∩ B, then C is independent of A ∪ B.

Solution: It is true. To prove it, observe by the Sum Rule that

Pr {x ∈ (C ∩ (A ∪ B))}
= Pr {x ∈ (C ∩ (A − B))} + Pr {x ∈ (C ∩ (B − A))} + Pr {x ∈ (C ∩ (A ∩ B))} ,

and then that

Pr {x ∈ (C ∩ (A − B))} + Pr {x ∈ (C ∩ (A ∩ B))} = Pr {x ∈ (C ∩ A)}

also by the Sum Rule. Then use the fact that C is independent of both A and A ∩ B to get that C is independent from A − B, and similarly that it is independent from B − A.

Problem 6 Compute the probabilities of the following three events and determine which one is most likely. Assume that the dice are fair, 6-sided, and mutually independent.

(a) Rolling at least one 6 when six dice are rolled.

Solution: The probability of rolling a 6 on a particular die is \frac{1}{6}. The probability of not rolling a

6 on a particular die is \frac{5}{6}, since this is the complementary event. The probability of not rolling a 6 on any of six dice is (\frac{5}{6})^{6}, since the numbers rolled are mutually independent. The probability of rolling a 6 on some die is therefore 1 − (\frac{5}{6})^{6} = 0.665 . . ..

(b) Rolling at least two 6’s when twelve dice are rolled.

Solution: The probability of rolling two or more 6’s is 1 minus the probability of rolling zero or one 6’s. The probability of rolling zero 6’s is (\frac{5}{6})^{12}, arguing as before. The probablity of rolling exactly one 6 is

12 · \frac{1}{6} · (\frac{5}{6})^{11}

since there are 12 ways to choose the die that comes up 6, the probability of this die coming up 6 is \frac{1}{6}, and the probability of the remaining dice all coming up in the range 1 to 5 is (\frac{5}{6})^{11}.

Overall, the probability of rolling two or more sixes is therefore

1 − (\frac{5}{6})^{12} − 12 · \frac{1}{6} · (\frac{5}{6})^{11} = 0.618 ….

(c) Rolling at least three 6’s when eighteen dice are rolled.

Solution: Arguing as before, the probability of rolling at least three 6’s is

1 − (\frac{5}{6})^{18} − 18 · \frac{1}{6} · (\frac{5}{6})^{17} − \binom{18}{2} · (\frac{1}{6})^{2} · (\frac{5}{6})^{16} = 0.597 ….

Solution: The first event is most likely.