8
$\begingroup$

Suppose that we bet on the outcomes of coin flips in the following way. Each of us chooses a different series of three flips, and we flip a coin until three consecutive flips, in order, match your choice or mine. For example, you might pick HHT while I pick HTH, and we flip until either HHT or HTH.

Is one of us more likely to win?

My friend Shimon argues as follows. If you pick HHT and I pick HTH, a long stream of flips will sooner or later include HH, the first two flips in your choice; and at that moment you have won, because there's no way that later flips can produce my HTH streak before it produces your HHT streak. But no corresponding situation exists for the other side; should HT, the first two flips in my choice, arise, it's still possible for you to win, because the next flips could be THHT, so that the six flips HTTHHT would be another win for you.

I consider this total nonsense. It's obvious that the next three flips are as likely to be HHT, or HTT, or any of the six other possible sets of three flips. His approach of asking whether wins are possible given certain strings of past flips is mind-boggling, working without any clear sample-space and defying mathematics.

I suggested a simulation. The simulation I produced is an Excel spreadsheet that flips sets of 65 flips. In each set, it finds the first flip that begins your choice or mine, and assigns a winner. The following screen shot shows that simulation.

enter image description here

Blue is associated with HHT, and pink is associated with HTH. In the first set, HHT began in flips 2, 10, 16, 20, 29, 36 and 50. HTH began in flips 3, 5, 11, 13, 21 and 51. Because HHT arose first, there's a 1 in the blue vertical bar beside the first set. As you may be able to see, HHT won 8 sets of the pictured 10 sets.

In my little experiment, HHT won far more often, and often by dramatic margins.

I've looked around this stack exchange, and found a few questions almost exactly like mine – like this one and this one -- and several questions at least very similar to mine -- like this one and this one.

They all seem to believe that Shimon is right, and some sequences are more likely than others. But despite that seeming (if not very clearly stated) unanimity, and despite my own simulation, I just cannot believe it. Obviously every possible set of three flips is equally likely.

So I guess that my question is, can someone explain this at a more intuitive level, reaching the mistake that's misleading me or (I still think) Shimon?

$\endgroup$
12
  • 5
    $\begingroup$ This is called Penney's Game and there's a lot of information regarding it online. $\endgroup$
    – lulu
    Oct 27 at 23:40
  • 8
    $\begingroup$ As an obvious case that might help intuition, suppose $A$ chooses $TTT$ and $B$ chooses $HTT$. Then convince yourself that the only way $A$ can possibly win is if the coin comes up $TTT$ initially, so $A's $ chance of winning is only $\frac 18$. $\endgroup$
    – lulu
    Oct 27 at 23:41
  • $\begingroup$ Start with HH, next flip H is bad, but then followed by a T gives HHT a win. However start with HT followed by a T (bad), but nether can win on the next flip. $\endgroup$ Oct 27 at 23:48
  • $\begingroup$ Undoubtedly this has been asked and answered on this site before, probably several times. E.g., math.stackexchange.com/questions/3853515/… and math.stackexchange.com/questions/954395/… and math.stackexchange.com/questions/3856649/… and math.stackexchange.com/questions/3390215/… $\endgroup$ Oct 27 at 23:57
  • 1
    $\begingroup$ That's a different question. Each $3$ character string is equally likely to come up so that game is fair (but not terribly interesting). Study the example I gave you, or look up any of the online references. $\endgroup$
    – lulu
    Oct 28 at 0:01
7
$\begingroup$

Let's say I'm betting on HHT and you're betting on HTH. I claim the odds are $2$ to $1$ in my favor.

Look at it this way. Sooner or later the coin is going to come up H for the first time. Let's consider what happens on the next two flips after that first head. There are four cases.

  1. HHT I win.
  2. HHH I win; sooner or later the coin will come up T.
  3. HTH You win.
  4. HTT We start over.

The following parable may or may not illuminate the error in your thinking.

An underground train follows a circular route, stopping in turn at stations A, B, C, . . . X, Y, Z, A, B, C, . . . You and your friend stagger on board and fall asleep. Some time later you both wake up, between stations, having no idea where you got on or where you are now.

You: I wonder where we are. I get off at Q.

Your friend: I bet you ten bucks we hit my stop before yours.

You: Hmm. One station is just as likely as another. That's a fair bet. You're on. Which is your stop?

Your friend: P.

$\endgroup$
1
  • 2
    $\begingroup$ A nice example indeed. It's similar to this question. $\endgroup$
    – justhalf
    Oct 28 at 8:18
7
$\begingroup$

I feel your pain: you are getting many arguments that explain why your friend is correct, and links to previous stack exchange posts that also side with your friend's conclusion. Even your own simulations confirm your friend is correct! However, what (if anything!) is wrong with your reasoning to the contrary?!? The provided arguments and findings may show that your reasoning is incorrect, but none of them explain why or where your reasoning is incorrect. So, instead of providing yet another argument why your friend’s reasoning is correct, let me see if I can get to the heart as to why your reasoning is incorrect.

I think that what lies at the core of your reasoning is the idea that ‘at any point in a long sequence of heads and tails, any specific sequence of three heads and tails is just as possible as any other’.

And yes, that is true in the sense that if you start at that point X in the sequence, and only look at the next three entries of that sequence. Indeed, this is just like when you say:

It's obvious that the next three flips are as likely to be HHT, or HTT, or any of the six other possible sets of three flips.

However, whether some specific sequence of three will appear before some other sequence of three also depends on whatever entries you have before that point X. Thus we get your friend’s reasoning: if the last two outcomes that you obtained before X were both heads, then the very next entry could end the game right then and there.

So, your mistake could be seen as the result of an ambiguity in the claim of ‘getting a specific sequence from some point on’. Again, if you mean this to be the event of getting a specific sequence starting from a point in the sequence, then you are right: starting at that point in the sequence, any sequence is just as likely to appear as any other. But what we are after is the event of getting a specific sequence from that point in the game. And, at any point in the game, the outcomes that happened before you reached the point of the sequence that you are at at that point in the game make a difference. I believe the conflation of these two different senses of ‘from that point on’ lies at the heart of the mistake in your reasoning.

$\endgroup$
2
$\begingroup$

Your intuition is correct in that as many HTH as HHT will appear in any long enough sequence. If you count those occurences in your simulations, you may confirm that result, and if you play with your friend a (boring) game of "we flip a coin 1000 times, we count how many HHT and how many HTH there are, and whoever has the most wins", this is a fair game.

However, what you are playing is a different game : you are playing "what sequence comes first" ; and this game is not fair.

You don't win every time HTH appears: You win when HTH appears and HHT has not appeared yet. You opponent wins when HHT appears and HTH has not appeared yet.

The key here is to see that the events (the winning cases) are not independant. HHT and HTH appear just as often, but half of the time HTH appears just one flip after HHT.

As a suggestion to help your intuition, let's suppose no one wins in the first three coin flips (this remove 1/4 of the tries, half of them wins and the other half losses). Now consider the first HTH of the sequence and ask yourself what was the previous flip:

  • Half of the time, it will be a H, making the pattern ...HHTH. You lose because HHT appeared just one position before HTH !
  • Half of the time, it will be a T, making the pattern ...THTH. It all depends whether HHT is to be found beforehand or not. You may win, or not.

Symmetry is broken because the two pattern HHT and HTH are not independant. The calculations in the other answers are correct : the odds are against you 2:1.

And if you want to trick your opponent, offer a game of "which sequence comes second"...

$\endgroup$
1
$\begingroup$

I already posted one possible explanation as to where and how your intuition is taking you astray, but maybe what you are doing is this:

Again, you correctly point out that at any specific location of any long sequence, and specific sequence is just as likely to occur as any other. This also implies that the number of those sub-sequences you get inside any longer sequence is exactly the same for any sub-sequence.

[this is something you can confirm with your simulations: you should get (ignoring small random variations) just as many HHT's and HTH's in all those sequences you looked at.]

As such, it certainly makes intuitive sense that the average first location of any subsequence inside a larger sequence would not differ between the different subsequences: there are just as many HTH's as HHT's, so if we just randomly sprinkle those into the larger sequence, then why would one, on average, appear earlier than any other?

This seems to be along the lines that you reason, but unfortunately it does not work.

As the Answer by @Evargalo shows: the events of HHT and HTH occurring in a long sequence are not independent. But it is also true that the event of one HTH event occurring in a long sequence is not independent from the occurrence of a second HTH either, because once you have a HTH occurrence, then you already have the first H of a second HTH event. Indeed, what happens as a result is that all the HTH occurrences in a sequence will tend to be more clustered/clumped together in comparison to the occurrences of HHT events

[again, this is something you could try and quantify in your simulations as well, but just eye-balling your graph, I think you can see that the HTH events are more clustered than the HHT events ... but also have longer stretches of having no such occurrences in between ... so you could look at the standard deviation of the distances of their occurrences: you should find that for HTH that's higher than for HHT]

On the other hand, because there is no overlap possible between any two HHT sequences, their occurrences will 'push' each other away from each other, and will be more evenly distributed. And, as a result of that, it stands to reason that the occurrence of the first HTH event would indeed be further into the sequence than the first HHT event.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.