GTO Brainteaser #10 Solution

In our most recent brainteaser, here, I posed a probability puzzle about the relative likelihood of seeing HHT or HTT first in a sequence of coin flips.  I won't restate the full problem so please check out this post for the details: http://blog.gtorangebuilder.com/2016/02/gto-brainteaser-10-flipping-coins.html.  Its been a while since I did a brainteaser so if you enjoy this type of content and want to see more let me know in the comments below.

Solution

So, how do we go about solving this type of problem?

The key concept is that we will state things interms of the EV of reaching a specific state.  Since many sequences of flips lead us back to a state that is EV equivalent to our starting state this lets us set up an equation in terms of our starting EV that we can solve.  Thinking of the possible transitions from one EV state to another is a core concept in working out complex sequential EVs and is relative in situations like estimating your odds of winning a HUSNG vs an opponent when the stacks are not equal.

Lets begin by computing the EV of our coin flipping game which requires determining the probability with which our sequence ends at HHT or HTT.  We should note that to get HTT without getting HHT first requires that prior to or first H we had either just started the game, or we had flipped a T.

Lets call S (S for start) the state where in our most recent history of flips neither of our last two tosses are H and the game has not ended.  Call the EV of this state E.  Note that the game starts in state S so (we have no previous tosses so they cannot be H) so E is also the EV of the game as a whole.

Now what can happen from state S?  If we toss and get tails we stay in state S.  If we toss and get H we move into a new state which I will call P1.

So we can already write the equation

E = 1/2 * (EV of P1) + 1/2 * E.

If we subtract 1/2 * E from both sides and multiply both sides by 2 we get

E =  EV of P1

Now lets consider what can happen once we reach P1.

Case 1: Our next flip is T -- If we get a tail then we are at least 3 flips from getting HHT,  On our third flip 2 things can happen.  Either we get H and are back in state P1 or we get T and the game ends and we win.  So the EV of case 1 is just

 1/2 * (EV of P1) + 1/2 * Win

Case 2: Our next flip is a H -- If we then get a 3rd head in a row we are back in Case 2 where our most recent history is HH.  If we get a Tail as our 3rd flip the game ends and we lose.  Thus the EV of case 2 is just

EV of case 2 = 1/2 * EV of case 2 + 1/2 * Lose.

Note that if we substract 1/2 * EV of case 2 from both sides and multiply by 2 this simplifies to

EV of case 2 = Lose

Since case 1 and case 2 are equally likely this means that:

EV of P1 = 1/2 * (1/2 EV of P1 + 1/2 Win) + 1/2( Lose)

This simplifies to

3/4 EV of P1 = 1/4 Win + 1/2 Lose

Multiply both sides of the equation by 4/3 to get EV of P1 = 1/3 Win + 2/3 Lose

Which means our original Equation can be simplified to

E = 1/3 Win + 2/3 Lose.

This means that HHT comes first 2/3rds of the time and the EV of the game is 1/3 * 105 - 2/3 * 100 = -31.6666.  This is a very profitable game for the casino despite it seeming at first glance like HHT and HTT should happen equally often!

I'll leave the solution to the bonus as an exercise for those of you are excited to get your hands dirty with some math but I will state the final result which is quite surprising.

It terms out the despite the fact the HHT comes first 2/3rds of the time, on average it takes more flips to get HHT than to get HTT.  This seems like a paradox, when we win the game it happens more quickly on average than when we lose but we lose more often than when we win.  I suspect that if a casino were to actually provide this game that paradox would lead many to naively overestimate their chances of winning as they played.

I know it can also be helpful to see the results of these types of problems via simulation as well as by mathematics so I've put up some free runable code that monte-carlos the result here: https://jsfiddle.net/sg9g33t2/