Andy and Betty flip a fair coin until either five heads or two tails come up in a row. If two tails comes up first, Andy pays Betty $3. If five heads comes up first, Betty pays Andy $24. What is Andy's expected value for playing this game?

$33/7 ? edit: obviously wrong. was thinking of another question.

Last edited by bertstein on June 5th, 2005, 10:00 pm, edited 1 time in total.

- RealIllusion
**Posts:**22**Joined:**

I don't have an analytical solution to this, but playing around on a spreadsheet indicates that two tails in a row is about 11 times more likely to occur first than five heads in a row. Hence I would say that Andy's expected value is approximately $[ (11/12)*(-3) + (1/12)*24] = minus 75 cents.

Simulating on a spreadsheet the first 26 tosses the prob of two tails in a row is 91.06% and the prob of 5 heads is 8.80%. The remaining 0.14% remains undetermined (it needs more than 26 tosses to determine the winner). The margin for Andy should be around -0.62$ and bounded between this two values -0.623$ < x < -0.585$P.

I get a value of -21/34 = 0.6176. Let v(h) be the value if you've just got a first head.Let v(t) be the value if you've just got a first tail.let v(hh) be the value if you've just had only two heads, etc, etc.v(h)=0.5*v(hh) + 0.5*v(t)v(hh)=0.5*v(hhh)+0.5*v(t)...v(hhhh)=0.5*24 + 0.5*v(t)v(t)=0.5*-3 + 0.5* v(t)Solving these gives v(h) =6/34, v(t)=-48/34So hence before you toss either coin, your expected payoff is -21/34

gjlipman has it correct and Paolos' bounds are correct as well.I got this problem wrong when it was posed to me, I reasoned that two tails are eight times as likely as five heads, so the game is fair. That would be true if you called off the bet if you didn't get either two tails or five heads at the start. It would also be true if we used two separate coins, flipped one twice to check for two tails and the other five times to check for heads; and either split the bet or continued the game if both or neither player won.However, I should have remembered from finance that it's the path that matters, not the terminal distribution.

- onimenokyo
**Posts:**32**Joined:**

Wow, coded the game and got an expected winning of -0.61764607..which extremely close to -21/34=0.61764705..Can someone tell me the name of gjlipman's method (the general idea), or explain it?i don't understand why v(h)=0.5*v(hh) + 0.5*v(t) (where that came from)or how solving v(t)=0.5*-3 + 0.5* v(t) gives v(t)=-48/34 if that is where it's solved.

Suppose we're in the middle of the flipping. Let X be the number of heads since the last tail, and T(X) be the probability of Andy losing given X. We know:T(4) = T(0)/2, with four heads either the next flip will be a head, and Andy wins, or a tail, in which case he has T(0)T(3) = [T(4) + T(0)]/2, if the next flip is heads, Andy has T(4), if it's tails he has T(0)T(2) = [T(3) + T(0)]/2T(1) = [T(2) + T(0)]/2T(0) = [T(1) + 1]/2, if the next flip is heads, Andy has T(1), if tails he loses for sure.That's easily solved to:T(4) = 8/17T(3) = 12/17T(2) = 14/17T(1) = 15/17T(0) = 16/17You can do this by hand easily enough. I set it up as a matrix in Excel and inverted it.The first flip can be either heads, in which case we get T(1) or tails, in which case we get T(0). So Andy's probability of losing is (15/17 + 16/17)/2 = 31/34. Since he loses $3 31 times out of 34, that's a total of -$93, and wins $24 3 times out of 34, that's a total of $72, he loses $21 in every 34 games.

Last edited by Aaron on June 10th, 2005, 10:00 pm, edited 1 time in total.

Since I made up my method - I'm going to call it the Lipman method. If you ever used it, please send me money and reference it!Really, it is mainly markov chain analysis. I identified the relevant states, and then the state transition probabilities. Then either using a matrix or by algebra you can solve."i don't understand why v(h)=0.5*v(hh) + 0.5*v(t) (where that came from)"if you are in state (h) (you've just thrown a head, and there was no head immediately before that) two things might happen, each with 0.5 chance. You might throw another head, in which case you'll be in state (hh) (which means you've thrown two heads, and no head immediately before that), or you might throw a tail, in which you're in state (t) (you've just thrown a tail, and there was no tail immediately before that). To show how to solve it, consider v(hh)=0.5v(hhh)+0.5v(t)v(h)=0.5v(hh)+0.5v(t)then v(h)=0.25v(hhh)+0.75v(t) and so on.As a useful interesting exercise, show that the expected number of tosses is 4.26 (I think it is, though I might have made a stupid mistake).

- onimenokyo
**Posts:**32**Joined:**

Interesting indeed. I use E(4) as expected number of tosses after 4 heads. and E(0) as expected number of tosses after 1 tails.i use E(4) = (5 + 5 + E(0))/2 // half chance of winning after 5 tosses or half chance of 5 tosses plus expected tosses after one tailsthen E(3) = (E(4)+4+E(0))/2 etcand E(0) = (2+ 2+E(1))/2solving i get E(0)=110/17and E(1)=152/17which gives E(start)=(E(0)+E(1))/2= 7.706..... which is wrongmy simulation gives me 5.47 avg toss per game.

- onimenokyo
**Posts:**32**Joined:**

sorry, i've just done it, i've over counted each extra toss by 1 because E(0) or E(1) already includes one toss. so E(4)= (5+4+E(0))/2 etcand E(0)=(2+1+E(1))/2solving gives E(start) = 93/17=5.47

yep - you're right - I rechecked my maths. I forgot to add in the initial toss, and I also slipped up slightly in my maths. Isn't markov chain analysis much more rewarding than doing a simulation. If you like these sorts of puzzles, calculate the probability of winning a game (not a set or match) of tennis if you're probability of winning a point is 0.6. And if each point takes a minute, what is the expected length of the game.

The probability of winning a tennis game is 73.5729%The expected lenght of the game is 6m 29sP.

I got the same winning prob. but time is coming to 6.3664 minutes (=6 min 22 secs)Expected time, given a deuce occured, was:Prob(1st player wins/deuce) * (6 + 1.84/0.52) + Prob(2nd player wins/deuce) * (6 + 1.64/0.52)(I ended up computing winning (& losing probabilities) for each of the possible ending scores ... which was easy, except for a deuce scenario. For deuce I had to use lipman's method). Not sure, where is the error. -------------------------------------------------Also Paolos, if you could drop in a hint on how you modeled the original coin flipping problem in spreadsheet ... I'd be thankful.I could "simulate" the tosses for 2 tails occuring before 5 heads ... and average over a no. of trials to get a close answer, but that's different.I would like to see the precise result of 2 tails winning over 5 heads in 26 tosses ... and the residual probability of no-result in 26 tosses.(need a spreadsheet modeled result ...not an analytical result to this, becoz the same approach could be used in other probs, which indeed may have no easy analytical solutions). thanks. And to mention a thought I just got, I can't think of an analytical way to solve the above constrained problem (lipman's method works only if the tosses are infinite)!

Last edited by bhutes on June 12th, 2005, 10:00 pm, edited 1 time in total.

QuoteOriginally posted by: bhutesProb(1st player wins/deuce) * (6 + 1.84/0.52) + Prob(2nd player wins/deuce) * (6 + 1.64/0.52)but a game can finish in less than 6 minutes!Let p(d) is the probability that a deuce occurs (27.65% from the binomial distribution)Let p(w) is the probability that somebody wins before a deuce (1-27.65%)Let E(w) is the expected lenght of the game if a deuce doesn't occur (5.20 calculating all the combinations)Let E(d) is the expected lenght of the game if a deuce occurs (6+50/13 from gjlipman's method)The expected lenght is p(d)*E(d)+p(w)*E(w)=6m 29sP.

GZIP: On