Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science April 27, 2000 Professors David Karger and Nancy Lynch

Problem Set 9 Solutions

Problems:

Problem 1

(a) Carefully prove the following theorem:

If A and B are events in a probability space with Pr(B) ≠ 0 and Pr(B̄) ≠ 0, then Pr(A) = Pr(A | B) Pr(B) + Pr(A | B̄) Pr(B̄).

Show all steps, and justify them with basic facts about probability.

Solution.

Pr(A) = Pr((A ∩ B) ∪ (A ∩ B̄))
= Pr(A ∩ B) + Pr(A ∩ B̄)

⟶ (Because they are disjoint.)

= Pr(A | B) Pr(B) + Pr(A | B̄) Pr(B̄)

□

(b) A space probe near Mars communicates with Earth using bit strings. Suppose that in its transmissions it sends a 1 one-third of the time and a 0 two-thirds of the time. When a 0 is sent, the probability that it is correct is 0.9, and the probability it is received incorrectly (as a 1) is 0.1. When a 1 is sent, the probability it is received correctly is 0.8, and the probability it is received incorrectly (as a 0) is 0.2.

Use the formula above to find the probability that a 0 was transmitted, given that a 0 was received.

Solution.

Let R be the event that a 0 was received. Let S be the event that a 0 was transmitted.

So we are trying to find Pr(S | R).

2 Handout ??: Problem Set 9 Solutions Then we have:

Pr(S) = 2/3
Pr(S̄) = 1/3
Pr(R | S) = 0.9
Pr(R̄ | S) = 0.1
Pr(R̄ | S̄) = 0.8
Pr(R | S̄) = 0.2

Now rearranging:

Pr(S | R) = \frac{Pr(S ∩ R)}{Pr(R)}
= \frac{Pr(R | S) Pr(S)}{Pr(R)}
= \frac{Pr(R | S) Pr(S)}{Pr(R | S) Pr(S) + Pr(R | S̄) Pr(S̄)}
= \frac{0.9 ∗ 2/3}{0.9 ∗ 2/3 + 0.2 ∗ 1/3}
= \frac{1.8}{1.8 + .2}
= .9
□

(c) Generalize the theorem above. Namely, given an event A and mutually exclusive events B_{1}, B_{2}, … B_{k} with nonzero probability, prove that:

P r(B_{1} ∪ B_{2} ∪ B_{3} ∪ … B_{k}) = 1

implies:

Pr(A) = ∑_{i=1}^{k} Pr(A|B_{i}) Pr(B_{i})

Solution.

Pr(A) = Pr(A ∪ (B_{1} ∩ B_{2} ∩ … ∩ B_{k}))
= Pr((A ∩ B_{1}) ∪ (A ∩ B_{2}) … ∪ (A ∩ B_{k}))
= Pr(A ∩ B_{1}) + Pr(A ∩ B_{2}) + … + Pr(A ∩ B_{k}) ⟶ Disjoint
= Pr(A | B_{1}) Pr(B_{1}) + Pr(A | B_{2}) Pr(B_{2}) + … + Pr(A | B_{k}) Pr(B_{k})
= ∑_{i=1}^{k} Pr(A|B_{i}) Pr(B_{i})

□

Problem 2

(a) Consider families with 3 children, assume that the events that the lst, 2nd and 3rd child are girls are all independent, and have probability 1/2. Let X be the event that “the family has children of both sexes”, and Y the event that ”the family has at most one girl”. Are these events independent? Prove or disprove. Solution. To simplify scenario, think of this as flipping three fair coins. Then X is the event that there is at least one head and at least one tail, and Y is the event that there is at most one head. For X:

Pr(at least one head and one tail) = 1 − Pr(zero heads or zero tails)
= 1 − Pr(zero heads) − Pr(zero tails)
= 1 − 1/8 − 1/8
= 3/4

For Y:

Pr(at most one head) = Pr(zero heads or one head)
= Pr(zero heads) + Pr(one head)
= 1/8 + 3 ∗ 1/8
= 1/2

For X ∩ Y:

Pr((at most one head) and (at least one head and one tail)) = Pr(exactly one head and two tails)
= 3 ∗ 1/8
= 3/8

Since P r(X ∩ Y) = P r(X) ∗ P r(Y) the two are independent.

□

(b) Consider the same question for a family of 2 children. Solution. For X:

Pr(at least one head and one tail) = 1 − Pr(zero heads or zero tails)
= 1 − Pr(zero heads) − Pr(zero tails)
= 1 − 1/4 − 1/4
= 1/2

Handout ??: Problem Set 9 Solutions 5

For Y:

Pr(at most one head) = Pr(zero heads or one head)
= Pr(zero heads) + Pr(one head)
= 1/4 + 2 ∗ 1/4
= 1/4

For X ∩ Y:

Pr((at most one head) and (at least one head and one tail)) = Pr(exactly one head and one tail)
= 2 ∗ 1/4
= 1/2

Since P r(X ∩ Y) ≠ P r(X) ∗ P r(Y) the two are not independent.

□

(c) Consider the same question for a family of 4 children. Solution. For X:

Pr(at least one head and one tail) = 1 − Pr(zero heads or zero tails)
= 1 − Pr(zero heads) − Pr(zero tails)
= 1 − 1/16 − 1/16
= 7/8

For Y:

Pr(at most one head) = Pr(zero heads or one head)
= Pr(zero heads) + Pr(one head)
= 1/16 + 4 ∗ 1/16
= 5/16

For X ∩ Y:

Pr((at most one head) and (at least one head and one tail)) = Pr(exactly one head and three tail)
= 4 ∗ 1/16
= 1/4

Since P r(X ∩ Y) ≠ P r(X) ∗ P r(Y) the two are not independent.

□

6 Handout ??: Problem Set 9 Solutions

Problem 3 Shishir, David, and Ken went target shooting last weekend. They shot simultaneously at an empty soda can, which fell over. They have probabilities p_{s}, p_{d} and p_{k} of hitting it. Calculate the following probabilities; state any independence assumptions you need.

(a) The probability that all three hit the can. Solution. Let S, D, and K (respectivelly) be the events that they each hit the can. And let F be the event that the can fell over. Assume that the can needs to be hit to fall over. Also assume mutual exclusivity on whether or not each person hits the can. So we want Pr(S ∩ D ∩ K|F).

Pr(S ∩ D ∩ K | F) = \frac{Pr(S ∩ D ∩ K ∩ F)}{Pr(F)}
= \frac{Pr(F | S ∩ D ∩ K) Pr(S ∩ D ∩ K)}{Pr(F)}
= \frac{p_{s}p_{d}p_{k}}{Pr(F)}

To calculate Pr(F):

Pr(F) = P r(F | S ∪ D ∪ K) Pr(S ∪ D ∪ K) + P r(F | S̄ ∪ D ∪ K) Pr(S̄ ∪ D ∪ K)
= 1 ∗ Pr(S ∪ D ∪ K) + 0 ∗ Pr(S̄ ∪ D ∪ K)
= p_{s} + p_{d} + p_{k} − p_{s}p_{d} − p_{d}p_{k} − p_{s}p_{k} + p_{s}p_{d}p_{k}

Altogether:

Pr(S ∩ D ∩ K | F) = \frac{p_{s}p_{d}p_{k}}{Pr(F)}
= \frac{p_{s}p_{d}p_{k}}{p_{s} + p_{d} + p_{k} − p_{s}p_{d} − p_{d}p_{k} − p_{s}p_{k} + p_{s}p_{d}p_{k}}

□

(b) The probability that Shishir hit the can. Solution.

Pr(S) = \frac{Pr(S ∩ F)}{Pr(F)}
= \frac{Pr(F | S) Pr(S)}{Pr(F)}
= \frac{p_{s}}{p_{s} + p_{d} + p_{k} − p_{s}p_{d} − p_{d}p_{k} − p_{s}p_{k} + p_{s}p_{d}p_{k}}
□

(c) The probability that exactly two of them hit the can. Solution.

Pr(exactly two hit the can | F) = \frac{Pr(F | exactly two hit can) Pr(exactly two hit can)}{Pr(F)}
= \frac{Pr(exactly two hit can)}{p_{s} + p_{d} + p_{k} − p_{s}p_{d} − p_{d}p_{k} − p_{s}p_{k} + p_{s}p_{d}p_{k}}
= \frac{p_{s}p_{d}(1 − p_{k}) + (1 − p_{s})p_{d}p_{k} + p_{s}(1 − p_{d})p_{k}}{p_{s} + p_{d} + p_{k} − p_{s}p_{d} − p_{d}p_{k} − p_{s}p_{k} + p_{s}p_{d}p_{k}}

□

Problem 4 Imagine a random length n string of 0s and 1s. We would like to find a method for determining the probability of a length k substring consisting of only 0s.

(a) Develop a recurrence for the probability of seeing the substring 00 in a random bit string of length n. Solution. Let p(n) be the probability of seeing 00 in a random string of length n. Now segment across three possibilities for the start of the string:

1. Starts with 00: This happens with probability 1/4. When it happens, then we are done.

2. Starts with 1: This happens with probability 1/2. When it happens, then our chance of having a 00 in the string is now p(n-1).

3. Starts with 01: This happens with probability 1/4. When it happens, then our chance of having a 00 in the string is now p(n-2).

All total, our recurrence is:

p(n) = 1/4 + (1/2)p(n − 1) + (1/4)p(n − 2)
□

(b) Solve the recurrence. Solution. The roots are (1 + \sqrt{5})/4 and (1 − \sqrt{5})/4 and the particular solution is p(n) = 1. The coefficients are (−5 + 3\sqrt{5})/10 and (−5 − 3\sqrt{5})/10. The full solution is:

\frac{−5 − 3\sqrt{5}}{10} (\frac{1 + \sqrt{5}}{4})^{n} + \frac{−5 + 3\sqrt{5}}{10} (\frac{1 − \sqrt{5}}{4})^{n} + 1 = 0

□

8 Handout ??: Problem Set 9 Solutions

(c) Write a general recurrence for seeing a k-length string of all 0s within a random string of length n. Solution. The strings partion by starting points again. The partions are strings that start with 1, 01, 001, 0001, … 0000001 (of length k).and 0000000 (of length k) This means the recurrence is:

p(n) = \frac{1}{2^{k}} + \frac{p(n − 1)}{2} + \frac{p(n − 2)}{4} + … \frac{p(n − i)}{2^{i}} + … \frac{p(n − k)}{2^{k}}

□

Problem 5 Suppose there are 120 people in a room. Assume that their birthdays are independent and uniformly distributed. As stated in lecture notes, with probability > 99% there will be two that have the same birthday.

Now suppose you find out the birthdays of all the people in the room except one—call her “Jane”— and find all 119 dates to be different.

(a) What’s wrong with the following argument:

With probability greater than 99%, some pair of people in the room have the same birthday. Since the 119 people we asked all had different birthdays, it follows that with probability at greater than 99% Jane has the same birthday as some other person in the room.

Solution.

Here’s the problem with the argument: Let A be the event that some two people in the room have the same birthday. Let B be the event that the 119 people we asked all have different birthdays.

It is true that Pr {A} > 0.99 (that is indeed the probability spoken about in the lecture notes). However, that is the a priori probability, i.e., assuming all the birthdays are uniform and independent, with no other constraints. The argument above makes the erroneous assumption that event A has probability of at least 99% even once we know that event B holds. But once we know that event B holds, the birthdays are no longer independent. Thus Pr {A | B} is not necessarily equal to Pr {A} (in our case, they are actually quite different, as will be computed in part (b)).

□

(b) What is the actual probability that Jane has the same birthday as some other person in the room?

Solution.

Let S be the set of birthdays of the 119 people in the room other than Jane. By assumption, |S| = 119. Let b be the date of Jane’s birthday. Since b is uniformly distributed over a set of size 365, and b is independent of all the birthdays in S, we have

Pr \{b ∈ S | B\} = \frac{|S|}{365} = \frac{119}{365} ≈ 32.6%,

where B is the event that the 119 people we asked all have different birthdays.

□

Problem 6 Consider a complete graph on 6 vertices (a complete graph means there is an edge between every pair of vertices).

We would like to prove the following theorem:

It is possible to color the edges of the complete graph on 6 vertices, with colors red

or blue, in such a way that no set of 4 vertices has all of its ( \begin{matrix}4 \\ 2 \end{matrix} ) connecting edges

colored the same way. Call such a coloring a ”mixed-up” coloring.

One way of solving this problem would be to actually exhibit a mixed-up coloring. But that’s not the way they’re going to do it in this problem …

(a) Start by numbering all the 4-subsets of the vertices, 1,2, … How many 4-subsets are there? Solution.

( \begin{matrix}6 \\ 4 \end{matrix} ) = 15

□

(b) Define A_{i} to be the event that the ith subset (in the numbered list) has all its edges colored the same color. Compute Pr(A_{i}). Solution. The chance that they are all red is (1/2)^{6} so the chance that they are all either blue or red is 2 ∗ (1/2)^{6} or 1/32.

□

(c) Give an upper bound for Pr(∪_{i}A_{i}). Your bound should come out less than 1. Solution. Using Boole’s Law (P r(∪A_{i}) ≤ ∑ P r(A_{i})), we have an upper bound of \binom{6}{4} ∗ \frac{1}{32} or \frac{15}{32}.

□

(d) Explain in your own words why that shows that a mixed-up coloring exists. Solution. Since the probability that a mixed up coloring does not exist is less than 1, then the probability that one does exist is greater than 0. Since this event has a nonzero probability, some such coloring must exist.

□

(e) (Optional) Can you come up with a specific mixed-up coloring for this graph?

(f) (Optional) Try to generalize your reasoning in this problem to a condition on a pair of numbers n and k that allows such a theorem to be proved (for size k subsets of an n-vertex graph).