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

Problem Set 10

Due Date: May 2, 2000.

Self-study: Games of unbounded length Exercises 1, 2 and 3 in Handout 42 (Dice Game)

Reading:

6.042 Fall 97 Lecture notes: Lectures 21 and 22 (available from course webpage)

Problems:

Problem 1 Recall the envelope guessing game demonstrated in lecture. (You do go to lecture, right?) You are shown two envelopes, each lying face down on a table. There is a number from {0, …, n} written inside each. You pick an envelope and get to see the number in that envelope. You can then either choose to stay with that number, or switch to the number written in the other envelope. You win if the number you end up with is the larger of the two (that is, if either you originally picked the larger and stayed, or if you originally picked the smaller and switched).

A randomized strategy for this game is a function that, for each number i that may be revealed in the envelope you look at, assigns a probability p_{i} of switching. For example, a strategy where p_{i} = \frac{1}{2} for all i effectively ignores the number revealed and chooses randomly. A strategy where p_{i} = 1 for i < \frac{n}{2} and p_{i} = 0 for i ≥ \frac{n}{2} would switch if the number revealed is in the lower half of the range and stay if it is in the upper half of the range.

(a) Prove that the strategy described in class for winning with probability better than 1/2 is optimal if the envelopes are filled with x and x+1, where x is chosen uniformly from {0, …, n−1}. In other words, since we have shown that the strategy given in lecture wins with probability at least \frac{1}{2} + \frac{1}{2n}, show that the expected value of wins per guess with any randomized strategy (any set of \{p_{0}, p_{1}, … p_{n}\} is at most \frac{1}{2} + \frac{1}{2n}.

(b) Optional question: Can you think of another strategy that is also optimal as described above? Is this new strategy ‘really’ optimal?

Problem 2 A new fault-tolerant computer network contains 100,000 computer nodes, and is designed to function adequately when no more than 5000 computers are down. Suppose that the probability that any particular computer is down is 4%; moreover, these probabilities are independent for different computers.

(a) Estimate the probability that exactly 5000 computers are down.

(b) Estimate the probability that the network can function adequately.

Problem 3 The Gallup polling service is conducting a poll to see what percentage of Americans believe that 6-year-olds should be given the legal right to decide where they should live. They would like to be accurate (after all, this is a very serious issue) to within a 2% margin of error, with at least 98% probability. Estimate how many people they would need to poll to be able to make this claim of reliability. (As in lecture, assume that they are polling with replacement, so they may poll the same person twice).

Problem 4 Let X_{1}, X_{2}, and X_{3} be three mutually independent random variables, each having the uniform distribution, Pr [ X_{i} = k] equal to 1/3 for each of k = 1, k = 2, and k = 3. Let M be another random variable giving the maximum of these three random variables.

(a) What is the distribution of M?

(b) What is the expected value of M?

(c) Generalize to n variables with possible values 1, 2, … n.

Problem 5 Suppose a length n string of 0’s and 1’s is chosen uniformly randomly (e.g., by n independent tosses of fair coin) and then wrapped around to form a circle.

(a) What is the maximum number of occurrences of the string 0^{k} (k 0’s) in this circle? What is the expected number of occurrences of 0^{k}? (Note: A string of k + 1 0’s counts as two strings of length k – starting in the first position of the string and starting in the second position. Also remember that there is no particular start or end of the circle.)

(b) Suppose k is even. What is the expected number of occurrences of 0^{\frac{k}{2}} 1^{\frac{k}{2}} (total length k)?

(c) Now fix n = 8, k = 4. Is the probability that 0000 appears in the circle equal to the probability that 0011 appears?

(d) Justify your answer for the previous part. If your answers in the previous parts seem to be “contradictory”, explain.

Problem 6 Suppose that you choose a listing (permutation) of the numbers 1, 2, …, n uniformly at random. What is the expected number of entries that are greater than all entries that follow them? For example, in the listing 4, 2, 5, 1, 3, the numbers 3 and 5 are greater than all following entries. (Hint: Try using indicator variables).

Problem 7 Every day in Boston, a rainstorm occurs with probability 1/3 (independently of any other day). Each day it rains, the radar system at the Nashua airport breaks with probability 1/25. The system never breaks on fair days.

(a) Assuming that the radar was working yesterday (but may break today, if it happens to rain), how many days can we expect the Nashua radar system to work correctly before it next breaks?

(b) Optional question: Suppose that the first time the radar system breaks (on a rainy day with probability 1/25), it is only patched-up with a quick hack to keep it working. (As a computer science student, you should be able to relate to this). After being patched-up, it will fail on future rainy days with probability 1/10, after which the system will need major repairs. Calculate the expected number of days until the radar system needs major repairs.

Problem 8 Suppose that R is a random variable. Let E be an event. The conditional expectation of R given that event E occurs is denoted Ex(R | E) and is defined to be

Ex(R | E) = ∑_{x∈range(R)} x · Pr(R = x | E)

(a) Suppose I flip a fair coin 4 times. Compute the expected number of heads, given that all 4 values are not the same.

(b) Compute the expected value of the number rolled on a fair, 6-sided die, given that the outcome is prime.

(c) Prove the following identity, assuming that all expectations exist.

Ex(R) = Pr(E) · Ex(R | E) + Pr(\overline{E}) · Ex(R | \overline{E})

(d) Optional problem: Suppose you are playing poker. You have the following chart of payoffs:

One P air : $10
T wo P air : $15
T hree of a Kind : $30
F ull House : $60
All else : $0

4 Handout 41: Problem Set 10 Calculate the expected amount of money you will make on a hand, given that the first two cards you are dealt are both Jacks.