# The HH vs HT question

My puzzle is based on this tweet (image):

Flip a fair coin 100 times—it gives a sequence of heads (H) and tails (T). For each HH in the sequence of flips, Alice gets a point; for each HT, Bob does, so e.g. for the sequence THHHT Alice gets 2 points and Bob gets 1 point. Who is most likely to win?

The question in the tweet is a counterintuitive probability puzzle, which is quite tricky to solve. There are already great explanations available online; see the answers to this stats.stackexchange question, or this writeup by Mihai Nica. My question is a harder version of the puzzle.

Generalizing from $$100$$ flips to $$n$$ flips, let $$A_n$$ be the set of coins flip sequences of length $$n$$ where Alice wins, and let $$B_n$$ be the sequences of length $$n$$ where Bob wins. It turns out that the game favors Bob whenever $$n\ge 3$$, so that $$|B_n|>|A_n|$$.

Let $$B_n^*$$ be the set of sequences such that Bob wins, and where Bob stays winning even when an extra H is added to the end. This means that $$B^*_n$$ is a subset of $$B_n$$. For example, the sequence $$s=\mathsf{THTTH}$$ is in $$B_5$$, because $$s$$ has one $$\mathsf{HT}$$ and zero $$\mathsf{HH}$$'s. However, when you append an extra $$\mathsf{\color{blue}H}$$ to $$s$$, the result is $$\mathsf{THTTH{\color{blue}H}}$$. The extended sequence has one $$\mathsf{HH}$$ and one $$\mathsf{HT }$$, so Bob is no longer winning, meaning $$s$$ is not included in $$B_5^*$$.

Puzzle: Prove, for all $$n\ge 2$$, that $$|A_n|=|B^*_n|$$.

Source: This was originally asked by reddit use bobjane in this reddit post on the math riddles subreddit.

Here is an illustration of what I am asking you to prove when $$n=5$$. In the right column, I list all of the sequences of $$5$$ flips where Bob wins, but then I cross out the sequences that are removed to make $$B^*_5$$. As you can see, the remaining sequences in $$B^*_5$$ can be matched one-to-one with those in $$A_5$$.

$$A_5$$ $$B_5^*$$
HHHHH HTHTH
HHHHT HTHTT
HHHTH HTTHT
HHHTT HTTTT
HHTHH HHTHT
HTHHH HTHHT
THHHH THTHT
THHHT THTTT
TTHHH TTHTT
TTTHH TTTHT
HTTTH
THTTH
TTHTH
• IMHO this generalization is better to be asked in some other more math oriented SE topic.
– z100
Commented Jun 3 at 19:37
• The original question would have fit here as well but this seems primarily a maths question not a puzzle. Commented Jun 4 at 10:38
• This is a very interesting find! I want to construct a bijection of course, but it can't work to match sequences with HH/HT-difference $k$ to those of $-k$ because their respective counts are different.
– xnor
Commented Jun 4 at 20:18

One important thing to note that if

the game is ever later tied, then we are essentially in the same situation with a shorter sequence remaining, so we are done by induction. Let A be a minimal initial substring of the full sequence that starts HH, ends with H, with the score tied. I will call A an Alice tie. Similarly, let B be a minimal initial substring of the full sequence that starts HT and ends with H with the score tied. I'll call B a Bob tie. For example, if the full sequence is HHHTTHTHHT, then just the first HHHTTHTH is the Alice tie substring, since at that point the score is tied 2-2, and it is the shortest subtring starting at the start, ends with H, where the score is tied.

I'm going to show there is a sort of bijection between

Alice ties and Bob ties, which means there are the same number of Alice wins that start HH and Bob wins that start HT that never tie. Since there are the same number that never tie, and if we tie we're done by induction, that will complete the proof.

So what is this bijection between

Alice ties and Bob ties? Well, just literally reverse the substring. So in our example, we can reverse HHHTTHTH to HTHTTHHH and we have a Bob tie. Pretty easy, except of course there is a complication: while all Bob ties end in H, not all Alice ties end in H. For example, HHHTHTT, and this is necessarily not just a substring but the entire sequence. In this case, we append an H to the end HHHTHTTH, then reverse: HTTHTHHH. Of course, this is now too long in some sense, but this is exactly the strings we threw out when going from $$B_n$$ to $$B_n^*$$, so we're good! So while there are actually more Alice ties than Bob ties, if we include elements of $$B_n \setminus B_n^*$$ as Bob ties, then there is a bijection, so we are done.

• I understand the bijection between Alice ties and Bob ties, but how do you get a bijection between sequences that never tie? For example, what is the output of your bijection when the input is HHHHHH (six Hs)? Commented Jun 6 at 18:31
• I don't have an explicit bijection for never ties, but there are an equal number of sequences that start HH as HT, and if we "throw out" an equal number (because they tie or are in B_n - B_n^*), then what is left must also be equal. Commented Jun 6 at 18:50
• I understand now. Well done; you solved a puzzle that 90% of twitter could not! Your solution was much more elegant than the one I had in mind (I think that happens a lot with your answers to my questions!). Commented Jun 7 at 2:09
• lol with the 90% of twitter comment -- this one is about the same difficulty as 8 ÷ 2(2+2), right?? But thanks for posting this -- I spent a lot of time on it when bobjane posted it but didn't get anywhere, but when you posted it here I gave it a second try. Commented Jun 7 at 5:02
• Kinda funny that everything except the thing we care about seems to be in bijection. Anyway, neat argument! Commented Jun 7 at 6:58

unless I misunderstood the question....

I think:

The changes are equal 50-50...

Here is why:

Alice scores in 1 of then (HH), Bob scores in 1 of them (HT).
The other 2 score nothing for them.

Going further:

When the third coin is tossed, either one of them scores if, and only if the second coin was H and they score with a probability of 50%. If the second coin is T none of them score.

We can generalize this and say:

When tossing coin $$N+1$$ there are 2 cases (3 if you expand the second one).
1. If coin $$N$$ was T, nobody scores
2. If coin $$N$$ was H, both of them have a 50% chance of scoring.
This equilibrium is kept for any N >= 2.

• You have misunderstood the question. Consider the case where n=3. Of the 8 possible sequences, A wins on HHH, THH. B wins on HTH, HTT, THT. The other cases are ties: HHT, TTH, TTT. You correctly showed that A and B score the same amount of points on average, but B nonetheless wins more often. Commented Jun 4 at 9:03
• damn it....thanks for clearing it. Will leave this here for people to downvote until I find something better Commented Jun 4 at 9:07