Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science December 3, 1999 Professors Nancy Lynch and Srinivas Devadas

Notes for Tutorial 19 (12/2/99)

Problem 1 The St. 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 St. 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.

(a) Suppose the fixed wager is $10. What is the expected amount of money that the gambler will win in this game? Suppose the fixed wager is $10,000?

Let V be the random variable corresponding to the amount of money that the gambler is paid by the dealer. The distribution of V is as follows: for any n ≥ 1,

Pr {V = 2^{n−1}} = 2^{−n},

where the probability refers to the event that the dealer tosses n − 1 tails followed by a head. The average of V is

E [V] = ∑_{n=1}^{∞}[2^{−n}2^{n−1}] = ∑_{n=1}^{∞} 1/2 = ∞.

So whatever the fixed wager, the gambler expects to win an infinite amount.

(b) What is the probability that the gambler does not lose money in a game when the fixed wager is $10,000?

The probability of recovering the money of the wager is only

Pr {V ≥ 10, 000} = Pr {V ≥ 2^{14}}
= Pr {dealer flips at least 14 consecutive tails}
= 2^{−14} = \frac{1}{16, 384}

(c) In reality, it would not be reasonable for the gambler to play the game with the fixed wager at $10,000. Why?

The model ignores the fact the both the casino and the player can lose only bounded amounts of money before going bankrupt. Truncating the game when either party goes bankrupt can completely change the expected winnings.

For example, since the probability of the gambler coming out ahead by any amount in a single game with the $10,000 entry fee is 2^{−14}, the expected number of games that must be played before this happens is 2^{14}, so if the player has less than $2^{14} · 10^{5} = $163, 840, 000, he can expect to go bankrupt before coming out ahead in even one game.

Optional exercise: What should the casino’s and the gambler’s net worths be in order for the gambler’s expectation to be positive when the fixed wager is $10? How about $10, 000?

Problem 2

(a) Suppose we flip a fair coin until two heads in a row come up. What is the expected number, F, of flips we perform? Hint: Let F_{T} be the expected number of further flips until two heads comes up, given that the previous flip was T, and likewise let F_{H} be the expected number of further flips until two heads comes up given that the previous flip was H. Argue that F_{T} will equal 1 plus the average of F_{T} and F_{H}.

Clearly F = F_{T}. Assuming the hint

F_{T} = 1 + \frac{F_{T} + F_{H}}{2} .

Similarly,

F_{H} = 1 + \frac{F_{T} + 0}{2}.

Solving for F_{T} yields F = 6.

(b) Suppose we flip a fair coin until a head followed by a tail come up. What is the expected number, G, of flips we perform?

Clearly G = G_{T}. As above

G_{T} = 1 + \frac{G_{T} + G_{H}}{2} ,
G_{H} = 1 + \frac{0 + G_{H}}{2} .

So G = G_{T} = 4.

(c) Suppose we now play a game: flip a fair coin until either HH or HT first occurs. You win if HT comes up first, lose if HH comes up first. What odds should you offer an opponent to make this a fair game?

Even money odds. Although the expected time for HH is larger than for HT, the game of waiting for one or the other to come up first is fair!

To prove this, let W be the probability of winning. Clearly,

W = (1/2) Pr {W | first roll is T } + (1/2) Pr {W | first roll is H} = (1/2)W + (1/2)(1/2)

so W = 1/2.

Problem 3 An urn contains red and blue colored balls. The fraction of red balls is r where 0 ≤ r ≤ 1. A gambler repeatedly pulls a ball at random from the urn. That is, at any point during succesive pulls, each ball in the urn is equally likely to be the next one pulled. The gambler puts the ball back into the urn before making the next pull. He keeps pulling balls until he pulls two red balls in a row.

The sequence of pulls by the Gambler can be regarded as a sequence of tries, where the first try begins with the first ball pulled. Each try consists of a sequence of pulled balls continuing until either a blue ball, or two red balls in a row, are pulled. For example, if the colors of pulled balls are RBBBRBRR, then there are five tries which we indicate with slashes: /RB/B/B/RB/RR/. Note that each try consists of one or two consecutive balls.

(a) What is the expected length of the ith try, assuming that there are at least i tries?

Given that there is an ith try, it is of length 1 iff it starts with a blue ball. It is of length 2 iff it consists of 2 red balls. Hence,

E [length of ith try | there is an ith try] = 1 · (1 − r) + 2 · r = 1 + r.

(b) What is the expected number of tries?

A series of tries ends iff only the last try consists of two reds. We know from lecture that the “mean time to failure” is the reciprocal of the probability of failure, so E [num tries] is the 1/Pr(2 reds) = 1/r^{2}.

(c) Write a simple expression in terms of your answers to the previous parts of this problem for the expected number of balls pulled by the Gambler. Briefly justify your reasoning.

Wald’s Thm applies because E [length of ith try | there is an ith try] is the same expression from part (a) for all i. Hence,

E [num pulls] = E [pulls per try] · E [num tries] = (1 + r)\frac{1}{r^{2}} .