Massachusetts Institute of Technology Handout 7 Mathematics for Computer Science August 12, 2004 Professor Charles E. Leiserson

Optional Homework 3

Problem 1. A publisher gives the proofsheets of a new book to two different proofreaders, who read it separately. The first proofreader finds 60 misprints. The second proofreader finds 70 misprints of which 50 are the same as misprints found by the first proofreader. Make some reasonable assumptions about the probabilistic process by which the proofreaders find misprints in order to determine the expected number of misprints remaining undetected in the book.

Problem 2. Alice, Bill, and Carol like to play the following game. Each player puts two dollars into a hat and then secretly writes a number between 1 and 6 on a piece of paper. Someone then rolls an ordinary die. The players reveal their numbers, and the money in the hat is given to the player who correctly predicts the outcome of the die roll. If more than one player is correct, the money is divided equally among the winners. If no one is correct, everyone takes their money back.

Over the course of many games, Carol notices that she is slowly, but steadily losing money. She makes sure that the money is distributed according to the rules. She tests the die to confirm that it is fair. She ensures that her guesses are secret. She tries many different guessing strategies. But she keeps losing money. Why?

Problem 3. In the game of Chuck-a-Luck, the player picks a number between 1 and 6. The game operator then rolls three dice. The outcome of the game is determined as follows:

• If the player’s number comes up once, she wins one dollar.

• If the player’s number comes up twice, she wins two dollars.

• If the player’s number comes up three times, she wins p dollars.

• If the player’s number does not come up at all, she loses a dollar.

For what value of p is the game fair?

Problem 4. You are running the following game at a carnival. A player flips a coin until he gets heads. Then, you pay the player 3^{k} dollars, where k is the number of tails that he flipped. How much should you charge people to play this game if you want the game to be fair?

Problem 5. Suppose that we play the following game. I put some money in one envelope and twice as much money in a second envelope. Now you pick an envelope at random and count how much money is inside. Suppose you find x dollars there. Now, you can either keep the x dollars or else take the unknown amount of money in the other envelope.

If you take the x dollars, then your expected payoff is, of course, x dollars. On the other hand, if you switch, then with probability 1/2 you win x/2 dollars and with probability 1/2 you win 2x dollars. Your expected payoff is therefore

\frac{1}{2} · \frac{x}{2} + \frac{1}{2} · 2x = \frac{5}{4}x

Thus, the analysis indicates that switching improves your expected payoff by 25 percent. Argue that this conclusion is obviously wrong, and then pinpoint the precise error in the analysis.