# On cases where Litt's game is fair

Anne-Laure Basdevant, Olivier Hénard, Édouard Maurel-Segala, Arvind Singh

► To cite this version:

Anne-Laure Basdevant, Olivier Hénard, Édouard Maurel-Segala, Arvind Singh. On cases where Litt's game is fair. Comptes Rendus. Mathématique, 2025, 363 (G10), pp.977-984. 10.5802/crmath.783. hal-05405546

HAL Id: hal-05405546

https://hal.science/hal-05405546v1

Submitted on 8 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Comptes Rendus
Mathématique

Anne-Laure Basdevant, Olivier Hénard, Édouard Maurel-Segala and Arvind Singh

On cases where Litt's game is fair

Volume 363 (2025), p. 977-984

Online since: 5 September 2025

https://doi.org/10.5802/crmath.783

<figure><img src="image_2.png" /></figure>

This article is licensed under the

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/
Research article / *Article de recherche*
Probability theory / *Probabilités*

# On cases where Litt's game is fair

## *Sur des cas où le jeu de Litt est équitable*

Anne-Laure Basdevant<sup>a</sup>, Olivier Hénard<sup>b</sup>, Édouard Maurel-Segala<sup>b</sup> and
Arvind Singh<sup>b</sup>

<sup>a</sup> Sorbonne Université, CNRS, Laboratoire de Probabilités, Statistique et Modélisation, 75205 Paris, France

<sup>b</sup> Université Paris-Saclay, CNRS, Laboratoire de mathématiques d'Orsay, 91405 Orsay, France

*E-mails:* anne.laure.basdevant@normalesup.org, olivier.henard@universite-paris-saclay.fr, edouard.maurel-segala@universite-paris-saclay.fr, arvind.singh@universite-paris-saclay.fr

**Abstract.** A fair coin is flipped $n$ times, and two finite sequences of heads and tails with the same length are given, say $A$ and $B$. Each time $A$ appears in the sequence of fair coin flips, Alice gets a point, and each time $B$ appears, Bob gets a point. Who is more likely to win? This puzzle is a slight extension of Litt's game [10]. In this note, we show that the game is fair for any value of $n$ and any two words $A, B$ that have the same auto-correlation structure by building up a bijection that exchanges Bob and Alice scores. It is remarkable that the inter-correlations between $A$ and $B$ do not play any role in this case. Additionally, we propose a conjecture for cases where the game is unfair, providing insights into the underlying structure of the game for a fixed $n$.

**Résumé.** Une pièce équilibrée est lancée $n$ fois, et deux suites finies $A$ et $B$ de piles et faces de même longueur sont données. Chaque fois que $A$ apparaît dans la suite de lancers de la pièce, Alice gagne un point, et chaque fois que $B$ apparaît, Bob gagne un point. Qui a le plus de chances de gagner ? Ce problème est une légère extension du jeu de Litt [10]. Nous montrons que le jeu est équitable pour toute valeur de $n$ et pour toute paire de mots $A, B$ ayant la même structure d'auto-corrélation, en construisant une bijection qui échange les scores de Bob et Alice. Le fait que les inter-correlations entre $A$ et $B$ ne jouent aucun rôle ici est remarquable. De plus, nous proposons une conjecture pour les cas où le jeu est inéquitable, qui témoigne de la structure riche du jeu de taille finie.

**Keywords.** Coin flips, pattern counts, stochastic games.

**Mots-clés.** Pile ou face, motifs, jeu aléatoire.

**2020 Mathematics Subject Classification.** 60C05.

Manuscript received 26 March 2025, revised 19 June 2025, accepted 14 July 2025.

## 1. Introduction and main results

In [10], Litt came up with the following puzzle: a fair coin is tossed $n$ times, Alice gets a point each time the sequence HH appears, while Bob scores a point each time the sequence HT appears (and these sequences may be overlapping). The game may result in a win for Alice, a win for Bob or a tie (the possibilities being exclusive). Who is more likely to win, Alice or Bob? The perhaps surprising answer is that:

(1) for any size $n \ge 3$, Bob is more likely to win than Alice;
(2) for $n$ large, it holds:

$$2 \times (\mathbb{P}_n(\text{Bob wins}) - \mathbb{P}_n(\text{Alice wins})) \sim \mathbb{P}_n(\text{Tie}) \sim \frac{1}{\sqrt{\pi n}}.$$

Several elements of proofs for the first fact quickly emerged on X [13,14,16], then more formal proofs of both facts appeared on the arXiv [3,15]. Zeilberger online journal [4] maintains a list of contributions and questions on the problem.

Among the proofs given, we would like to advertise an early probabilistic proof: in [13], Ramesh builds a “fair majorant” for the score difference of Alice and Bob that consists in a delayed simple random walk; the score difference of Alice and Bob is a deterministic function of this walk, at distance at most 1 below it, see Section 3 for the full details. A rigorous proof of both facts (1) and (2) is then at an easy reach. Another by-product of his approach is that giving Alice an initial advantage of only one point reverses the statement of fact (1) in a strong sense: for any size $n \ge 0$, Alice then has probability strictly greater than 1/2 of winning. In particular, Alice is more likely to win than Bob. This approach has been detailed in Grimmett [6], who recently rediscovered the arguments of Ramesh.

Considering a contest between HT and TH is also possible, but arguably less interesting since flipping the sequence of tosses, or reading the sequence in the reverse order exchanges Alice and Bob points, which results in a fair game. The aim of this note is to uncover more subtle symmetries within the words ensuring the game is again fair.

For $\ell \ge 0$, a word of length $\ell$ is a sequence $A = (a_1, \dots, a_\ell)$ in $\{\text{H}, \text{T}\}^\ell$. For $X_n := (\epsilon_k)_{1 \le k \le n}$ a finite sequence in $\{\text{H}, \text{T}\}^n$, we denote by

$$N_A(X_n) := |\{\ell \le k \le n, (\epsilon_{k-\ell+1}, \dots, \epsilon_k) = (a_1, \dots, a_\ell)\}|$$

the number of occurrences of the word $A$ in the sequence $X_n$. Let $A$ and $B$ be two words of length $\ell$. In the generalized Litt's game, Alice wins if $N_A(X_n) > N_B(X_n)$, Bob wins if $N_B(X_n) > N_A(X_n)$, and the game is a tie otherwise.

A key quantity encoding the intersections of $A$ and $B$ is the correlation of $A$ and $B$, which may be represented as a subset of integers or simply as a number (the base 2 expansion of the subset):

$$[A|B] = \sum_{k \in \text{Cor}(A,B)} 2^k \quad \text{where} \quad \text{Cor}(A,B) = \{1 \le k \le \ell-1, (a_{\ell-k+1}, \dots, a_\ell) = (b_1, \dots, b_k)\}.$$

To be more specific, we shall call *inter-correlation* the correlation of two distinct words (beware the order matters), and *auto-correlation* the correlation of a word with itself. The main result in this note is that Litt's game, played with a uniform sequence of toss $X_n$, is fair for any pair of words $A$ and $B$ with the same auto-correlation. Surprisingly, this result holds regardless of the inter-correlation between $A$ and $B$.

**Theorem 1.** Let $A, B$ two words of length $\ell$ such that $[A|A] = [B|B]$. Assume that, under $\mathbb{P}_n$, the letters $(\epsilon_i)_{1 \le i \le n}$ of $X_n$ form an i.i.d. sequence with the uniform distribution on $\{\text{H}, \text{T}\}$. Then for each $n \ge 1$, the random variables $(N_A(X_n), N_B(X_n))$ and $(N_B(X_n), N_A(X_n))$ have the same distribution. In particular, for any $n \ge 1$,

$$\mathbb{P}_n(\text{Bob wins}) = \mathbb{P}_n(\text{Alice wins}). \qquad (1)$$

For instance, the words $A = \text{HHTHTH}$ and $B = \text{HTTTHH}$ have the same auto-correlation hence Litt's game played with $A$ and $B$ is fair despite the apparent lack of symmetry between these words and their non-trivial inter-correlations<fnref n="1" />. We also point out that, even though $(N_A(X_n), N_B(X_n))$ is exchangeable when $[A|A] = [B|B]$, the law of this couple still depends on the inter-correlation $[A|B]$ and $[B|A]$.

<footnote n="1">¹In this case, we have $[A|A] = [B|B] = 2$, $[A|B] = 2$ and $[B|A] = 6$.</footnote>
It is possible to estimate the probability (1) of Alice (or Bob) winning, as well as the probability of a tie using a Local Central Limit theorem for sums of weakly dependent random variables. In a recent preprint [8] (posted after the present result was announced), Janson, Nica and Segert develop a method based on Edgeworth expansions to tackle the general case of words A and B with possibly distinct auto-correlations. Their main result states that, for $A \neq B$, as $n$ gets large, the following asymptotics

$$ \mathbb{P}_n(\text{Bob wins}) - \mathbb{P}_n(\text{Alice wins}) = \frac{[A|A] - [B|B]}{\sqrt{2^\ell + [A|A] + [B|B] - [A|B] - [B|A]}} \cdot \frac{1}{2\sqrt{\pi n}} + o\left(\frac{1}{\sqrt{n}}\right), \quad (2) $$

$$ \mathbb{P}_n(\text{Tie}) = \frac{2^\ell}{\sqrt{2^\ell + [A|A] + [B|B] - [A|B] - [B|A]}} \cdot \frac{1}{2\sqrt{\pi n}} + o\left(\frac{1}{\sqrt{n}}\right), \quad (3) $$

hold as soon as the denominators on both RHS are non null<fnref n="2" />. In the case $[A|A] = [B|B]$, Theorem 1 proved in this note refines on the first formula by stating that the quantity is, in fact, identically null for all $n$. Furthermore, in light of (2), Theorem 1 covers all cases where the game is fair.

A key feature of (2) is that $\mathbb{P}_n(\text{Bob wins}) - \mathbb{P}_n(\text{Alice wins})$ has, asymptotically, the sign of $[A|A] - [B|B]$. In light of this observation together with some extensive numerical computations<fnref n="3" />, we are lead to state the following remarkable conjecture for a fixed length $n$ of the underlying word $X_n$. We use $\Delta$ to denote the symmetric difference of two sets.

**Conjecture 2.** Assume $[A|A] > [B|B]$. Then, for each $n \ge n_0 := 2^\ell - \max\{\text{Cor}(A)\Delta\text{Cor}(B)\}$,

$$ \mathbb{P}_n(\text{Alice wins}) < \mathbb{P}_n(\text{Bob wins}) < \frac{1}{2} < \mathbb{P}_n(\text{Alice wins}) + \mathbb{P}_n(\text{Tie}). $$

Some comments are in order. First, the restriction to $n \ge n_0$ is necessary for the first inequality only (the most important one indeed), and we have equality for $n < n_0$. Also, the last two inequalities are equivalent (and valid for each $n \ge 0$), but we like to phrase the conjecture this way, because of the following vivid interpretation of this set of inequalities: even if Alice loses in the standard version of the game (first inequality), if we were to give Alice *one additional point*<fnref n="4" />, then her new winning probability would exceed 1/2 for each $n$ (last inequality); in particular, Alice would be advantaged over Bob at each subsequent time. Conjecture 2 also suggests that the advantage of Bob versus Alice may be put in bijection with a subset of the Tie event. Conjecture 2 is valid for the original Litt's game (HH versus HT) by Ramesh's proof. Also, it is in line with the asymptotics above: to see this, notice the last two inequalities in the conjecture are equivalent to

$$ |\mathbb{P}_n(\text{Alice wins}) - \mathbb{P}_n(\text{Bob wins})| < \mathbb{P}_n(\text{Tie}), $$

which may be checked from the conjectured asymptotics because of the inequality $|[A|A] - [B|B]| \le 2^\ell - 2$ that is true for every pair of words A, B.

The statement contained in Conjecture 2 is remarkable because there are very few settings where such fixed length results hold for pattern matching: another famous exception is the fact that the number of words of fixed length $n$ avoiding $A$ is larger than the number of words of length $n$ avoiding $B$ if $[A|A] > [B|B]$, for each $n \ge n_0$, where $n_0$ is again defined as in Conjecture 2, and with equality before. For $n$ large enough (larger than an indefinite constant), the statement has been stated and proved by Guibas and Odlyzko [7] and independently by Blom [1], while the result for all $n \ge n_0$ has been established by Månnson [11] after a series of works on the topic [2,5].

<footnote n="2">²The pairs of words giving a null denominator are (T, H), $(TH^{\ell-1}, H^{\ell-1}T)$ for $\ell \ge 2$, and those pairs obtained by interchanging H and T. They all correspond to degenerate cases.</footnote>

<footnote n="3">³The conjecture has been checked for all words A and B of size $\le 10$ and for $n \le 35$.</footnote>

<footnote n="4">⁴Beware this is distinct from starting the random word $X_n$ with the word A.</footnote>
Finally, we point that the general topic of pattern matching and overlaps has been the subject of many investigations, starting with the non-transitive *Penney-Ante game* named after Penney [12] (and famously solved by Conway) in which one is asked to compute the probability that *A* appears before *B* in a sequence of fair coin flips, see [7,9] and the references therein.

## 2. Proof of Theorem 1

The auto-correlation and inter-correlation of two words are quantities that appear naturally when we look at the probability of one word appearing before another in a sequence of coin flips. The formal definition, which we repeat below, is the following.

**Definition 3.** Let A, B be two words of length *ℓ*. We define the indices of inter-correlation of A and B by

$$ \mathrm{Cor}(A, B) = \{1 \le k \le \ell - 1, (a_{\ell-k+1}, \dots, a_{\ell}) = (b_1, \dots, b_k)\}. $$

We write $\mathrm{Cor}(A)$ to denote $\mathrm{Cor}(A, A)$. We define the inter-correlation $[A|B]$ of $(A, B)$ by

$$ [A|B] = \sum_{k \in \mathrm{Cor}(A,B)} 2^k $$

and the auto-correlation of A as $[A|A]$.

Let us make some remarks about this definition:

* the number $[A|B]$ is not in general equal to $[B|A]$;

* for all A, B of length *ℓ*, $[A|B] \in [0; 2^\ell - 2]$;

* for every words A, B, C, D of length *ℓ*, $[A|B] = [C|D]$ if and only if $\mathrm{Cor}(A, B) = \mathrm{Cor}(C, D)$.

Fix any two words A and B with length *ℓ* and the same auto-correlation. To prove that $(N_A(X_n), N_B(X_n))$ has the same law as $(N_B(X_n), N_A(X_n))$, we prove the existence of a bijection $\phi$ from $\{H, T\}^n$ to $\{H, T\}^n$ such that, for any sequence $X_n \in \{H, T\}^n$, $(N_A(X_n), N_B(X_n)) = (N_B(\phi(X_n)), N_A(\phi(X_n)))$. The rest of the paper is devoted to the construction of $\phi$.

We introduce some additional notation. If C, D are two words, CD will be the concatenation of C and D. Besides, for two words C, D of length *ℓ* and *m* ∈ $\mathrm{Cor}(C, D)$, we denote $C^m D$ the word of length $2\ell - m$ beginning by C and ending by D. For example, if $C = \underline{HTTHTH}$, $D = \overline{THTHHH}$, we have $C^2 D = \underline{HTTHTHTHHH}$. We extend this notation to *k* words $C_1, \dots, C_k$ of length *ℓ* and $m_1, \dots, m_k \ge 1$ in the obvious way: if $m_i \in \mathrm{Cor}(C_i, C_{i+1})$ for each *i*, we define the word of length $k\ell - \sum m_i$

$$ Y = C_1^{m_1} C_2^{m_2} C_3^{m_3} \cdots C_{k-1}^{m_{k-1}} C_k. \qquad (4) $$

**Definition 4.** Let A, B be two words of length *ℓ*. A word Y of the form (4) where $C_1, \dots, C_k \in \{A, B\}^k$ is called an overlap of A and B. We denote by $\mathcal{E}(A, B)$ the set of all overlaps of A and B.

Note that do not accept $m_i = 0$ in (4). In particular, the concatenation $Y = AB$ of A and B may not be in $\mathcal{E}(A, B)$. We notice also that, for $Y \in \mathcal{E}(A, B)$, the expression of Y in the form given by (4) may be not unique. We shall say a decomposition of Y is maximal if, writing $Y = C_1^{m_1} C_2^{m_2} C_3^{m_3} \cdots C_{k-1}^{m_{k-1}} C_k$, we have

$$ N_A(Y) = |\{1 \le i \le k, C_i = A\}| \quad \text{and} \quad N_B(Y) = |\{1 \le i \le k, C_i = B\}|. $$

We have the following decomposition of a word.

**Definition 5.** Let Y be a word. There exists a unique way to write Y in the form

$$ Y = X_0 E_1 X_1 E_2 \cdots X_{k-1} E_k X_k \qquad (5) $$

such that

* the words $E_1, \dots, E_k$ belong to $\mathcal{E}(A, B)$;
* for all $i \in [0, k]$, neither A nor B appears in $X_i$ (which may be empty);

* $N_A(Y) = \sum_{i=1}^k N_A(E_i)$ and $N_B(Y) = \sum_{i=1}^k N_B(E_i)$.

We say that the words $(E_1, \dots, E_k)$ which appear in (5) form the pattern of the word Y with respect to A and B, and we write: $\mathbf{Patt}_{A,B}(Y) = (E_1, E_2, \dots, E_k)$.

**Proposition 6.** Let A, B be two words with the same auto-correlation, and let $\phi: \mathcal{E}(A, B) \to \mathcal{E}(A, B)$ be defined in the following way. If $Y := C_1^{m_1} C_2^{m_2} \cdots C_{k-1}^{m_{k-1}} C_k$ with $C_i \in \{A, B\}$, we set

$$ \phi(Y) = \bar{C}_k^{m_{k-1}} \bar{C}_{k-1}^{m_{k-2}} \cdots \bar{C}_2^{m_1} \bar{C}_1 $$

where $\bar{C}_i = A$ if $C_i = B$ and $\bar{C}_i = B$ if $C_i = A$. Then $\phi$ is well-defined, it is independent of the decomposition chosen for Y, it is an involution and $\phi(Y)$ has the same length as Y. Moreover, we have $(N_A(Y), N_B(Y)) = (N_B(\phi(Y)), N_A(\phi(Y)))$.

For instance, setting $A = \text{HHTH}$ and $B = \text{THHT}$, the reader may check that applying $\phi$ to each of the two representations of the word $Y = \text{HHTHHTHHTH} = A^1 A^1 A = A^2 B^3 A^2 B^3 A$ yields the same word $\phi(Y) = \text{THHTHHHTHHHT} = B^1 B^1 B = B^3 A^2 B^3 A^2 B$.

**Proof.** We first prove that $\phi(Y)$ is well defined i.e. if $m_i \in \text{Cor}(C_i, C_{i+1})$, then $m_i \in \text{Cor}(\bar{C}_{i+1}, \bar{C}_i)$. Recall that we assume that A, B have the same auto-correlation, i.e. $\text{Cor}(A) = \text{Cor}(B)$. We have two cases:

* Either $C_i = C_{i+1}$, for example $C_i = A$. Then $\bar{C}_i = \bar{C}_{i+1} = B$. Hence, we have $\text{Cor}(C_i, C_{i+1}) = \text{Cor}(A) = \text{Cor}(B) = \text{Cor}(\bar{C}_{i+1}, \bar{C}_i)$.

* Or $C_i \neq C_{i+1}$, for example $(C_i, C_{i+1}) = (A, B)$. Then $(\bar{C}_{i+1}, \bar{C}_i)$ is also equal to $(A, B)$ and so $\text{Cor}(C_i, C_{i+1}) = \text{Cor}(\bar{C}_{i+1}, \bar{C}_i)$.

Note that $\phi$ does not depend on the decomposition chosen for Y. To justify this claim, it is enough to consider the case of words Y with two decompositions $Y = C_1^{m_1} C_2^{m_2} C_3$ and $Y = C_1^m C_3$. Note that $|Y| = 2\ell - m = 3\ell - m_1 - m_2$. Applying $\phi$ with the first decomposition we get $\phi(Y) = \bar{C}_3^{m_2} \bar{C}_2^{m_1} \bar{C}_1$ and since $|\phi(Y)| = |Y| < 2\ell$, necessarily, $\bar{C}_3$ and $\bar{C}_1$ overlap in the writing of $\phi(Y)$ and thus we also have $\phi(Y) = \bar{C}_3^m \bar{C}_1$. The fact that $\phi$ is an involution is clear.

We write now Y with its maximal decomposition i.e. $Y := C_1^{m_1} C_2^{m_2} \cdots C_{k-1}^{m_{k-1}} C_k$ with maximal $k$. By construction, we directly get that $N_A(\phi(Y)) \ge N_B(Y)$ and $N_B(\phi(Y)) \ge N_A(Y)$. We claim that, by maximality of the decomposition, there is equality in these two inequalities. Indeed, consider the case of words Y whose maximal decomposition consist in two words: $C_1^m C_2$. Among those words Y, only the words where $C_1 = C_2$ have to be considered. If $Y_0 = C_1^m C_1$, it holds $\phi(Y_0) = \bar{C}_1^m \bar{C}_1$. Now, assume that $\phi(Y_0) = \bar{C}_1^{m_1} \bar{C}_3^{m_2} \bar{C}_1$ for some $C_3 \in \{A, B\}$. The map $\phi$ being independent of the decomposition, we get $Y_0 = \phi(\phi(Y_0)) = C_1^{m_1} \bar{C}_3^{m_2} C_1$, which has a distinct count of the $\bar{C}_3$-word; this negates the fact that $Y_0 = C_1^m C_1$ is the maximal decomposition in the first place. $\square$

The function $\phi$ defined in the previous proposition can be extended to a function on patterns. For $(E_1, \dots, E_k) \in \mathcal{E}(A, B)^k$, we set

$$ \phi(E_1, \dots, E_k) = (\phi(E_k), \dots, \phi(E_1)) $$

which defines an involution on $\mathcal{E}(A, B)^k$. Given a pattern $M = (E_1, \dots, E_k) \in \mathcal{E}(A, B)^k$ and $n \ge 1$, we define $L_M(n)$ as the number of words of length $n$ with pattern $M$:

$$ L_M(n) = |\{\text{word } Y, |Y| = n \text{ and } \mathbf{Patt}_{A,B}(Y) = M\}|. $$

To prove Theorem 1, it is sufficient to show that, for any pattern $M$ and any $n \ge 1$, we have

$$ L_M(n) = L_{\phi(M)}(n). \qquad (6) $$
Indeed, if $Y$ is a word such that $\textbf{Patt}_{A,B}(Y) = M$ and $Z$ is a word such that $\textbf{Patt}_{A,B}(Z) = \phi(M)$, we have

$$ (N_A(Y), N_B(Y)) = \left( \sum_{i=1}^{k} N_A(E_i), \sum_{i=1}^{k} N_B(E_i) \right) = \left( \sum_{i=1}^{k} N_B(\phi(E_i)), \sum_{i=1}^{k} N_A(\phi(E_i)) \right) = (N_B(Z), N_A(Z)). $$

In view of equality (6), we conclude that

$$ \begin{aligned} P((N_A(X_n), N_B(X_n)) = (a, b)) &= \frac{1}{2^n} \sum_{\substack{\text{pattern } M \text{ s.t.} \\ (N_A(M), N_B(M)) = (a,b)}} L_M(n) \\ &= \frac{1}{2^n} \sum_{\substack{\text{pattern } M \text{ s.t.} \\ (N_A(M), N_B(M)) = (a,b)}} L_{\phi(M)}(n) \\ &= P((N_B(X_n), N_A(X_n)) = (a, b)). \end{aligned} $$

In order to establish (6), we prove the slightly more precise result:

**Lemma 7.** For any pattern $M = (E_1, \dots, E_k)$, for any $I = (i_0, \dots, i_k)$, set

$$ L^M(I) = |\{Y = X_0 E_1 X_1 \cdots E_k X_k : \textbf{Patt}_{A,B}(Y) = M; \forall j, |X_j| = i_j\}|. $$

Then

$$ L^M(I) = L^{\phi(M)}(I') $$

where $I' = (i_k, \dots, i_0)$.

To paraphrase the lemma, there are as many words admitting a given pattern $M$ and spacings $I$ between the overlaps constituting $M$, than there are admitting the dual pattern $\phi(M)$ and the dual spacings $I'$ between the overlaps of $\phi(M)$, where $I'$ is $I$ read from right to left. Since the proof is by induction on the length of the spacings between the overlaps, the question of a constructive "natural" bijection remains open.

**Proof.** Let us remark that we have

$$ L^M(I) = L^{E_1}(i_0, 0) \left( \prod_{j=1}^{k-1} L^{(E_j, E_{j+1})}(0, i_j, 0) \right) L^{E_k}(0, i_k) $$

and

$$ L^{\phi(M)}(I') = L^{\phi(E_k)}(i_k, 0) \left( \prod_{j=1}^{k-1} L^{(\phi(E_{j+1}), \phi(E_j))}(0, i_j, 0) \right) L^{\phi(E_1)}(0, i_0). $$

Moreover, the value of $L^{(E_j, E_{j+1})}(0, i_j, 0)$ only depends on $i_j$, on the word ending $E_j$ and on the word beginning $E_{j+1}$. For example, if $E_j$ ends with an $A$ and $E_{j+1}$ starts with a $B$, we have

$$ L^{(E_j, E_{j+1})}(0, i_j, 0) = L^{(A, B)}(0, i_j, 0). $$

Now, if $E_j$ ends with an $A$ and $E_{j+1}$ starts with a $B$, then $\phi(E_{j+1})$ ends with an $A$ and $\phi(E_j)$ starts with a $B$. Thus, in this case, we directly get

$$ L^{(\phi(E_{j+1}), \phi(E_j))}(0, i_j, 0) = L^{(E_j, E_{j+1})}(0, i_j, 0) = L^{(A, B)}(0, i_j, 0). $$

The situation is more involved when $E_j$ ends with the same word than $E_{j+1}$ starts with, let say the word $A$. Then indeed

$$ L^{(\phi(E_{j+1}), \phi(E_j))}(0, i_j, 0) = L^{(B, B)}(0, i_j, 0) \quad \text{while} \quad L^{(E_j, E_{j+1})}(0, i_j, 0) = L^{(A, A)}(0, i_j, 0). $$

Besides, if $E_1$ starts with $A$, then $\phi(E_1)$ ends with a $B$, and we have

$$ L^{\phi(E_1)}(0, i_0) = L^{(B)}(0, i_0) \quad \text{while} \quad L^{E_1}(i_0, 0) = L^{(A)}(i_0, 0), $$
and a similar assertion holds for $L^{E_k}(0, i_k)$ and $L^{\phi(E_k)}(i_k, 0)$. Combining all these remarks, we see
that Lemma 7 will be proved as soon as we establish the following equality: for each $i \ge 0$,

$$
L^{(A,A)}(0, i, 0) = L^{(B,B)}(0, i, 0) \quad \text{and} \quad L^{(B)}(0, i) = L^{(A)}(i, 0). \tag{7}
$$

We prove (7) by induction on $i$. The proposition clearly holds for $i=0$. Assume it holds for $k \le i-1$. Thus, for any pattern $M$, if $I = (i_0, \dots, i_k)$ with $i_j < i$ for all $j$, we get

$$
L^M(I) = L^{\phi(M)}(I').
$$

Let us now prove that $L^{(B)}(0, i) = L^{(A)}(i, 0)$. Writing $|I| = \sum_{j=0}^k i_j$ if $I = (i_0, \dots, i_k)$ and $|M| = \sum_{i=1}^k |E_i|$ for the length of the pattern $M = (E_1, \dots, E_k)$, we find that

$$
\begin{align*}
L^{(A)}(i, 0) &= \left| \left\{ \text{words } XA : |X| = i \text{ and } \mathbf{Patt}_{A,B}(XA) = A \right\} \right| \\
&= 2^i - \sum_{k \ge 1} \sum_{\substack{M=(E_1, \dots, E_k) \ne (A) \\ E_k \text{ ends with } A}} \sum_{\substack{I=(i_0, \dots, i_{k-1}, 0) \\ |I| + |M| = i + |A|}} L^M(I) \\
&= 2^i - \sum_{k \ge 1} \sum_{\substack{M=(E_1, \dots, E_k) \ne (A) \\ E_k \text{ ends with } A}} \sum_{\substack{I=(i_0, \dots, i_{k-1}, 0) \\ |I| + |M| = i + |A|}} L^{\phi(M)}(I').
\end{align*}
$$

At this point, we use the recurrence assumption noticing that |I| < i since |M| > |A|. Recalling
that if M ends with A, then φ(M) starts with B, we see that the last line is also equal to

$$
2^i - \sum_{k \ge 1} \sum_{\substack{M=(E_1, \dots, E_k) \ne (B) \\ E_1 \text{ starts with } B}} \sum_{\substack{I=(0, i_1, \dots, i_k) \\ |I| + |M| = i + |B|}} L^M(I) = L^{(B)}(0, i).
$$

The equality $L^{(A,A)}(0, i, 0) = L^{(B,B)}(0, i, 0)$ is proved with a similar argument. $\square$

<figure><img src="image_3.png" /></figure>

3. Ramesh original argument

For the ease of reference, we reproduce here verbatim the original tweets [13] of Sridhar Ramesh
on the original HH versus HT game with the permission of their author:

"Consider a random walk in which one takes equally likely steps of one unit up or one unit down, but with different distributions of speeds. (E.g., maybe up steps take one hour, while down steps have probability 1/2 of taking 2 hours, 1/4 of taking 3 hours, 1/8 of 4 hours, etc). The time it takes to return to the origin is independent of whether the first step is up and last step is down or vice versa, as doing the same steps in reverse order has the same probability. Thus, for any fixed walk time, the last step away from the origin begun before the time limit is equally likely to be up or down. Thus, at the end when "the buzzer goes off", one is equally likely to be above or below the origin (possibly in the middle of an uncompleted step). Applied to our game, with HH as a step up in one unit of time and HTⁿH as a step down over n+1 units of time, this says we are equally likely to end above the origin (Alice wins or we are in the middle of an HTⁿH step which has tied the game) or below it (Bob wins). Since it is indeed possible to end in the middle of a game-tying HTⁿH step (e.g., if the game consists of HHT followed by all T's), Alice is less likely to win than Bob. QED. The salient difference is that the "buzzer" can cut off HTⁿH in the middle (after awarding Bob a game-tying point but before returning to H), which it cannot do for HH. The random walk framing perhaps allows some ready generalization to other interesting problems."
**Declaration of interests**

The authors do not work for, advise, own shares in, or receive funds from any organization that could benefit from this article, and have declared no affiliations other than their research organizations.

**References**

[1] G. Blom, "On the stochastic ordering of waiting times for patterns in sequences of random digits", *J. Appl. Probab.* **21** (1984), no. 4, pp. 730–737.

[2] I. Cakir, O. Chryssaphinou and M. Månsson, "On a conjecture by Eriksson concerning overlap in strings", *Comb. Probab. Comput.* **8** (1999), no. 5, pp. 429–440.

[3] S. B. Ekhad and D. Zeilberger, "How to answer questions of the type: If you toss a coin *n* times, how likely is HH to show up more than HT?", 2024. Online at https://arxiv.org/abs/2405.13561.

[4] S. B. Ekhad and D. Zeilberger, "How to answer questions of the type: If you toss a coin *n* times, how likely is HH to show up more than HT?", in *Doron Zeilberger's personal (online) journal*, 2024. Online at https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/litt.html.

[5] K. Eriksson, "Autocorrelation and the enumeration of strings avoiding a fixed string", *Comb. Probab. Comput.* **6** (1997), no. 1, pp. 45–48.

[6] G. R. Grimmett, "Alice and Bob on $\mathcal{X}$: reversal, coupling, renewal", 2024. Online at https://arxiv.org/abs/2409.00732.

[7] L. J. Guibas and A. M. Odlyzko, "String overlaps, pattern matching, and nontransitive games", *J. Comb. Theory, Ser. A* **30** (1981), no. 2, pp. 183–208.

[8] S. Janson, M. Nica and S. Segert, "The generalized Alice HH vs Bob HT problem", 2025. Online at https://arxiv.org/abs/2503.19035.

[9] S.-Y. R. Li, "A martingale approach to the study of occurrence of sequence patterns in repeated experiments", *Ann. Probab.* **8** (1980), no. 6, pp. 1171–1176.

[10] D. Litt, *Flip a fair coin 100 times*, post on X (@littmath), March 16, 2024. Online at https://x.com/littmath/status/1769044719034647001 (accessed on July 31, 2025).

[11] M. Månsson, "Pattern avoidance and overlap in strings", *Comb. Probab. Comput.* **11** (2002), no. 4, pp. 393–402.

[12] W. Penney, "Penney-Ante, Problem 95", *J. Recreat. Math.* **2** (1969), no. 4, p. 241.

[13] S. Ramesh, *Consider a random walk*, post on X (@RadishHarmers), March 19, 2024. Online at https://x.com/RadishHarmers/status/1770217475960885661 (accessed on July 31, 2025).

[14] S. Ramesh, *Here are two bijective proofs*, post on X (@RadishHarmers), March 20, 2024. Online at https://x.com/RadishHarmers/status/1770530578179198981 (accessed on July 31, 2025).

[15] S. Segert, "A proof that HT is more likely to outnumber HH than vice versa in a sequence of *n* coin flips", 2024. Online at https://arxiv.org/abs/2405.16660.

[16] A. Selby, *In your original example*, post on X (@alexselby1770), March 18, 2024. Online at https://x.com/alexselby1770/status/1769795239667994765 (accessed on July 31, 2025).