The HH vs HT question

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

Answer 1

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.

Answer 2

unless I misunderstood the question....

I think:

The changes are equal 50-50...

Here is why:

Let's start with 2 coins. There are possible outcomes.
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.