The Generalized Alice HH Vs Bob HT Problem

In 2024, Daniel Litt posed a simple coinflip game pitting Alice’s “Heads–Heads” versus Bob’s “Heads–Tails”: Who is more likely to win if they score 1 point per occurrence of their substring in a sequence of n fair coinflips? This attracted over 1 million views on X and quickly spawned several articles explaining the counterintuitive solution. We study the generalized game, where the set of coin outcomes, $$\{ \text {Heads}, \text {Tails} \}$$ { Heads , Tails } , is generalized to an arbitrary finite alphabet $${\mathcal {A}}$$ A , and where Alice’s and Bob’s substrings are any finite $${\mathcal {A}}$$ A -strings of the same length. We find that the winner of Litt’s game can be determined by a single quantity which measures the amount of prefix/suffix self-overlaps in each string; whoever’s string has more overlaps loses. For example, “Heads–Tails” beats “Heads–Heads” in the original problem because “Heads–Heads” has a prefix/suffix overlap of length 1 while “Heads–Tails” has none. The method of proof is to develop a precise Edgeworth expansion for discrete Markov chains and apply this to calculate Alice’s and Bob’s probability to win the game correct to order O(1/n).