%~Mouliné par MaN_auto v.0.35.0 (e18f28b9) 2025-07-30 15:44:41
\documentclass[CRMATH,Unicode,XML,biblatex]{cedram}

\TopicFR{Probabilités}
\TopicEN{Probability theory}

\addbibresource{CRMATH_Basdevant_20250272.bib}

\usepackage{mathtools}

\newcommand{\word}[2]{{\smash{#1}}^{#2}}

\newcommand{\motif}[2]{\mathbf{Patt}_{#2}(#1)}
\newcommand{\defeq}{=}

\DeclareMathOperator{\Cor}{Cor}

\renewcommand{\c}[2]{\ensuremath{[#1 \vert #2]}}

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}

\renewcommand{\P}{\mathbb{P}}

%%%---------------------------------------------------------------------------

%%% BAR & OVERLINE

%%% Better widebar macro
\makeatletter
\let\save@mathaccent\mathaccent
\newcommand*\if@single[3]{%
  \setbox0\hbox{${\mathaccent"0362{#1}}^H$}%
  \setbox2\hbox{${\mathaccent"0362{\kern0pt#1}}^H$}%
  \ifdim\ht0=\ht2 #3\else #2\fi
 }
%The bar will be moved to the right by a half of \macc@kerna, which is computed by amsmath:
\newcommand*\rel@kern[1]{\kern#1\dimexpr\macc@kerna}
%If there's a superscript following the bar, then no negative kern may follow the bar;
%an additional {} makes sure that the superscript is high enough in this case:
\newcommand*\widebar[1]{\@ifnextchar^{{\wide@bar{#1}{0}}}{\wide@bar{#1}{1}}}
%Use a separate algorithm for single symbols:
\newcommand*\wide@bar[2]{\if@single{#1}{\wide@bar@{#1}{#2}{1}}{\wide@bar@{#1}{#2}{2}}}
\newcommand*\wide@bar@[3]{%
  \begingroup
  \def\mathaccent##1##2{%
%Enable nesting of accents:
    \let\mathaccent\save@mathaccent
%If there's more than a single symbol, use the first character instead (see below):
    \if#32 \let\macc@nucleus\first@char \fi
%Determine the italic correction:
    \setbox\z@\hbox{$\macc@style{\macc@nucleus}_{}$}%
    \setbox\tw@\hbox{$\macc@style{\macc@nucleus}{}_{}$}%
    \dimen@\wd\tw@
    \advance\dimen@-\wd\z@
%Now \dimen@ is the italic correction of the symbol.
    \divide\dimen@ 3
    \@tempdima\wd\tw@
    \advance\@tempdima-\scriptspace
%Now \@tempdima is the width of the symbol.
    \divide\@tempdima 10
    \advance\dimen@-\@tempdima
%Now \dimen@ = (italic correction / 3) - (Breite / 10)
    \ifdim\dimen@>\z@ \dimen@0pt\fi
%The bar will be shortened in the case \dimen@<0 !
    \rel@kern{0.6}\kern-\dimen@
    \if#31
      \overline{\rel@kern{-0.6}\kern\dimen@\macc@nucleus\rel@kern{0.4}\kern\dimen@}%
      \advance\dimen@0.4\dimexpr\macc@kerna
%Place the combined final kern (-\dimen@) if it is >0 or if a superscript follows:
      \let\final@kern#2%
      \ifdim\dimen@<\z@ \let\final@kern1\fi
      \if\final@kern1 \kern-\dimen@\fi
    \else
      \overline{\rel@kern{-0.6}\kern\dimen@#1}%
    \fi
 }%
  \macc@depth\@ne
  \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar
  \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax}%
  \macc@set@skewchar\relax
  \let\mathaccentV\macc@nested@a
%The following initialises \macc@kerna and calls \mathaccent:
  \if#31
    \macc@nested@a\relax111{#1}%
  \else
%If the argument consists of more than one symbol, and if the first token is
%a letter, use that letter for the computations:
    \def\gobble@till@marker##1\endmarker{}%
    \futurelet\first@char\gobble@till@marker#1\endmarker
    \ifcat\noexpand\first@char A\else
      \def\first@char{}%
    \fi
    \macc@nested@a\relax111{\first@char}%
  \fi
  \endgroup
}
\makeatother

\let\oldbar\bar
\renewcommand*{\bar}[1]{{\mathchoice{\widebar{#1}}{\widebar{#1}}{\widebar{#1}}{\oldbar{#1}}}}

%%%---------------------------------------------------------------------------

%%% DELIMITERS

%\usepackage{mathtools}
\DeclarePairedDelimiter{\parens}{\lparen}{\rparen}
\DeclarePairedDelimiter{\braces}{\{}{\}}
\DeclarePairedDelimiter{\card}{\lvert}{\rvert}

%%%---------------------------------------------------------------------------

\graphicspath{{./figures/}}

\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}

\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}

\newcommand*{\relabel}{\renewcommand{\labelenumi}{(\theenumi)}}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}\relabel}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}\relabel}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}\relabel}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}\relabel}
\let\oldforall\forall
\renewcommand*{\forall}{\mathrel{\oldforall}}

%%%---------------------------------------------------------------------------

\makeatletter
\def\@setafterauthor{%
  \vglue3mm%
\begingroup\hsize=13cm\advance\hsize\abstractmarginL\raggedright
\noindent
   \leftskip\abstractmarginL
  \normalfont\Small
  \@afterauthor\par
\endgroup
\vskip2pt plus 3pt minus 1pt
}
\makeatother

%%%---------------------------------------------------------------------------

\title{On cases where Litt's game is fair}
\alttitle{Sur des cas où le jeu de Litt est \'equitable}

\author{\firstname{Anne-Laure} \lastname{Basdevant}}
\address{Sorbonne Université, CNRS, Laboratoire de Probabilités, Statistique et Modélisation, 75205 Paris, France}
\email{anne.laure.basdevant@normalesup.org}

\author{\firstname{Olivier} \lastname{Hénard}}
\address{Université Paris-Saclay, CNRS, Laboratoire de mathématiques d’Orsay, 91405 Orsay, France}
\email{olivier.henard@universite-paris-saclay.fr}

\author{\firstname{Édouard} \lastname{Maurel-Segala}}
\address[2]{Université Paris-Saclay, CNRS, Laboratoire de mathématiques d’Orsay, 91405 Orsay, France}
\email{edouard.maurel-segala@universite-paris-saclay.fr}

\author{\firstname{Arvind} \lastname{Singh}}
\address[2]{Université Paris-Saclay, CNRS, Laboratoire de mathématiques d’Orsay, 91405 Orsay, France}
\email{arvind.singh@universite-paris-saclay.fr}

\subjclass{60C05}

\keywords{\kwd{Coin flips} \kwd{pattern counts} \kwd{stochastic games}}
\altkeywords{\kwd{Pile ou face} \kwd{motifs} \kwd{jeu aléatoire}}

\begin{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~\cite{LittX}. 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$.
\end{abstract}

\begin{altabstract}
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\tralicstex{}{~}? Ce problème est une légère extension du jeu de Litt~\cite{LittX}. 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-corrélations 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.
\end{altabstract}

\begin{document}

\maketitle

\section{Introduction and main results}

In~\cite{LittX}, Litt came up with the following puzzle: a fair coin is tossed $n$ times, Alice gets a point each time the sequence $\mathrm{HH}$ appears, while Bob scores a point each time the sequence $\mathrm{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:
\begin{enumerate}
\item \label{fact_1} for any size $n\geq 3$, Bob is more likely to win than Alice;
\item \label{fact_2} for $n$ large, it holds:
\[
2 \times \parens[\big]{\P_n(\text{Bob wins})-\P_n(\text{Alice wins})} \sim \P_n(\text{Tie}) \sim \frac{1}{\sqrt{\pi n}}.
\]
\end{enumerate}
Several elements of proofs for the first fact quickly emerged on X~\cite{RameshX1, RameshX2, SelbyX}, then more formal proofs of both facts appeared on the arXiv~\cite{Zeilberger24, Segert24}. Zeilberger online journal~\cite{Zeilbergerjournal} maintains a list of contributions and questions on the problem.

Among the proofs given, we would like to advertise an early probabilistic proof: in~\cite{RameshX1}, 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~\ref{ramesh} for the full details. A rigorous proof of both facts~\eqref{fact_1} and~\eqref{fact_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~\eqref{fact_1} in a strong sense: for any size $n \geq 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~\cite{Grimmett24}, who recently rediscovered the arguments of Ramesh.

Considering a contest between $\mathrm{HT}$ and $\mathrm{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\geq 0$, a \emph{word} of length $\ell$ is a sequence $A=(a_1,\dotsc,a_\ell)$ in $\{\mathrm{H},\mathrm{T}\}^\ell$. For $X_n\coloneqq (\varepsilon_k)_{1\leq k\leq n}$ a finite sequence in $\{\mathrm{H},\mathrm{T}\}^n$, we denote by
\[
N_A(X_n)\coloneqq \card[\big]{\braces[\big]{\ell\leq k\leq n, \ (\varepsilon_{k-\ell+1},\dotsc,\varepsilon_k)=(a_1,\dotsc,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):
\[
\c{A}{B}
\defeq \sum_{k\in \Cor(A,B)} 2^k \quad \text{where} \ \Cor(A,B)
\defeq\braces[\big]{1\leq k \leq \ell-1, \ (a_{\ell-k+1},\dotsc,a_\ell)=(b_1,\dotsc,b_k)}.
\]
To be more specific, we shall call \emph{inter-correlation} the correlation of two distinct words (beware the order matters), and \emph{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$.

\begin{theorem}\label{bijection}
Let $A$, $B$ two words of length $\ell$ such that $\c{A}{A}= \c{B}{B}$.
Assume that, under\/ $\P_n$, the letters $(\varepsilon_i)_{1\leq i\leq n}$ of\/ $X_n$ form an i.i.d.\ sequence with the uniform distribution on\/ $\{\mathrm{H},\mathrm{T}\}$. Then for each $n\geq 1$, the random variables $\parens[\big]{N_A(X_n),N_B(X_n)}$ and $\parens[\big]{N_B(X_n),N_A(X_n)}$ have the same distribution. In particular, for any $n\geq 1$,
\begin{equation}\label{probwin}
\P_n(\emph{Bob wins})=\P_n(\emph{Alice wins}).
\end{equation}
\end{theorem}

For instance, the words $A = \mathrm{HHTHTH}$ and $B = \mathrm{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\footnote{In this case, we have $\c{A}{A} = \c{B}{B} = 2$, $\c{A}{B} = 2$ and $\c{B}{A} = 6$.}. We also point out that, even though $\parens[\big]{N_A(X_n),N_B(X_n)}$ is exchangeable when $\c{A}{A}= \c{B}{B}$, the law of this couple still depends on the inter-correlation $\c{A}{B}$ and $\c{B}{A}$.

It is possible to estimate the probability~\eqref{probwin} 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~\cite{J25} (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
\begin{align}
	\label{formula1}
\P_n(\text{Bob wins}) -\P_n(\text{Alice wins}) & = \frac{\c{A}{A} -\c{B}{B}}{\sqrt{2^\ell + \c{A}{A} +\c{B}{B} - \c{A}{B} -\c{B}{A}}} \cdot \frac{1}{2 \sqrt{\pi n}}+o\parens[\Bigg]{\frac{1}{\sqrt{n}}},
\\ 	\label{formula2}
\P_n(\text{Tie}) & = \frac{2^\ell}{\sqrt{2^\ell + \c{A}{A} +\c{B}{B} - \c{A}{B} - \c{B}{A}}} \cdot \frac{1}{2 \sqrt{\pi n}}+o\parens[\Bigg]{\frac{1}{\sqrt{n}}},
\end{align}
hold as soon as the denominators on both RHS are non null\footnote{The pairs of words giving a null denominator are $(\mathrm{T},\mathrm{H})$, $(\mathrm{TH}^{\ell-1},\mathrm{H}^{\ell-1}\mathrm{T})$ for $\ell \geq 2$, and those pairs obtained by interchanging H and T. They all correspond to degenerate cases.}. In the case $\c{A}{A} =\c{B}{B}$, Theorem~\ref{bijection} 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~\eqref{formula1}, Theorem~\ref{bijection} covers all cases where the game is fair.

A key feature of~\eqref{formula1} is that $\P_n(\text{Bob wins}) -\P_n(\text{Alice wins})$ has, asymptotically, the sign of $\c{A}{A} -\c{B}{B}$. In light of this observation together with some extensive numerical computations\footnote{The conjecture has been checked for all words $A$ and $B$ of size $\leq 10$ and for $n \leq 35$.}, we are lead to state the following remarkable conjecture for a \emph{fixed length} $n$ of the underlying word~$X_n$. We use $\Delta$ to denote the symmetric difference of two sets.

\begin{conjecture}\label{conj-distinct-correl}
Assume $\c{A}{A}>\c{B}{B}$. Then, for each $n \geq n_0\coloneqq 2 \ell- \max\braces[\big]{\Cor(A) \Delta \Cor(B)}$,
\[
\P_n(\emph{Alice wins}) < \P_n(\emph{Bob wins}) < \frac{1}{2} < \P_n(\emph{Alice wins}) + \P_n(\emph{Tie}).
\]
\end{conjecture}

Some comments are in order. First, the restriction to $n \geq 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 \geq 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 \emph{one additional point}\footnote{Beware this is distinct from starting the random word $X_n$ with the word $A$.}, 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~\ref{conj-distinct-correl} also suggests that the advantage of Bob versus Alice may be put in bijection with a subset of the Tie event. Conjecture~\ref{conj-distinct-correl} is valid for the original Litt's game ($\mathrm{HH}$ versus $\mathrm{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
\[
\card[\big]{\P_n(\text{Alice wins}) - \P_n(\text{Bob wins})} < \P_n(\text{Tie}),
\]
which may be checked from the conjectured asymptotics because of the inequality $\card[\big]{\c{A}{A} -\c{B}{B}} \leq 2^{\ell}-2$ that is true for every pair of words $A$, $B$.

The statement contained in Conjecture~\ref{conj-distinct-correl} 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 $\c{A}{A} > \c{B}{B}$, for each $n \geq n_0$, where $n_0$ is again defined as in Conjecture~\ref{conj-distinct-correl}, and with equality before. For $n$ large enough (larger than an indefinite constant), the statement has been stated and proved by Guibas and Odlyzko~\cite{Guibas-Odlyzko-81} and independently by Blom~\cite{Blom84}, while the result for all $n \geq n_0$ has been established by Månnson~\cite{Mansson02} after a series of works on the topic~\cite{Eriksson97,Mansson99}.

Finally, we point that the general topic of pattern matching and overlaps has been the subject of many investigations, starting with the non-transitive \emph{Penney--Ante game} named after Penney~\cite{Penney-69} (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~\cite{Guibas-Odlyzko-81, Li-80} and the references therein.

\section{Proof of Theorem~\ref{bijection}}

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.

\begin{defi}
Let $A$, $B$ be two words of length $\ell$. We define the indices of inter-correlation of $A$ and~$B$ by
\[
\Cor(A,B)=\braces[\big]{1\le k \le \ell-1, \ (a_{\ell-k+1},\dotsc,a_\ell)=(b_1,\dotsc,b_k)}.
\]
We write\/ $\Cor(A)$ to denote\/ $\Cor(A,A)$. We define the inter-correlation $\c{A}{B}$ of\/ $(A,B)$ by
\[
\c{A}{B} =\sum_{k\in \Cor(A,B)} 2^k
\]
and the auto-correlation of $A$ as $\c{A}{A}$.
\end{defi}

Let us make some remarks about this definition:
\begin{itemize}
\item the number $\c{A}{B}$ is not in general equal to $\c{B}{A}$;
\item for all $A$, $B$ of length $\ell$, $\c{A}{B} \in \llbracket 0; 2^{\ell}-2 \rrbracket$;
\item for every words $A$, $B$, $C$, $D$ of length $\ell$, $\c{A}{B}=\c{C}{D}$ if and only if $\Cor(A,B)=\Cor(C,D)$.
\end{itemize}

Fix any two words $A$ and $B$ with length $\ell$ and the same auto-correlation. To prove that $\parens[\big]{N_A(X_n),N_B(X_n)}$ has the same law as $\parens[\big]{N_B(X_n),N_A(X_n)}$, we prove the existence of a bijection $\phi$ from $\{\mathrm{H},\mathrm{T}\}^n$ to $\{\mathrm{H},\mathrm{T}\}^n$ such that, for any sequence $X_n\in\{\mathrm{H},\mathrm{T}\}^n$, $\parens[\big]{N_A(X_n),N_B(X_n)} = \parens[\big]{N_B\parens[\big]{\phi(X_n)},N_A\parens[\big]{\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 $\ell$ and $m\in \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 = \mathrm{\underline{HTTHTH}}$, $D = \mathrm{\overline{THTHHH}}$, we have $C^2D= \mathrm{\underline{HTTH} \underline{\overline{TH}} \overline{THHH}}$. We extend this notation to $k$ words $C_1,\dotsc,C_k$ of length $\ell$ and $m_1,\dotsc,m_k\geq1$ in the obvious way: if $m_i\in \Cor(C_i,C_{i+1})$ for each $i$, we define the word of length $k\ell-\sum m_i$
\begin{equation}\label{notE}
Y = \word{C_1}{m_1}\word{C_2}{m_2}\word{C_3}{m_3} \dotsm \word{C_{k-1}}{m_{k-1}}C_{k}.
\end{equation}

\begin{defi}
Let $A$, $B$ be two words of length $\ell$. A word $Y$ of the form~\eqref{notE} where $C_1,\dotsc,C_k \in \{A,B\}^k$ is called an \emph{overlap} of $A$ and $B$. We denote by $\mathcal{E}(A,B)$ the set of all \emph{overlaps} of $A$ and $B$.
\end{defi}

Note that do not accept $m_i=0$ in~\eqref{notE}. 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~\eqref{notE} may be not unique. We shall say a decomposition of $Y$ is maximal if, writing $Y=\word{C_1}{m_1}\word{C_2}{m_2}\word{C_3}{m_3} \dotsm \word{C_{k-1}}{m_{k-1}}C_{k}$, we have
\[
N_A(Y) = \card[\big]{\braces[\big]{1\le i \le k, \ C_i=A}} \qquad \text{and} \qquad N_B(Y) = \card[\big]{\braces[\big]{1\le i \le k, \ C_i=B}}.
\]
We have the following decomposition of a word.

\begin{defi}
Let $Y$ be a word. There exists a unique way to write $Y$ in the form
\begin{equation}\label{decomp}
Y = X_0 E_1 X_1 E_2 \dotsm X_{k-1} E_k X_{k}
\end{equation}
such that
\begin{itemize}
\item the words $E_1,\dotsc, E_k$ belong to $\mathcal{E}(A,B)$;
\item for all $i\in \llbracket 0,k\rrbracket$, neither $A$ nor $B$ appears in $X_i$ (which may be empty);
\item $N_A(Y)=\sum_{i=1}^k N_A(E_i)$ and $N_B(Y)=\sum_{i=1}^k N_B(E_i)$.
\end{itemize}
We say that the words $(E_1,\dotsc,E_k)$ which appear in~\eqref{decomp} form the \emph{pattern} of the word $Y$ with respect to $A$ and $B$, and we write: $\motif{Y}{A,B} = (E_1,E_2,\dotsc, E_k)$.
\end{defi}

\begin{prop}
Let $A$, $B$ be two words with the same auto-correlation, and let $\phi \colon \mathcal{E}(A,B) \to \mathcal{E}(A,B)$ be defined in the following way. If $Y\coloneqq \word{C_1}{m_1}\word{C_2}{m_2} \dotsm \word{C_{k-1}}{m_{k-1}}C_{k}$ with $C_i \in \{A,B\}$, we set
\[
\phi(Y)
\defeq\word{\bar{C}_k}{m_{k-1}}\word{\bar{C}_{k-1}}{m_{k-2}} \dotsm \word{\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 $\parens[\big]{N_A(Y),N_B(Y)} = \parens[\big]{N_B\parens[\big]{\phi(Y)},N_A\parens[\big]{\phi(Y)}}$.
\end{prop}

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

\begin{proof}
We first prove that $\phi(Y)$ is well defined i.e.\ if $m_i\in \Cor(C_i,C_{i+1})$, then $m_i\in \Cor(\bar{C}_{i+1},\bar{C}_i)$. Recall that we assume that $A$, $B$ have the same auto-correlation, i.e.\ $\Cor(A)=\Cor(B)$. We have two cases:
\begin{itemize}
\item Either $C_i=C_{i+1}$, for example~$C_i=A$. Then $\bar{C}_i=\bar{C}_{i+1}=B$. Hence, we have $\Cor(C_i,C_{i+1})=\Cor(A)=\Cor(B)=\Cor(\bar{C}_{i+1},\bar{C}_i)$.
\item 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 $\Cor(C_i,C_{i+1})=\Cor(\bar{C}_{i+1},\bar{C}_i)$.
\end{itemize}
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=\word{C_1}{m_1}\word{C_2}{m_2}C_{3}$ and $Y=\word{C_1}{m}C_{3}$. Note that $\card{Y}=2\ell-m=3\ell-m_1-m_2$. Applying $\phi$ with the first decomposition we get $\phi(Y)=\word{\bar{C}_3}{m_2}\word{\bar{C}_2}{m_1}\bar{C}_{1}$ and since $\card[\big]{\phi(Y)}=\card{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)=\word{\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\coloneqq \word{C_1}{m_1}\word{C_2}{m_2} \dotsm \word{C_{k-1}}{m_{k-1}}C_{k}$ with maximal $k$. By construction, we directly get that $N_A\parens[\big]{\phi(Y)} \geq N_B(Y)$ and $N_B\parens[\big]{\phi(Y)} \geq 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: $\word{C_1}{m}C_{2}$. Among those words $Y$, only the words where $C_1=C_2$ have to be considered. If $Y_0= \word{C_1}{m}C_1$, it holds $\phi(Y_0) = \word{\bar{C}_1}{m} \bar C_1$. Now, assume that $\phi(Y_0) = \word{\bar{C}_1}{m_1} \word{\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\parens[\big]{\phi(Y_0)} = \word{C_1}{m_1} \word{\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= \word{C_1}{m}C_1$ is the maximal decomposition in the first place.
\end{proof}

The function $\phi$ defined in the previous proposition can be extended to a function on patterns. For $(E_1,\dotsc,E_k)\in\mathcal{E}(A,B)^k$, we set
\[
\phi(E_1,\dotsc,E_k) \defeq \parens[\big]{\phi(E_k),\dotsc,\phi(E_1)}
\]
which defines an involution on $\mathcal{E}(A,B)^k$. Given a pattern $M=(E_1,\dotsc,E_k)\in \mathcal{E}(A,B)^k$ and $n\geq 1$, we define $L_M(n)$ as the number of words of length $n$ with pattern $M$:
\begin{equation*}
L_M(n) \defeq \card[\big]{\braces[\big]{\text{word} \ Y, \ \card{Y} = n \ \text{and} \ \motif{Y}{A,B} = M}}.
\end{equation*}
To prove Theorem~\ref{bijection}, it is sufficient to show that, for any pattern $M$ and any $n\geq 1$, we have
\begin{equation}\label{egalitemot}
L_M(n)=L_{\phi(M)}(n).
\end{equation}
Indeed, if $Y$ is a word such that $\motif{Y}{A,B} = M$ and $Z$ is a word such that $\motif{Z}{A,B} = \phi(M)$, we have
\[
\parens[\big]{N_A(Y),N_B(Y)} = \parens*{\sum_{i=1}^k \! N_A(E_i),\sum_{i=1}^k \!N_B(E_i)} = \parens*{\sum_{i=1}^k \! N_B\parens[\big]{\phi(E_i)},\sum_{i=1}^k \!N_A\parens[\big]{\phi(E_i)}} = \parens[\big]{N_B(Z),N_A(Z)}.
\]
In view of equality~\eqref{egalitemot}, we conclude that
\[
\begin{aligned}
P\parens[\Big]{\parens[\big]{N_A(X_n),N_B(X_n)}=(a,b)}
	& = \frac{1}{2^n} \sum_{\substack{\text{pattern $M$ s.t.} \\ \parens*{N_A(M),N_B(M)}=(a,b)}} L_M(n)
\\	& = \frac{1}{2^n} \sum_{\substack{\text{pattern $M$ s.t.} \\ \parens*{N_A(M),N_B(M)}=(a,b)}} L_{\phi(M)}(n)
\\	& = P\parens[\Big]{\parens[\big]{N_B(X_n),N_A(X_n)}=(a,b)}.
\end{aligned}
\]
In order to establish~\eqref{egalitemot}, we prove the slightly more precise result:
\begin{lemma}\label{1}
For any pattern $M=(E_1,\dotsc,E_k)$, for any $I=(i_0,\dotsc,i_k)$, set
\[
L^{M}(I) \defeq \card[\big]{\braces[\big]{Y=X_0E_1X_1 \dotsm E_kX_k : \motif{Y}{A,B} = M; \ \forall j, \ \card{X_j} = i_j}}.
\]
Then
\[
L^{M}(I)=L^{\phi(M)}(I')
\]
where $I' = (i_k,\dotsc,i_0)$.
\end{lemma}

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.

\begin{proof}
Let us remark that we have
\[
L^M(I)=L^{E_1}(i_0,0)\parens*{\prod_{j=1}^{k-1} L^{(E_j,E_{j+1})}(0,i_j,0)}L^{E_k}(0,i_k)
\]
and
\[
L^{\phi(M)}(I')=L^{\phi(E_k)}(i_k,0)\parens*{\prod_{j=1}^{k-1} L^{\parens*{\phi(E_{j+1}),\phi(E_{j})}}(0,i_j,0)}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^{\parens*{\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^{\parens*{\phi(E_{j+1}),\phi(E_{j})}}(0,i_j,0)=L^{(B,B)}(0,i_j,0) \qquad \text{while} \qquad 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) \qquad \text{while} \qquad 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~\ref{1} will be proved as soon as we establish the following equality: for each $i \geq 0$,
\begin{equation}\label{e:recurrence}
L^{(A,A)}(0,i,0)=L^{(B,B)}(0,i,0) \qquad \text{and} \qquad L^{(B)}(0,i)=L^{(A)}(i,0).
\end{equation}
We prove~\eqref{e:recurrence} 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,\dotsc,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 $\card{I}= \sum_{j=0}^k i_j$ if $I=(i_0,\dotsc,i_k)$ and $\card{M}= \sum_{i=1}^k \card{E_i}$ for the length of the pattern $M=(E_1,\dotsc, E_k)$, we find that
\begin{align*}
L^{(A)}(i,0)
	& = \card[\big]{\braces[\big]{\text{words} \ XA : \card{X} = i \ \text{and} \ \motif{X A}{A,B} = A}}
\\	& = 2^i-\sum_{k\geqslant 1} \ \sum_{\substack{M=(E_1,\dotsc,E_k)\neq (A) \\ \text{$E_k$ ends with $A$}}} \ \sum_{\substack{I=(i_0,\dotsc,i_{k-1},0) \\ \card{I}+\card{M}=i+\card{A}}}L^M(I)
\\	& = 2^i-\sum_{k\geqslant 1} \ \sum_{\substack{M=(E_1,\dotsc,E_k)\neq (A) \\ \text{$E_k$ ends with $A$}}} \ \sum_{\substack{I=(i_0,\dotsc,i_{k-1},0) \\ \card{I}+\card{M}=i+\card{A}}}L^{\phi(M)}(I').
\end{align*}
At this point, we use the recurrence assumption noticing that $\card{I}<i$ since $\card{M}>\card{A}$. Recalling that if $M$ ends with $A$, then $\phi(M)$ starts with $B$, we see that the last line is also equal to
\[
2^i-\sum_{k\geqslant 1} \ \sum_{\substack{M=(E_1,\dotsc,E_k)\neq (B) \\ \text{$E_1$ starts with $B$}}} \ \sum_{\substack{I=(0,i_1,\dotsc,i_{k}) \\ \card{I}+\card{M}=i+\card{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.
\end{proof}

\section{Ramesh original argument}\label{ramesh}

For the ease of reference, we reproduce here verbatim the original tweets~\cite{RameshX1} of Sridhar Ramesh on the original $\mathrm{HH}$ versus $\mathrm{HT}$ game with the permission of their author:
\begin{quote}
``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 $\mathrm{HH}$ as a step up in one unit of time and $\mathrm{HT}^n\mathrm{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 $\mathrm{HT}^n\mathrm{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 $\mathrm{HT}^n\mathrm{H}$ step (e.g., if the game consists of $\mathrm{HHT}$ followed by all $\mathrm{T}$'s), Alice is less likely to win than Bob. QED. The salient difference is that the ``buzzer'' can cut off $\mathrm{HT}^n\mathrm{H}$ in the middle (after awarding Bob a game-tying point but before returning to $\mathrm{H}$), which it cannot do for $\mathrm{HH}$. The random walk framing perhaps allows some ready generalization to other interesting problems.''
\end{quote}

\section*{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.

\printbibliography

\end{document}