Probability question - time to achieve a given sequence of coin flips

Factual Questions
1

Two players are repeatedly flipping a fair coin. Player A flips until they get the sequence HTH. Player B flips until they get the sequence HHT. Who should expect to finish sooner?

My intuition says Player A has an advantage, because if they get HT they have one more to get, and if they get HH, then they still only have two more to get.

But if Player B gets HH they have one more to get, but if HT they have to go back to the start.

But I can’t prove it, or quantify it, and maybe my intuition is wrong?

2

You’re only considering two of the possible four outcomes for the first two flips. You consider HT and HH for both players, but ignore TH and TT. If you take those outcomes into account, then the odds will become 50/50.

ETA: For either sequence, the odds of making it on 3 consecutive flips is 1/8. The odds of having to restart after any given flip are 1/2, regardless of the sequence they need to make.

3

It doesn’t matter how many starting Ts there are, the game only starts after the 1st H. The next 2 spins have a 25% A win, (TH) and 25% B win(HT) 25% reset (TT)

If it’s HH then Player B is 1 away whilst player A is 2 away, that’s the only asymmetry so player B has the advantage.

4

Absolutely.

Now if you change the problem to totals of H + T such as:

  • A has to get ‘two heads and a tail’ in any order
  • B has to get ‘three tails’ in a row,

then A has the advantage because there are more sequences to win with than B has.

5

No clearly B is ahead as I just outlined.

All starting Ts can be ignored as they don’t do anything. The 4 combinations starting with H are

HTH- A wins
HHT- B wins
HTT- game is reset
HHH- B is 1 away from victory, A is 2 away.

6

I would think that the odds of getting any combination are the same.

7

Imagine for a moment the lineup of HHT vs HHH.

Both need to get HH in order to have a 50% chance of winning on the next flip. Exactly identical.
If HHT loses on the next flip, they get another chance to win again immediately, and will continue to have a 50% chance of winning on every subsequent flip.
If HHH loses on the next flip, they are restarting entirely.

8

I think you’ve got that wrong. An early tail would reset both. It’s just a wait for HH then a sudden death winner takes all. This is a 50/50 as would any sequence where only the last one is different.

9

Oh sorry ignore all my comments. I misread it as 1 set of flips from 1 source and the winner is the first to get their sequence. That changes the answer so I’m acknowledging my misreading now.

10

Good explanation, thanks

I guess my intuition was off.

11

Are they both playing from the same coin flips, or is each flipping their own coin?

12

Each flipping their own coin. Sorry if that wasn’t clear

13

If you just start from scratch and flip coins, the expected time to get HTH is 10. On the other hand, the expected time for HHT is 8 (can’t do better then that). Your intuition seems reversed as HTH loses out having the initial “H” at the end as well. You can see this by writing down, for instance, a regular expression that accepts HTH: T*{H, HTT, HTTT, …}* HTH versus
T*{H, HT}*HHT which is easier to satisfy.

14

How is this calculated? Not doubting you, just curious as to how one would work this out. It’s possible that you explained it further on when talking about “regular expressions” but I didn’t understand the notation.

15

I am glad you asked.

This may not be the most “elementary” way to calculate the expectation, but it is instructive and gives a bit of an insight as to what is going on. In order to calculate the expected length of a string, we need to count how many there are. The claim is that a string that ends with the first occurrence of “HTH” has the following structure:

  • zero or more occurrences of “T”; followed by
  • zero or more occurrences of “H”, “HTT”, “HTTT”, etc.; followed by
  • HTH

For example, if the total length is 3 there is only HTH

Length 4: HHTH, THTH
Length 5: TTHTH, THHTH, HHHTH

and so on.

A generating function which counts these is given by
(1+x+x^2+x^3+\cdots)(1+x+x^2+2x^3+\cdots)\cdot x^3
i.e. from
(1+\mathtt{T}+\mathtt{T}^2+\cdots)(1+\mathtt{H} + \mathtt{HH} + \mathtt{HHH} + \mathtt{HTT} + \cdots)\mathtt{HTH}

Doing some algebra, this equals

\frac{1}{1-x}\cdot \frac{1}{1-x\bigl(\frac{1}{1-x}-x\bigr)}\cdot x^3 = \frac{x^3}{1-2x+x^2-x^3}.

More generally, if you specify your target word (here “HTH”) and consider the structure of strings that end with that word but have no other occurrences of the target word, there is a trick by Guibas and Odlyzko that avoids explicitly calculating the regular expression or the corresponding finite automaton: let S be the language of words that do not contain the target word, and T be the language of words where it occurs only at the end. Appending a single letter to a word in S results in a nonempty word in S or T, and appending the target word to a word in S results in either a word that contains the target at or near the end (you could have overlaps between the beginning and the end of the target word).

In the case of HTH, this yields the equations S(x)+T(x) = 1+2xS(x) and x^3S(x)=T(x)(1+x^2) which we can solve for T(x). More generally, you get

T(x) = \frac{x^k}{x^k+(1-2x)c(x)}

where c(x) is the polynomial whose coefficient of x^i is 1 whenever shifting the target to the right i letters overlaps.

Bottom line is, if you can count the matching strings and compute the generating function, it is just a bit more algebra to calculate the expected time until your pattern occurs: compute xT'(x) and substitute x=1/2. Because if T(x) = a_0 + a_1x + a_2x^2+\cdots then T'(x) = a_1 + 2a_2x+3a_3x^2+\cdots.

NB that for good sequences like HHT you have to wait on average 8, but with a pessimal choice like HHH you have to wait 14.

16

A perhaps intuitive way to calculate this is to notice that there are only four states the game can be in, and the the expected number of flips “left to go” in any of those four states doesn’t care about the history. So you can use recursive relationships.

Let E_0 be the answer we seek, namely the expected number of flips when we just start (i.e., we have no progress yet on the HTH goal).

After the first flip, there is a 50% chance we spent one flip and made progress to the next “state” of the game (we flipped H) and a 50% chance we spent one flip and are back at the beginning (we flipped T). So:

E_0 = 1 + \frac{1}{2}E_{\mathrm{H}} + \frac{1}{2}E_0

where E_{\mathrm{H}} is the expected number of flips needed once we have our initial “H”. Notice how the sort of “infinite” possibilities in the failure branch is no different from just starting over, and thus we just need to add in another E_0 flips after our first flip to account for the rest of the game in that 50% possible branch. This simplifies nicely to:

E_0 = 2 + E_{\mathrm{H}}\ \ \ \ \ \ \ \ \ \ Eq. 1

For E_{\mathrm{H}}, we consider another flip (so we add another 1) and then we also need more flips, either however many it takes after a lucky T or however many it takes after an unlucky H. In this case, the failure (H) doesn’t start us over from scratch, since we are still in the “H” state.

E_{\mathrm{H}} = 1 + \frac{1}{2}E_{\mathrm{HT}} + \frac{1}{2}E_{\mathrm{H}}

We can simplify in the same way and plug E_{\mathrm{H}} into our E_0 expression (Eq. 1) to yield

E_0 = 4 + E_{\mathrm{HT}}\ \ \ \ \ \ \ \ \ \ Eq. 2

Finally, at the state “HT” we consider one more flip and then we either end up needing zero more flips after that (win!) or we bomb out with a T and need E_0 more flips (starting over). So:

E_{\mathrm{HT}} = 1 + \frac{1}{2}(0) + \frac{1}{2}E_0 = 1 + \frac{1}{2}E_0

Plug E_{\mathrm{HT}} into Eq. 2 to solve immediately for E_0.

E_0 = 4 + 1 + \frac{1}{2}E_0\ \ \ \implies \ \ \ \ E_0 = 10

17

Thank you both for the clear explanations!

18

Rhis is a form of Penney’s Game, btw, a well-known non-transitive game

19

For an extreme example: Say that one player needs TTTTTTH, and the other needs HTHTHTH (both seven flips long). And suppose that they’ve both gotten lucky, and matched the first six flips of their sequence. Either one of them will now win if they get a H, but the symmetry ends there: If player 2 gets a T, then she’s back to square zero, and has to get her whole seven-flip sequence from scratch. But if player 1 gets a T, no biggie, he’s still one flip away from winning. Every flip from here out, he’ll either win, or he’ll stay the same; his position can never get any worse.

20

Great example. Thank you.

Which clearly accentuates that although any given goal of n Hs & Ts in a particular sequence are equally likely a priori, each of them occurring embedded in a longer sequence are wildly different in likelihood depending on what the sequence is.