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

Problem Set 9

Due Date: April 25, 2000.

Self-study:

Rosen, Section 4.4

Self-study problems: 9, 11, 13, 15, 17

Reading:

Rosen: Section 4.5

6.042 Fall 97 Lecture notes (available from course webpage): Lecture 20

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.

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

(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})

Problem 2 (a) Consider families with 3 children, assume events that the lst, 2nd and 3rd child are girls are all independent, and have probability 1/2.

Let H be the event that ”the family has children of both sexes”, and G the event that ”the family has at most one girl”. Are these events independent? Prove or disprove.

(b) Consider the same question for a family of 2 children.

(c) Consider the same question for a family of 4 children.

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.

(b) The probability that Shishir hit the can.

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

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 of all 0s.

(a) Develop a recurrence for the probability of seeing 00 in a random bit string of length n.

(b) Solve the recurrence.

(c) Write a general recurrence for seeing a k-length string of all 0s within a random string of length n.

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.

Handout 22: Problem Set 9 3 (b) What is the actual probability that Jane has the same birthday as some other person in the room? 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?

(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}).

(c) Give an upper bound for Pr(∪_{i}A_{i}). Your bound should come out less than 1.

(d) Explain in your own words why that shows that a mixed-up coloring exists.

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