# Probability question - time to achieve a given sequence of coin flips **URL:** \ **Category:** Factual Questions\ **Tags:** science-math\ **Created:** [April 20, 2026, 3:56pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432 "2026-04-20T15:56:06Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![zimaane](https://avatars.discourse-cdn.com/v4/letter/z/a3d4f5/32.png) [@zimaane](https://boards.straightdope.com/u/zimaane)\ **Post date:** [April 20, 2026, 3:56pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/1 "2026-04-20T15:56:06Z")
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? ---
**Author:** ![FlikTheBlue](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/fliktheblue/32/10972_2.png) [@FlikTheBlue](https://boards.straightdope.com/u/FlikTheBlue)\ **Post date:** [April 20, 2026, 3:59pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/2 "2026-04-20T15:59:41Z")
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. ---
**Author:** ![colinfred](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/colinfred/32/21338_2.png) [@colinfred](https://boards.straightdope.com/u/colinfred)\ **Post date:** [April 20, 2026, 4:10pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/3 "2026-04-20T16:10:16Z")
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. ---
**Author:** ![glee](https://avatars.discourse-cdn.com/v4/letter/g/b5a626/32.png) [@glee](https://boards.straightdope.com/u/glee)\ **Post date:** [April 20, 2026, 4:16pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/4 "2026-04-20T16:16:28Z")
> [@FlikTheBlue](#): > > For either sequence, the odds of making it on 3 consecutive flips is 1/8 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. ---
**Author:** ![colinfred](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/colinfred/32/21338_2.png) [@colinfred](https://boards.straightdope.com/u/colinfred)\ **Post date:** [April 20, 2026, 4:17pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/5 "2026-04-20T16:17:38Z")
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. ---
**Author:** ![Frodo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/frodo/32/302_2.png) [@Frodo](https://boards.straightdope.com/u/Frodo)\ **Post date:** [April 20, 2026, 4:21pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/6 "2026-04-20T16:21:25Z")
I would think that the odds of getting any combination are the same. ---
**Author:** ![Cheesesteak](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/cheesesteak/32/3694_2.png) [@Cheesesteak](https://boards.straightdope.com/u/Cheesesteak)\ **Post date:** [April 20, 2026, 4:24pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/7 "2026-04-20T16:24:50Z")
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. ---
**Author:** ![colinfred](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/colinfred/32/21338_2.png) [@colinfred](https://boards.straightdope.com/u/colinfred)\ **Post date:** [April 20, 2026, 4:27pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/8 "2026-04-20T16:27:46Z")
> [@Cheesesteak](#): > > 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 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. ---
**Author:** ![colinfred](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/colinfred/32/21338_2.png) [@colinfred](https://boards.straightdope.com/u/colinfred)\ **Post date:** [April 20, 2026, 4:41pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/9 "2026-04-20T16:41:35Z")
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. ---
**Author:** ![zimaane](https://avatars.discourse-cdn.com/v4/letter/z/a3d4f5/32.png) [@zimaane](https://boards.straightdope.com/u/zimaane)\ **Post date:** [April 20, 2026, 5:30pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/10 "2026-04-20T17:30:08Z")
Good explanation, thanks I guess my intuition was off. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [April 20, 2026, 10:56pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/11 "2026-04-20T22:56:15Z")
Are they both playing from the same coin flips, or is each flipping their own coin? ---
**Author:** ![zimaane](https://avatars.discourse-cdn.com/v4/letter/z/a3d4f5/32.png) [@zimaane](https://boards.straightdope.com/u/zimaane)\ **Post date:** [April 20, 2026, 10:57pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/12 "2026-04-20T22:57:33Z")
Each flipping their own coin. Sorry if that wasn’t clear ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [April 21, 2026, 11:34am UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/13 "2026-04-21T11:34:32Z")
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. ---
**Author:** ![hibernicus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hibernicus/32/2802_2.png) [@hibernicus](https://boards.straightdope.com/u/hibernicus)\ **Post date:** [April 24, 2026, 10:18pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/14 "2026-04-24T22:18:30Z")
> [@DPRK](#): > > If you just start from scratch and flip coins, the expected time to get HTH is 10 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. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [April 25, 2026, 1:24am UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/15 "2026-04-25T01:24:35Z")
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. ---
**Author:** ![Pasta](https://avatars.discourse-cdn.com/v4/letter/p/ecccb3/32.png) [@Pasta](https://boards.straightdope.com/u/Pasta)\ **Post date:** [April 25, 2026, 4:12am UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/16 "2026-04-25T04:12:16Z")
> [@hibernicus](#): > > How is this calculated? 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 ---
**Author:** ![hibernicus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hibernicus/32/2802_2.png) [@hibernicus](https://boards.straightdope.com/u/hibernicus)\ **Post date:** [April 26, 2026, 9:38pm UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/17 "2026-04-26T21:38:09Z")
Thank you both for the clear explanations! ---
**Author:** ![Andy\_L](https://avatars.discourse-cdn.com/v4/letter/a/c67d28/32.png) [@Andy\_L](https://boards.straightdope.com/u/Andy_L)\ **Post date:** [April 27, 2026, 10:51am UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/18 "2026-04-27T10:51:13Z")
Rhis is a form of [Penney’s Game](https://en.wikipedia.org/wiki/Penney%27s_game), btw, a well-known non-transitive game ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [April 28, 2026, 1:11am UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/19 "2026-04-28T01:11:06Z")
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. ---
**Author:** ![LSLGuy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lslguy/32/5813_2.png) [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)\ **Post date:** [April 28, 2026, 1:18am UTC](https://boards.straightdope.com/t/probability-question-time-to-achieve-a-given-sequence-of-coin-flips/1029432/20 "2026-04-28T01:18:48Z")
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.