Serving the Quantitative Finance Community

outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### educational coinflip game

The game goes like this:
* pick a Heads/tails pattern of length 3, e.g. "HTT"
* I also pick a pattern, ..maybe "HHT"
* We start flipping coins and the one who's pattern shows up first wins.

I have a strategy that will give me a higher win probability, and it goes in a circle. If you decide to pick my winning pattern then I switch to a better one next time and still have a higher probability to win, and we can endless keep doing that.

Brainteaser:
* What is the lowest probability of me winning assuming I try to maximize it
* Can you explain how you computed it using simple math concepts? I'm going to trick my son into trying to solve this by winning and not giving the answer directly, only offering math lessons so that he learns to figure it out himself. Maybe some of you have a very elegant, dead simple solution/insight/approach?

Nordsmate
Posts: 11
Joined: November 21st, 2005, 7:43 am

### Re: educational coinflip game

66% I think...

Solution - whatever length 3 pattern u choose (say HTT) I pick the pattern that is something then the first 2 of yours.. so THT say...
You can only win if (in this case) HT turns up as a pair...
If it does there is a 50% chance that just before the HT appeared, a T had appeared and I won.
If I didnt win (50%) then there is a 50% chance you win - total prob 25%
And theres 25%  neither of us win and we loop again...

So 2/3 of the time I win...

outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: educational coinflip game

Very simple & clear reasoning!

However, your explanation doesn't cover the 1/8th probability that my HTT shows up immediately (and hence there is no "just before') and then *I* win.

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Re: educational coinflip game

indeed, so his answer would become 7/8*2/3 = 7/12 or 58%

outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: educational coinflip game

Yes, and he can do better than 58% (for this  case where I pick HTT)

edit:
I'm not sure if the THT response is sub-optimal, or if the calculation of that probability is wrong.. but I know 58% is too low.

The reasoning of "<anything>HT" includes the cases where either HTT or THT already show up earlier on inside <anything>

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Re: educational coinflip game

katastrofa
Posts: 10158
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: educational coinflip game

The game goes like this:
* pick a Heads/tails pattern of length 3, e.g. "HTT"
* I also pick a pattern, ..maybe "HHT"
* We start flipping coins and the one who's pattern shows up first wins.

I have a strategy that will give me a higher win probability, and it goes in a circle. If you decide to pick my winning pattern then I switch to a better one next time and still have a higher probability to win, and we can endless keep doing that.

Brainteaser:
* What is the lowest probability of me winning assuming I try to maximize it
* Can you explain how you computed it using simple math concepts? I'm going to trick my son into trying to solve this by winning and not giving the answer directly, only offering math lessons so that he learns to figure it out himself. Maybe some of you have a very elegant, dead simple solution/insight/approach?
I think if I choose HTT and and you HHT, my chance of winning is 3/4 and your 1/4. I think the answer is 50%.

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Re: educational coinflip game

The game goes like this:
* pick a Heads/tails pattern of length 3, e.g. "HTT"
* I also pick a pattern, ..maybe "HHT"
* We start flipping coins and the one who's pattern shows up first wins.

I have a strategy that will give me a higher win probability, and it goes in a circle. If you decide to pick my winning pattern then I switch to a better one next time and still have a higher probability to win, and we can endless keep doing that.

Brainteaser:
* What is the lowest probability of me winning assuming I try to maximize it
* Can you explain how you computed it using simple math concepts? I'm going to trick my son into trying to solve this by winning and not giving the answer directly, only offering math lessons so that he learns to figure it out himself. Maybe some of you have a very elegant, dead simple solution/insight/approach?
I think if I choose HTT and and you HHT, my chance of winning is 3/4 and your 1/4. I think the answer is 50%.
it's 2 to 1 in that file I linked.
Once you get to HH, player 2 has won.
Why?
look at the possible tosses
HHT
HHHT
HHHHT
HHHHHT
HHHHHHT
HHHHHHHT
HHHHHHHHT

so sooner or later player 2 wins once you hit HH

Now consider what happens when you hit the first H in a sequence (so either the absolute 1st toss at the start or the previous throw was a T)
HTT 25% player 1 wins
HTH 25% and loop starts again
HH 50% and player 2 wins

and that's your 2 to 1

Nordsmate
Posts: 11
Joined: November 21st, 2005, 7:43 am

### Re: educational coinflip game

Yes - I have made a mistake.. and it is pattern specific...
I assumed that if on a "loop" I didn't win and you didn't win then we started again. Of course I want to choose a pattern such that if I didn't win and you didn't win then I am 2/3rd s of the way to winning again... and I can (for some patterns) choose patterns such that you can never win (because if I don't win you cant win) - unless you win in the very first round.

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Re: educational coinflip game

that's what happens if player 1 picks HHH and player 2 picks THH.
Either the 1st 3 tosses are H and player 1 wins or a T comes up and sooner or later player 2 wins
1/8 chance player 1 wins, 7/8 chance player 2 wins

outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: educational coinflip game

that's what happens if player 1 picks HHH and player 2 picks THH.
Either the 1st 3 tosses are H and player 1 wins or a T comes up and sooner or later player 2 wins
1/8 chance player 1 wins, 7/8 chance player 2 wins
This was the exact case that happened when I explained the game to my son. He picked HHH, I picked THH and he immediately said "ah, I see, I only win 1/8th of the times, the rest is all yours". He said the "cycle thing" was similar to Nontransitive dice he had heard about.

At Quora is a nice Markov chain plot that illustrates how to compute the win probabilities,.. but if we go there then it'll be just equations instead of intuition. Still,  getting the good intuition on how to solve it is a challenge in itself. E.g. with a pattern length of 4 there are instances where one patters has a higher win probability even though it also has a *larger* expected time to show up compared to the first. Comparing expected time would a different problem.

katastrofa
Posts: 10158
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: educational coinflip game

I misunderstood the task. I merged it with Nordsmate's answer and assume you were asking about the minimum probability of winning using the strategy he/she described, hence my answer (50%). And I obviously mixed something up with HHT vs HTT probabilities. I should have googled first

outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm