\documentclass[12pt]{amsart} 
%\usepackage{mathrsfs} 
\usepackage{geometry}
\usepackage{graphicx} 
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{amsmath,amscd}
\usepackage{amsthm} 
\usepackage{url,verbatim}
\usepackage{mathtools}

\RequirePackage[colorlinks,citecolor=blue,urlcolor=blue]{hyperref}
%\usepackage[notcite,notref]{showkeys} 
\usepackage{breakurl} 
\theoremstyle{plain}
\textwidth=460pt 
\textheight=23truecm
\voffset=-0.5truecm
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1 `/`basename #1
.tif`.png} 
\setlength{\parskip}{5pt}


\newcommand{\grg}[1]{{\textcolor{red} {[GRG: #1\marginpar{\textcolor{red}{\bf
$\bigstar$}}]}}} 

\newcommand{\zl}[1]{{\textcolor{blue} {[ZL: #1\marginpar{\textcolor{red}{\bf $\bigstar$}}]}}}

\renewcommand{\thefootnote}{\fnsymbol{footnote}} 
\newtheorem{theorem}{Theorem}
\newtheorem{definition}[theorem]{Definition} 
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example} 
\newtheorem{remark}[theorem]{Remark}

\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{question}[theorem]{Question}

\newcounter{mycount}

\newenvironment{romlist}{\begin{list}{\rm(\roman{mycount})}%
{\usecounter{mycount}\labelwidth=1cm\itemsep 0pt}}{\end{list}}

\newenvironment{numlist}{\begin{list}{\arabic{mycount}.}%
{\usecounter{mycount}\labelwidth=1cm\itemsep 0pt}}{\end{list}}

\newenvironment{numplist}{\begin{list}{(\arabic{mycount})}%
{\usecounter{mycount}\labelwidth=1cm\itemsep 0pt}}{\end{list}}

\newenvironment{letlist}{\begin{list}{\rm(\alph{mycount})}%
{\usecounter{mycount}\labelwidth=1cm\itemsep 0pt}}{\end{list}}

\newenvironment{Alist}{\begin{list}{\MakeUppercase{\alph{mycount}}.}%
{\usecounter{mycount}\labelwidth=1cm\itemsep 0pt}}{\end{list}}

\newenvironment{problist}{\begin{list}{{\alph{mycount}}}%
{\usecounter{mycount}\leftmargin=0pt\itemindent=1cm\labelwidth=1cm\itemsep 0pt}}{\end{list}}
   
\numberwithin{equation}{section} 
\numberwithin{theorem}{section}
\numberwithin{figure}{section}

\newcommand\XX{{\mathbb X}}
\newcommand\sK{{\mathcal K}}
\renewcommand\O{\text{\rm O}}


\newcommand\RR{{\mathbb R}} 
\newcommand\PP{{\mathbb P}} 
\newcommand\qq{\qquad} 
\newcommand\q{\quad} 
\newcommand\si{\sigma}
\newcommand\be{\beta} 
\newcommand\al{\alpha} 
\newcommand\Si{\Sigma}
\newcommand\g{\gamma} 
\newcommand\om{\omega} 
\newcommand\Om{\Omega}
\newcommand\De{\Delta} 
\newcommand\ol{\overline} 
\newcommand\FF{{\mathbb F}}
\renewcommand\AA{{\mathbb A}} 
\newcommand\sG{{\mathcal G}}

\newcommand\CC{{\mathbb C}} 
\newcommand\sB{{\mathcal B}} 
\newcommand\sL{{\mathcal L}}
\newcommand\NN{{\mathbb N}} 
\newcommand\ZZ{{\mathbb Z}} 
\newcommand\VV{{\mathbb V}}
\newcommand\EE{{\mathbb E}} 
\newcommand\sT{{\mathcal T}}
\newcommand\sD{{\mathcal D}} 
\newcommand\sF{{\mathcal F}}
\newcommand\sC{{\mathcal C}} 
\newcommand\La{\Lambda} 
\newcommand\la{\lambda}
\newcommand\eps{\epsilon} 
\newcommand\ot{1-2\ } 
\newcommand\resp{respectively}
\newcommand\deqd{\doteqdot} 
\newcommand\lra{\leftrightarrow}
\newcommand\oo{\infty} 
\newcommand\wt{\widetilde} 
\newcommand\TT{{\mathbb T}}
\renewcommand\th{\theta} 
\newcommand\de{\delta} 
\newcommand\sU{{\mathcal U}}
\newcommand\Pf{\mathrm{Pf}\, } 
\newcommand\Proj{{\mathrm{Proj}\,}}
\newcommand\rv{\mathrm{v}} 
\newcommand\re{\mathrm{e}}
\newcommand\bec{\be_{\mathrm{c}}} 
\renewcommand\v{{\mathrm{v}}}
\newcommand\nw{{\mathrm{nw}}} 
\newcommand\nea{{\mathrm{ne}}}
\newcommand\es{\varnothing} 
\renewcommand\ss{\mathrm{ss}}
\newcommand\dd{\mathrm{oo}} 
\newcommand\os{\mathrm{os}}
\newcommand\so{\mathrm{so}} 
\newcommand\symdif{\,\bigtriangleup\,}
\newcommand\m{\mathrm{mix}} 
\newcommand\e{\mathrm{ev}} 
\newcommand\I{\mathrm{I}}
\newcommand\HnD{\HH_{n,\De}}
\newcommand\wh{\widehat}
\newcommand\sgn{\mathrm{sgn}}
\newcommand\mo{\mu_\oo} 
\newcommand\Pip{\Pi^{\text{\rm poly}}}
\newcommand\Znp{Z_n^{\text{\rm poly}}}
\newcommand\Pipi{\Pi_{e,f}}
\newcommand\ac{a_{\mathrm{c}}}
\hyphenation{Simons}
\newcommand\pc{p_{\mathrm{c}}}
\newcommand\wpc{\widehat p_{\mathrm{c}}}
\newcommand\pic{\pi_{\mathrm{c}}}
\newcommand\rhoc{\rho_{\mathrm{c}}}
\newcommand\sA{{\mathcal A}} 
\newcommand\vG{\vec G}
\newcommand\LL{{\mathbb L}} 
\newcommand\sE{{\mathcal E}}
\newcommand\sR{{\mathcal R}}
\newcommand\pa{\ell}
\newcommand\LR{\mathrm{LR}}
\newcommand\pd{\partial}
\renewcommand\o{\text{{\rm o}}}
\renewcommand\H{\text{\rm H}}
\newcommand\T{\text{\rm T}}
\newcommand\A{\text{\rm A}}
\newcommand\B{\text{\rm B}}
\newcommand\Aa{\^ A}
\newcommand{\red}[1]{{\textcolor{red}{#1}}}
\newcommand{\blue}[1]{{\textcolor{blue}{#1}}}
\newcommand{\green}[1]{{\textcolor{green}{#1}}}

\title[Alice and Bob on $\XX$: reversal, coupling, renewal]{Alice and Bob on $\XX$:\\ reversal, coupling, renewal}
\author{Geoffrey R.\ Grimmett}
\address{Centre for
Mathematical Sciences, Cambridge University, Wilberforce Road,
Cambridge CB3 0WB, UK} 
\email{grg@statslab.cam.ac.uk}


\date{August 30, 2024} %\today}
\keywords{Coin tosses, random game, local central limit theorem}
\subjclass[2010]{60C05}

\begin{document}
\begin{abstract}
A neat question involving coin flips surfaced on $\XX$, and generated an intensive
outbreak of `social mathematics'. In a sequence of flips of a fair coin,
Alice wins a point at each appearance of two consecutive heads, and Bob wins a point whenever a 
head is followed immediately by a tail. Who is more likely to win the game? 
The subsequent discussion illustrated conflicting intuitions, and concluded with the correct answer
(it is a close thing).
It is explained here why the context of the question is interesting and how it may be answered in a quantitative
manner using the probabilistic techniques of reversal, coupling, and renewal.
\end{abstract}

\maketitle

\section{The problem}

\begin{question}\label{qn:1}
A fair coin is tossed $n$ times. Alice scores one point  at each appearance of two
consecutive heads, and Bob scores one point each time a head is followed immediately by a tail. 
The winner is the player who accumulates more points.
Who is the more likely to win?
\end{question}

Here are some intuitive arguments in order of decreasing naivet\'e.
\begin{letlist}
\item In any pair of consecutive coin tosses, Alice wins a point with probability $\frac14$,
and Bob wins a point with the same probability. Therefore, each has a mean total
score of $\frac14(n-1)$. Since these means are equal, each player has the same probability of winning.
\item Alice's points tend to arrive in clusters, whereas Bob's are isolated. 
That favours Alice, so she is more likely to win.
\item When Alice wins a point, she has an increased chance of winning again. 
Therefore, she tends to win the game by a wider margin than Bob.
However, her mean total
is the same as Bob's. It follows that Bob has a greater chance of winning.
\end{letlist}

This question (with $n=100$) was posed by Daniel Litt on his $\XX$ feed \cite{Litt}
on 16 March 2024. 
At the current time of writing, his post has attracted 1.2M views. 
First responders tended to favour Alice above Bob on the grounds of
argument (b), and a vote was reported as placing
Alice (26.3\%) over Bob (10.2\%), with 42.8\%\ of the 51,588 voters supporting equality. 
Later simulations appeared to show that Bob has a slight advantage.

ChatGPT has changed its position on the question over the intervening months. Initially it favoured 
Alice on the grounds given in (b) above. At the time of writing it has veered towards (a),
with the conclusion that
``The game is fair to both players in terms of expected outcomes.''
Fair enough, but not very helpful. There remains hope for mathematicians. 

More complete answers began to surface on Litt's $\XX$ feed fairly soon after the original post,
and
suggestions  were made for rigorous proof (see Remark \ref{rem:5} below). It is not easy to convey the details 
and to check the correctness of a mathematical
argument within the
format confines of  $\XX$, and  hence this note. We present three conclusions.

\begin{theorem}\label{thm:0}
Consider $n$ flips of a fair coin.
\begin{letlist}
\item Bob is (strictly) more likely than Alice  to win when $n \ge 3$.
\item $\PP(\text{\rm Bob wins}) - \PP(\text{\rm Alice wins}) \sim c/\sqrt n$ as $n\to\oo$, where 
$$
c= \frac1{2\sqrt \pi}\approx 0.282.
$$
\item
The probability of a tie is asymptotically $2c/\sqrt n$, with $c$ as in part (b).
\end{letlist}
\end{theorem}

Explicit representations
for the probabilities in (b) and (c) are given in
equations \eqref{eq:3n}--\eqref{eq:13n}. 
Parts (b) and (c) imply that
\begin{equation}\label{eq:51}
\frac12 - \PP(\text{B wins}) \sim \frac{c}{2\sqrt{n}}, \qq
\frac12 - \PP(\text{A wins}) \sim \frac{3c}{2\sqrt{n}}.
\end{equation}

It is immediate that Alice and Bob are equally likely to win when $n=1,2$; by  considering
the eight possible outcomes when $n=3$, we have
$\PP(\text{Bob wins}) - \PP(\text{Alice wins}) = \frac18$. 

The methods of proof may be summarised as reversal, coupling, and renewal,
and the proof of Theorem \ref{thm:0} illustrates these standard techniques. Reversing 
a random sequence is a long-established activity which has contributed
enormously to probability  and especially to the theory of random walks
(see, for example, \cite[Sect.\ 3.10]{PRP}). The coupling  approach enables
us to study the \lq pathwise\rq\ relationship between winning sequences for Alice and 
for Bob, rather
than by simply calculating probabilities (see, for example, \cite[Sect.\ 4.12]{PRP}). 
Renewal theory is the study of random processes 
that renew themselves at random times (see for example, \cite[Chap.\ 10]{PRP}).

\begin{remark}
The above problem may be phrased as  \lq$\H\T$ vs $\H\H$\rq. 
The methods described here yield
the same conclusions for $\T\H$ vs $\H\H$, for the following reason. 
Take a sequence $\om$ of heads/tails and reverse it in time to obtain $\rho(\om)$.
Then $\om$ and $\rho(\om)$ have the same probability distribution, and the same count of consecutive 
head pairs $\H\H$. However, every $\H\T$ in $\om$ becomes $\T\H$ in $\rho(\om)$.
\end{remark}

As mathematicians we insist on unambiguous definitions of the objects of our study. 
One may capture pretty well
all of probability theory by defining it
as the theory of a countably infinite sequence of tosses of a fair coin.  Perhaps not 
everything worth knowing is yet known about
this primeval experiment.

\begin{remark}\label{rem:5}
The target of this note is to obtain Theorem \ref{thm:0} using probabilistic methods.
Since writing it, we have learned of related contributions available online. 
The idea of reversal has arisen in certain contributions on $\XX$ to Litt's post. 
Mention is made also of \cite{EZ} (using symbolic computation) and \cite{Seg} (using analysis);
each of these works includes a version of Theorem \ref{thm:0}.
\end{remark}

\section{Notation and basic observations}\label{sec:not}

Here is some notation. Abbreviate Alice to A, and Bob to B; write $\H$ for a head and $\T$ for a tail.
Let 
$\NN$ denote the natural numbers, and let $\Om_\oo=\{\H,\T\}^\NN$ 
be the
set of all sequences $\om=(\om_1,\om_2,\dots)$
each element of which is either $\H$ or $\T$.  
We shall normally express such sequences as $\om=\om_1\om_2\cdots$.
Similarly, $\Om_n:= \{\H,\T\}^n$,
the set of all sequences of $n$ coin tosses. 

Let $\om\in\Om_\oo$.
Player A scores $-1$ at each appearance of 
$\H\H$; player B scores $1$ at each appearance of $\H\T$.
The score $S_k(\om)$ is the aggregate score after 
$k$ steps of $\om$, that is, $S_k(\om)$ is the number
of appearances of $\H\T$ minus the number of appearances of $\H\H$ in 
the subsequence $\om_1\om_2\cdots\om_k$.

Here is an outline of the method to be followed here. First, one defines epochs of renewal, 
at which the scoring process restarts. Neither player scores until the first appearance of $\H$. 
\begin{romlist}
\item If the following flip is $\T$ then Bob enters a winning period (of some length $l_\B$), 
which lasts until the next time that the aggregate score is $0$;
this must happen at an appearance of $\H\H$.  

\item If the following flip is $\H$ then Alice enters a winning period (of some length $l_\A$),
which lasts until the next time that the aggregate score is $0$;
this must happen at an appearance of $\H\T$. 
\end{romlist}
The process then restarts (subject to 
certain details to be made specific). After $n$ coin flips, Alice is winning if she is then in a winning period, 
and similarly for Bob.  Ties occur between winning periods.
We will see that the representative periods $l_\A$, $l_\B$ are such that
$l_\A$ is (stochastically) smaller than $l_\B$, and Theorem \ref{thm:0}(a) will follow.

The stochastic domination is proved by
displaying a concrete coupling of $l_\A$ and $l_\B$. 
The above explanation is given in more detail in Section \ref{sec:3}.

The asymptotic part (b) of Theorem \ref{thm:0} is of course connected to the local
central limit theorem (see, for example, \cite[p.\ 219]{PRP}). It suffices to use the earliest such theorem ever proved, namely the 1733 theorem of de Moivre
\cite{deM1,PdMA} (see also \cite[p.\ 243--254]{deM} and \cite[Thm 1.1]{SW}), 
although one may equally use the (de Moivre--)Stirling formula alone 
(see the historical note \cite{KP}).

We have assumed implicitly in the above that the lengths $l_\A$, $l_\B$ 
are finite (almost surely), and this
requires proof. It follows from the next lemma.

Let $\PP$ be the probability measure on $\Om_\oo$ under which the coin tosses 
are independent random variables,
each being $\H$ (\resp, $\T$) with probability $\frac12$. 
An event $E$ is said to occur \emph{almost surely} if
$\PP(E)=1$.

\begin{lemma}\label{lem:2}
The number of times $r$ at which the aggregate score satisfies
$S_r(\om)=0$ is infinite almost surely.
\end{lemma}

\begin{remark}
Many of the arguments of this note are valid in the more general setting where heads occurs with some probability $p\in(0,1)$. However, the conclusion of Lemma \ref{lem:2} is 
false when $p\ne \frac12$, and indeed
$\PP(\text{\rm A wins})$ approaches $1$ if $p>\frac12$, and approaches $0$ if $p<\frac12$,
in the limit as the number of coin flips grows to $\oo$.
\end{remark}

\begin{proof}[Proof of Lemma \ref{lem:2}]
 Write $1[A]$
for the indicator function of an event $A$. 
The score $S(r)$ after
$r$ appearances of $\T$ forms a random walk with typical jump-size $\De=(2-R)1[R\ge 1]$
where
$R$ is the length of a typical run of heads; we allow $R=0$, so that
$\PP(R=r)=(\frac12)^{r+1}$ for $r \ge 0$. 
Now,
$$
\EE(\De) = \sum_{r=1}^\oo (2-r)\left(\tfrac12\right)^{r+1} = 0.
$$
By a classical theorem of Chung and Fuchs \cite{CF}
(see, for example, \cite[Thm 5.10.16]{PRP})
this random walk is recurrent, and therefore the set $\{r: S(r)=0\}$ is
almost surely infinite.
\end{proof}

\section{Proof of Theorem \ref{thm:0}($\mathrm{a}$)}\label{sec:3}

A finite sequence $\om=\om_1\cdots\om_k$ is called 
\begin{align*}
&\text{a B-\emph{excursion} if it starts 
$\H\T$ and ends $\H\H$, and satisfies:}\\
&\hskip3cm \text{$S_l(\om)>0$ for $1<l<k$, and $S_k(\om)=0$,}\\
&\text{an A-\emph{excursion} if it starts 
$\H\H$ and ends $\H\T$, and satisfies:}\\
&\hskip3cm \text{$S_l(\om)<0$ for $1<l<k$, and $S_k(\om)=0$,}\\
&\text{an \Aa-\emph{excursion} it comprises an A-excursion followed by a (possibly empty) }\\
&\hskip3cm\text{run of tails and then a single head. }
\end{align*}
We write $\sB$ for the set of B-excursions, and $\sB_k$ for those of length $k$,
with similar notation for A-excursions and \Aa-excursions (using
the notation $\sA$ and $\hat \sA$, \resp).

\Aa-excursions are introduced for the following reason. 
Players A and B can score only following an appearance of $\H$. 
We shall use an embedded renewal
argument, and to that end it is convenient that excursions finish with a head.
Since an A-excursion ends with a tail, we simply extend it
to include any following run of tails, followed by the subsequent head; this extension contains neither $\H\H$ nor $\H\T$ and hence the score of the excursion is unchanged.

\begin{remark}\label{rem:2}
A \emph{headrun} (\resp, \emph{tailrun}) is a maximal consecutive sequence of heads
(\resp, tails). Any finite sequence $\om$ comprises alternating headruns and tailruns.
Alice's score equals the number of heads minus the number of headruns. Bob's score
equals the number of tailruns having a preceding head. Let $h$ be the total number
of heads, and $r$ the total number of runs (each comprising either heads or tails).
The aggregate score $S(\om)$
equals $r-h$ if $\om_1=\H$ (\resp, $r-1-h$ if $\om_1=\T$). 
\end{remark}

\begin{comment}
\begin{figure}
\begin{alignat*}{2}
\text{Case (b): } &\T^{M-1}\red{\H}\, \vert\, \red{\T\cdots\cdots} \hfill &&\red{\llap{\H}\H}\,\vert\\
\text{Case (c): } &\T^{M-1}\red{\H}\, \vert\, \red{\H\cdots\cdots \H\T}\,\vert\,
\red{\T^{M'-1}}&&\red{\H}\,\vert.\\
\phantom{\text{Case (c): }}&\phantom{\T^{M-1}}M\phantom{\,\vert\, \H\cdots\H}{M+Q}
\hskip6pt M+Q+M'.
\end{alignat*}
\caption{}\label{fig:1}
\end{figure}
\end{comment}


We define sequence-reversal next. 
Let $\Phi=\bigcup_{k=1}^\oo \Om_k$ be the set of all non-empty finite sequences,
and let $\Phi^{\H}$ be the subset of $\Phi$ containing
all finite sequences that begin $\H$.
For $\om\in\Phi$, we write $S(\om)$ for 
the aggregate score of $\om$. The score function is additive in the sense that
\begin{equation}\label{eq:2n}
S(\om_1\cdots\om_{m+n}) = S(\om_1\cdots\om_{m})+S(\om_m\cdots\om_{m+n}),
\qq m,n \ge 1.
\end{equation}
For a finite sequence
$\om= \om_1\om_2\dots \om_k\in\Phi$,
define its \emph{reversal} $\rho(\om)$ by $\rho(\om)= \om_k\om_{k-1}\dots \om_1$.

 
 \begin{lemma}\label{lem:1}
 \mbox{\hfil}
 \begin{letlist}
 \item If $\om=\om_1\cdots\om_k\in\Phi^\H$ ends in $\H$ (so that $\om_1=\om_k=\H$), 
 then $S(\om)=S(\rho(\om))$.
 \item Let $k\ge 2$.  The mapping $\rho$ is a measure-preserving bijection between the sets $\sB_k$ and
 $\hat \sA_k$.
 \end{letlist}
 \end{lemma}
 
\begin{proof}
(a) Let $\om\in\Phi^\H$ end in $\H$, so that $\rho(\om)\in \Phi^\H$.
By Remark \ref{rem:2}, $S(\om)$ equals the number of runs minus the number of heads. These counts are invariant under $\rho$.
 
 (b) A B-excursion $b=b_1b_2\cdots b_k\in \sB_k$ has the form $b=\H\T^r\H\cdots \H\H$ for some $r\ge 1$, 
 whence $\rho(b)=b_kb_{k-1}\cdots b_1$
 has the form $\H\H\cdots\H\T^r\H$. 
By part (a), $S(\rho(b))=S(b)=0$, which implies 
\begin{equation}\label{eq:21n}
S(b_kb_{k-1}\cdots b_{r+2})=0. 
\end{equation}

 We claim that 
 \begin{equation}\label{eq:20n}
 S(b_kb_{k-1}\cdots b_j) <0 \qq\text{for  } j \in [r+3,k-1].
 \end{equation}
Suppose, on the contrary, that $j\in[r+3,k-1]$ is such that $S(b_kb_{k-1}\cdots b_j) =0$.
 Then $s=\max\{t\le j : \om_t=\H\}$ is such that $s\ge r+2$ and $S(b_kb_{k-1}\cdots b_s)=0$.
 By part (a) and the fact that $b\in\sB_k$, we have 
 $S(b_sb_{s+1}\cdots b_k) = S(b_kb_{k-1}\cdots b_s)=0$. 
 By the additivity of $S$, \eqref{eq:2n}, 
 $$
 S(b_1b_2\cdots b_s) = S(b_1b_2\cdots b_k) - S(b_sb_{s+1}\cdots b_k) = 0,
 $$
 in contradiction of the assumption that $b$ is a B-excursion, and \eqref{eq:20n} follows.  

By \eqref{eq:21n}--\eqref{eq:20n}, $b_kb_{k-1}\cdots b_{r+2}$ is an A-excursion, and hence
$\rho(b)$ is an \Aa-excursion.
Therefore, $\rho$ is  an injection.
 By the same argument applied to $\rho^{-1}$, we have that $\rho$ is a surjection.
 The measure-preserving property follows from the fact that $\om$ and $\rho(\om)$
 have the same numbers of heads and tails.
 \end{proof}
 
 We make three observations, in amplification of the remarks of the last section.
Let $\om\in\Om_\oo$, and observe the initial evolution of scores. 

\begin{letlist}
\item There is no score until the first $\H$ appears. Let $M$ be the position of the first
$\H$, and note that $\PP(M=m) = (\frac12)^m$ for $m\ge 1$. That is, there is an initial 
sequence of tails of some random length $M-1$ ($\ge 0$), followed by a head 
(so that $\om=\T^{M-1}\H\cdots$). 
Following this head, there is equal probability of $\H$ or $\T$.
\item If the next toss is $\T$ (which is to say that $\om_{M+1}=\T$), then Bob scores one point.
He remains in the lead until the next epoch, $M+N$ say, at which the aggregate score equals $0$.
It must be the case that $\om_{M+N-1}\om_{M+N} = \H\H$,
and thus the sequence $\om_M\cdots\om_{M+N}$ is a B-excursion. 
The process restarts from $\H$ at time $M+N$.

\item  Suppose the next toss is $\H$
(i.e., $\om_{M+1}=\H$). The situation is slightly more complicated in this case.
At time $M+1$, Alice leads by $1$, and she continues in the lead until
the next epoch, $M+Q$ say, when the aggregate score equals $0$, and moreover 
$\om_{M+Q-1}\om_{M+Q} = \H\T$. Thus the sequence $\om_1\cdots\om_{M+Q}$ is an 
A-excursion.
Whereas in (b) the process restarts from the state 
$\om_{M+N}=\H$,
this time we have $\om_{M+Q}=\T$, and we wait a random period of time for the next $\H$. 
As in (a), there is a run of tails before
the next head, which is to say that the process restarts from the head at epoch $M+Q+M'$ where
$M'$ is an independent copy of $M$. The sequence $\om_M\cdots\om_{M+N+M'}$ is an
\Aa-excursion. 
\end{letlist}

We shall adjoin certain sequences by placing them in tandem, and we write either $\psi_1\psi_2$
or $\psi_1\cdot\psi_2$
for $\psi_1$ followed by $\psi_2$. When scoring $\psi_2$, viewed
as a subsequence of $\psi_1\psi_2$, one  
takes account of the final character of $\psi_1$, which will typically be $\H$ in the cases studied here. 
In order to do the necessary book-keeping we introduce the following notation: 
if $\psi$ is a sequence beginning $\H$,
we write $\H^{-1}\psi$ for the sequence obtained from $\psi$
by removing its initial $\H$.

Let $(\tau_i: i\ge 1)$ be a 
sequence of independent random elements 
of $\sA$, and let  $Q_i+1$ be the length of $\tau_i$ (so that $\H^{-1}\tau_i$
has length $Q_i$).
The $\tau_i$ are almost surely finite, by Lemma \ref{lem:2}.
Let $(M_i:i\ge 0)$ be independent  copies of $M$, also independent of the $Q_i$.
Let $N_i=Q_i+M_i$, and let $L_i=\T^{M_i-1}\H$.

We have that $\tau_i L_i$ is a random element of $\hat\sA$ of length $Q_i+M_i+1$.
By Lemma \ref{lem:1}, $\rho(\tau_i L_i)$ is a random element of $\sB$ of length $Q_i+M_i+1$.
We define
\begin{align*}
&\text{the \Aa-excursion $\alpha_i:=\tau_i L_i$},\\
&\text{the B-excursion $\beta_i:=\rho(\tau_i L_i)$}.
\end{align*}
Thus $\beta_i$ is a simple reversal of $\alpha_i$, and this fact will provide a coupling of 
\Aa-excursions and B-excursions which is length-conserving in that $\alpha_i$ and
$\beta_i$ have the same length.

Both $\alpha_i$ and $\beta_i$ start and end with $\H$; when placing them in tandem
we shall strip the initial $\H$.
Another way of expressing (a)--(c) is as follows. 
\begin{romlist}
\item  A random sequence of coin tosses begins $L_0$.

\item This is followed by 
\begin{equation*}
\gamma_1 := \begin{cases}
\H^{-1}\alpha_1 &\text{with probability $\frac12$},\\
\H^{-1}\beta_1 &\text{with probability $\frac12$}.
\end{cases}
\end{equation*}

\item Let $k\ge 2$, and suppose $\alpha_i$, $\beta_i$ have been constructed for
$i=1,2,\dots,k$. We then let
  \begin{equation}
\gamma_{k+1} := \begin{cases}
\H^{-1}\alpha_{k+1} &\text{with probability $\frac12$},\\
\H^{-1}\beta_{k+1} &\text{with probability $\frac12$}.
\end{cases}
\label{eq:8n}
\end{equation}
\end{romlist}
Note that the length of $\gamma_i$ is $Q_i+M_i$.

\begin{lemma}\label{lem:3}
The sequence $X=L_0\gamma_1\gamma_2\cdots$ is an independent 
sequence of fair coin tosses.
\end{lemma}

This does not require proof beyond the above remarks.  
The lemma provides a representation of a random sequence in terms of an initial tailrun, followed by
independent copies of $\gamma_1$ in tandem. Each $\gamma_i$ occupies a time-slot, and within this
slot there appears a sequence of coin-tosses; according to the flip of another fair coin, we either retain this
sequence or we reverse it (see \eqref{eq:8n}).   
(Some minor details concerning initial and final heads are omitted from this overview).
Lemma \ref{lem:3} provides the setting for a coupling of \Aa-excursions and B-excursions.

\begin{proof}[Proof of Theorem \ref{thm:0}(a)]
Let $X$ be as in Lemma \ref{lem:3}.
For a finite subsequence $\de=X_r X_{r}\cdots X_s$, write $\ol\de=\{r,r+1,\dots,s\}$
for the set of times spanned by $\de$, and  $\de^\circ=\ol\de\setminus\{s\}$. 
Let $n\ge 3$, and find the unique $I$ such that $n\in \gamma_I$ (write $I=0$ if
$n\in L_0$). At epoch $n$,
\begin{equation}
\label{eq:40}
\begin{aligned}
\text{$S_n=0$}&\text{\q if\q}&&I=0,\\
\text{$S_n>0$}&\text{\q if\q}&&I\ge 1,\, \H\gamma_I =\beta_I \in \sB \text{ and } n\in\beta_I^\circ,\\
\text{$S_n<0$}&\text{\q if\q}&&I\ge 1,\,\H\gamma_I =\tau_I L_I\in \hat\sA \text{ and } n\in\tau_I^\circ,\\
\text{$S_n=0$}&\text{\q if\q}&&\text{none of the above conditions hold}.
\end{aligned}
\end{equation}
Recalling \eqref{eq:8n}, it follows that
\begin{align}\label{eq:3n}
\PP(S_n>0)- \PP(S_n<0) &= \tfrac12\bigl[\PP(I\ge 1,\,n\in \beta_I^\circ)-\PP(I\ge 1,\,n\in\tau_I^\circ)\bigr]\\
&=\tfrac12\PP(I\ge 1,\,n\in\beta_I^\circ\setminus\tau_I^\circ)\ge 0.
\nonumber
\end{align}
The strict positivity of the last probability (with $n\ge 3$)
follows by consideration of sequences beginning $\H^2\T^{m}\H\cdots$
with $m\ge n$,
for which $M_0=1$, $M_1=m$, and $\gamma_1=\H\T^m\H$. Thus, $\tau_1=\H\H\T$,
and the interval $\beta_1^\circ \setminus \tau_1^\circ = \{3 ,m+2\}$ contains
the value $n$.
\end{proof}

The probability of a tie is derived similarly to \eqref{eq:3n} as
\begin{equation}\label{eq:13n}
\PP(S_n=0) =\PP(I=0) + \PP(I\ge 1,\, n\in\be_I\setminus\beta_I^\circ)
+ \tfrac12\PP(I\ge 1,\, n\in \beta_I^\circ\setminus \tau_I^\circ).
\end{equation}
From \eqref{eq:3n}--\eqref{eq:13n} (as in \eqref{eq:51})
one obtains representations for $\PP(S_n>0)$ and $\PP(S_n<0)$.


\section{Proof of Theorem \ref{thm:0}($\mathrm{b,\,c}$)}\label{sec:3}

Let $R$ be a renewal process with inter-renewal times distributed as $L_0\cdot \H^{-1}\tau_1$,
and let $\pi_m:=\PP(m \in R)$.  
By the renewal property, conditional on the event $\{m\in R\}$,
the sequence $\psi_{m,n}:=X_{m+1}X_{m+2}\cdots X_n$
is a sequence of independent coin flips. Since the events $\{m\in R,\, \psi_{m,n}=\T^{n-m}\}$,
$m=1,2,\dots,n$, are disjoint, we have by \eqref{eq:3n} that
\begin{align}\label{eq:4n}
\PP(S_n>0)- \PP(S_n<0) &= \frac12\sum_{m=3}^n \PP(m\in R,\,\psi_{m,n}=\T^{n-m})\\
&=\sum_{k=0}^{n-3} (\tfrac12)^{k+1}\pi_{n-k}.\nonumber
\end{align}
Theorem \ref{thm:0}(b) follows once the following has been proved.

\begin{proposition}\label{prop:1}
We have that $\pi_m \sim c/\sqrt m$ as $m\to\oo$, where $c=1/(2\sqrt \pi)\approx 0.282$.
\end{proposition}

The proof uses the de Moivre local central limit theorem (as in \cite{SW}),
though this amounts only to sustained use of the (de Moivre--)Stirling formula, \cite{KP}.
An outline of the proof of Theorem \ref{thm:0}(c) is included after that of the proposition.

\begin{proof}
We call $r\ge 1$ a $\tau$-\emph{endtime} if, for some $i\ge 1$, $r$ is the final end-time of $\tau_i$
(otherwise written, $r\in\tau_i\setminus\tau_i^\circ$).
Let $R_X$ be the set of $\tau$-endtimes. It is immediate that $R \subseteq R_X$. Moreover,
by \eqref{eq:8n},
any $r \in R_X$ satisfies $r\in R$ with probability $\frac12$ (these events being independent
for different $r$).
Therefore,
\begin{equation}\label{eq:31n}
\PP(m\in R) = 2 \PP(m\in R_X), \qq m\ge 1.
\end{equation} 

By Lemma \ref{lem:3}, the event $\{m\in R_X\}$ is the subset of all $\om\in\Om_m$ 
satisfying $\om_{m-1}\om_m=\H\T$ and $S(\om)=0$.
Let $h$ be the number of heads, and $r$ the number of runs (of either heads or tails). 
If $r$ is even, (\resp, odd), then such sequences begin $\H$ (\resp, $\T$), and they invariably
finish with a tailrun of exactly one tail. By Remark \ref{rem:2}, since the aggregate score is $0$,
we have $h=r$ if $r$ is even, and $h=r-1$ if $r$ is odd.

We use the fact that the number of $p$-partitions of the integer $q$ is 
$\binom {q-1}{p-1}$.
By partitioning the heads and tails into $r$ runs subject to the above, and interleaving headruns and tailruns,
we obtain that
$$
\vert\{m\in R_X\}\vert= \Si_1+\Si_2
$$
where
\begin{align*} %\label{eq:6n}
\Si_1&= \sum_{r \text{ odd}} 
\binom{m-h-2}{\frac12(r+1)-2} \binom{h-1}{\frac12(r-1)-1}
=\sum_{r \text{ odd}} 
\binom{m-r-1}{\frac12(r-3)} \binom{r-2}{\frac12(r-3)} ,\\
\Si_2&= \sum_{r\text{ even}}
\binom{m-h-2}{\frac12 r-2} \binom{h-1}{\frac12 r-1}
= \sum_{r\text{ even}}
\binom{m-r-2}{\frac12 r-2} \binom{r-1}{\frac12 r-1}.
%\label{eq:7n}
\end{align*}
Set $r=2s+1$ (\resp, $r=2s$) in $\Si_1$ (\resp, $\Si_2$) and add to obtain
\begin{align}\label{eq:9n}
\vert\{m\in R_X\}\vert
 &= 
\sum_{s=2}^\oo \left[\binom{m-2s-2}{s-1}+ \binom{m-2s-2}{s-2}\right]
\binom{2s-1}{s-1}\\
&=\sum_{s=2}^\oo \binom{m-2s-1}{s-1}\binom{2s-1}{s-1}.\nonumber
\end{align}
Therefore,
\begin{equation}\label{eq:11n}
\PP(m\in R_X) = 2^{-m} \vert\{m\in R_X\}\vert
= \frac14 \sum_{s=2}^\oo \PP(T_{m-2s-1}= s-1)\PP(T_{2s-1}=s -1),
\end{equation}
where $T_k$ has the binom$(k,\frac12)$ distribution. 
By Stirling's formula (or \cite[Thm 1.1]{SW}),
\begin{equation}\label{eq:10n}
\PP\left(T_{2s-1}=s -1\right) \sim \frac 1{\sqrt{\pi s}}\q\text{as } s\to\oo.
\end{equation}

We may occasionally use real numbers in the following where integers are expected.
The term $\PP(T_{m-2s-1}=s -1)$ in \eqref{eq:11n} is a maximum when 
$m-2s-1=2(s-1)$, which is to say that $s=\frac14 (m+1)$. Let $\gamma\in(\frac12,\frac23)$.
We may restrict the summation in \eqref{eq:11n} to values of $s$ 
satisfying $\vert s-\frac14 m\vert < m^\gamma$. To see this, note that
\begin{align*}
\sum_{s\ge  \frac14m+ m^\gamma} \PP(T_{m-2s-1} = s-1)
&\le \sum_{s\ge  \frac14m+ m^\gamma} \PP(T_{m/2} \ge s-1),
\end{align*}
which tends to $0$ as $m\to\oo$ by the moderate-deviation theorem of Cram\'er \cite{Cram}
(or, for a more modern treatment, see Feller \cite[p.\ 549]{F2}). 
We have used the fact that $T_k$ is 
stochastically increasing in $k$. A similar argument applies for $s\le \frac14 m - m^\gamma$.

Suppose $\vert s - \frac14 m\vert < m^\gamma$.
By \cite[Thm 1.2]{SW}, there is an absolute constant $C$ such that
$$
\left\vert \PP(T_{m-2s-1}=s -1)- \sqrt{\frac 2{\pi (m-2s-1)}} 
\exp\left(-\frac{(4s-m-1)^2}{2(m - 2s-1)}\right)\right\vert 
\le \frac C {m^{2/3}}.
$$
It follows that
$$
\sum_{\vert s - \frac14 m\vert < m^\gamma} 
\PP(T_{m-2s-1}=s -1)
$$
deviates from 
$$
\Psi_m:=\sum_{\vert s - \frac14 m\vert < m^\gamma}\sqrt{\frac 2{\pi (m-2s-1)}}
\exp\left(-\frac{(4s-m-1)^2}{2(m - 2s-1)}\right)
$$
by at most $C(2m^\gamma+1)/m^{2/3}$, which tends to $0$.
Express $\Psi_m$ as an integral, make the change of variable 
$$
\beta = \frac{4s-m-1}{\sqrt{m-2s-1}}
$$
and let $m\to\oo$ to obtain, by the dominated convergence theorem, that
$$
\Psi_m \to  \frac12\int_{-\oo}^\oo \frac1{\sqrt{2\pi}} e^{-\frac12 \beta^2} \, d\beta = \frac12.
$$
Therefore, the terms $\PP(T_{m-2s-1}=s -1)$ in \eqref{eq:11n} are (asymptotically)
concentrated in the interval $\frac14m\pm m^\gamma$, with total weight $\frac12$. Hence,
by \eqref{eq:31n} and \eqref{eq:11n}--\eqref{eq:10n}, 
$$
\pi_m\sim \frac2{8\sqrt{\pi m/4}} =   \frac1{2\sqrt{\pi m}},
$$
as claimed.
\end{proof}

\begin{proof}[Outline proof of Theorem \ref{thm:0}(c)]
One may deduce (c) from \eqref{eq:13n} by adapting the argument leading to \eqref{eq:4n}.
Alternatively, one may perform a direct calculation as above, and there follows a sketch of this. 
Let $Z_m$ be the set of vectors $\om\in\Om_m$ such that $S(\om)=0$.
Elements $\om\in Z_m$ may be expressed as interleaved headruns and tailruns, with the counts
of heads and tailruns being balanced by the condition $S(\om)=0$ (see Remark \ref{rem:2}). 
Such $\om$ may start with either $\H$ or $\T$, and each case leads to two terms as in the first line of
\eqref{eq:9n}. Thus, $\vert Z_m\vert$ is the sum of four terms, each being the product of two 
binomial coefficients. The analysis continues as in the above proof.
\end{proof}

\section*{Acknowledgements} 
GRG thanks Daniel Litt for a sweet question, and Charles McGinnes for drawing his attention to it.
He thanks Richard Weber and David Stirzaker for useful correspondence.

\bibliography{twitter}
\bibliographystyle{amsplain}
\end{document}