TL;DR
This paper provides a rigorous mathematical solution to a viral probability puzzle: in a sequence of coin flips, why is "Heads-Tails" (HT) more likely to outscore "Heads-Heads" (HH)? The authors generalize this to any alphabet and any string length, proving that the winner is determined by a single "overlap index"—essentially, the more a string overlaps with itself, the more likely it is to lose.
What Problem Does This Paper Address?
In early 2024, a math brainteaser went viral on X (formerly Twitter): Flip a fair coin 100 times; Alice gets a point for every "HH" and Bob gets a point for every "HT." Who is more likely to win?
While both patterns have a $1/4$ chance of appearing at any given position, the game is not fair. Bob is significantly more likely to win. This paper seeks to move beyond the specific "HH vs HT" case to a generalized theory. It addresses the "Generalized Litt’s Game," where players choose any two strings of the same length from any finite alphabet (like a 4-letter DNA sequence or a 26-letter alphabet) and compete over $n$ random draws. The goal is to find precise asymptotic formulas for the winning probabilities as the number of trials $n$ becomes large.
Methods
The authors model the scoring process using finite-state Markov chains. To get high-precision results, they develop a specific Edgeworth expansion for these chains.
While Central Limit Theorems can tell you that scores will eventually look like a Bell Curve (Normal distribution), Edgeworth expansions provide a "correction" to that curve to account for the fact that the scores are discrete integers. The authors provide a direct proof for this expansion in the context of Markov chains, which allows them to calculate winning, losing, and tie probabilities with an error of only $O(1/n)$.
Datasets
Not discussed in the paper. As a theoretical mathematics paper, it relies on formal proofs and asymptotic analysis rather than empirical datasets or benchmarks.
Key Insights and Ideas
- The Overlap Index ($\theta$): The core discovery is that the advantage in the game is dictated by how much a string overlaps with itself. For a string $A$, $\theta_{AA}$ measures its prefix/suffix self-overlaps.
- Clumping Leads to Losing: Strings with high self-overlap (like "AAAAA") tend to "clump" together in a random sequence. While this doesn't change the average number of occurrences, it increases the variance. In a head-to-head race over a fixed number of flips, this increased volatility actually makes the clumping string more likely to be outscored by a "smoother," non-overlapping string (like "ABCDE").
- The "Fairness" Rule: The authors prove that the game is asymptotically fair if and only if the two strings have the exact same overlap index ($\theta_{AA} = \theta_{BB}$).
- Pathological Exceptions: The paper identifies a small set of "pathological" strings (like HT vs TH) where the general asymptotic theory fails because the scores are constrained in a way that prevents a normal distribution from forming (e.g., the difference in scores can only ever be -1, 0, or 1).
Key Results
-
The HH vs HT Gap: For the original puzzle, the paper confirms that the probability gap is: $$P(\text{Bob wins}) - P(\text{Alice wins}) \sim \frac{1}{2\sqrt{\pi n}}$$ For $n=100$ flips, this gap is approximately $0.028$, a small but decisive advantage for Bob.
-
General Winning Formulas: Theorem 1.1 provides the precise winning probabilities for any valid strings $A$ and $B$: $$P(\text{Alice wins}) = \frac{1}{2} + \frac{\theta_{BB} - \theta_{AA} - 1}{2\sqrt{2\pi\sigma^2}}n^{-1/2} + O(n^{-1})$$ This formula explicitly shows that if Bob's string has less overlap ($\theta_{BB} < \theta_{AA}$), Alice's winning probability drops below 1/2.
-
Tie Probability: The probability of a tie is also precisely calculated as $P(\text{Tie}) \sim \frac{1}{\sqrt{2\pi\sigma^2n}}$.
Limitations and Future Work
- Equal Length Constraint: The current theory assumes Alice and Bob choose strings of the same length $\ell$. While the authors briefly discuss extensions for different lengths, a full generalized theory for unequal lengths is more complex.
- Uniform Distribution: The main results assume each letter in the alphabet is chosen with equal probability (a "fair" coin). While they suggest the method can be extended to non-uniform distributions, they leave the detailed calculations to the reader.
- Multiple Strings: The paper primarily focuses on one string per player. Extending this to cases where players score points for multiple different patterns (e.g., Alice gets points for HH or TT) is noted as a more difficult open problem.
Summary updated