The Generalized Alice HH Vs Bob HT Problem

Svante Janson (), Mihai Nica () and Simon Segert ()
Additional contact information
Svante Janson: Uppsala University
Mihai Nica: University of Guelph
Simon Segert: Independent Researcher

Journal of Theoretical Probability, 2025, vol. 38, issue 4, 1-52

Abstract: Abstract 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).

Keywords: Markov; chains; .; Edgeworth; expansion; .; Random; sequence; .; Coin; flips; 60J10 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-025-01452-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:38:y:2025:i:4:d:10.1007_s10959-025-01452-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-025-01452-7

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().