Massachusetts Institute of Technology Handout 60 6.042J/18.062J: Mathematics for Computer Science December 4, 1998 Professors N. Lynch and S. Devadas

Problems for Recitation 12 (12/4/98)

Problem 1. The Petersburg Casino offers the following game: the gambler bets a fixed wager, and then the dealer flips a fair coin (dealers do not flip coins in US casinos, but they do in Petersburg) until it comes up heads. The gambler receives $1 if the coin shows heads the first time, $2 if it shows the first head at second toss, and in general $2^{k−1} if the dealer tosses the coin k times to get the first head. The fixed wager is $100,000.

(a) What is the expected amount of money that the Petersburg Casino is going to pay to a gambler that plays this game? What about the variance? Is it reasonable for the gambler to risk $100,000 dollars in a game where there is a 50% chance of getting only one dollar back (this is not really a mathematical question: just think about that.)

(b) What is the probability that the gambler does not lose money in this game, i.e. what is the probability that he gets back from the Casino more than $100,000?

Problem 2. A Harvard student, lost in the underground corridors of MIT, finds himself in a room containing three doors. Door 1 leads him to freedom (out of MIT) after one hour travel; door 2 returns him to the same room after four hours travel, and door 3 returns him to the room after seven hours travel. Each time he finds himself in the room, the Harvard student picks a door with equal probability. Let T denote the time until he finds the exit.

(a) Define a sequence of independent identically distributed random variables R_{i} and a stopping rule Q such that

T = ∑_{i=1}^{Q} R_{i}

(b) Is R_{k} independent of the event that Q ≥ k? Is R_{k} independent of Q?

(c) If it is applicable, use Wald’s Theorem to find E [T].

(d) Now suppose that an MIT student is also lost and finds herself in a similar situation to the Harvard student. The MIT student never chooses the same door twice. What is E [T] for the MIT student?