%cointoss.tex: a Plain TeX file by Lucy Martinez and Doron Zeilberger
%How many coin tosses does it take until you get r Heads AND s Tails?
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\S{{\cal S}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\W{{\cal W}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf 
How many coin tosses would you need until you get n Heads OR m Tails
}
\bigskip
\centerline
{\it Svante JANSON, Lucy MARTINEZ and Doron ZEILBERGER}
\bigskip


{\bf Abstract}: We harness both human ingenuity and the power of symbolic computation to study the number of coin tosses until reaching
$n$ Heads OR $m$ Tails. We also talk about the closely related problem of reaching $n$ Heads AND $m$ Tails.


{\bf Preface}

If you toss a coin whose probability of Heads is $p$, until you reach $n$ Heads, you should expect to make $n/p$ coin tosses, and the variance
and higher moments are easily derived from the explicit probability generating function, (as usual $q:=1-p$)
$$
\sum_{k=0}^{\infty} {{n+k-1} \choose {n-1}} (px)^{n} (qx)^{k} \, = \, \left (\frac{px}{1-qx} \right )^n \quad,
$$
which is essentially the {\it negative-binomial distribution} (note that usually one only counts the number of Tails until you reach $n$ Heads,
but we are interested in the total number of coin-tosses, so we add the $n$ Heads. From this probability generating function
we can extract not only the expectation, but by repeated differnting with respect to $x$, and plugging in $x=1$ we can explicit
expressions of as many as desired {\it factorial moments}, that in turn gives the {\it moments}, and from them the {\it central moments}.
Then we can compute the {\it scaled central moments}, take the limit as $n \rightarrow \infty$ and prove that for a {\bf fixed} $p$
it tends to the good old Normal Distribution.

But what if you are not {\it Headist}? What if you like Tails just as much, and stop as soon as you get
$n$ Heads OR $m$ Tails? Another interesting stopping rule is to make {\bf both} Heads and Tails happy and keep tossing
until you get $n$ Heads AND $m$ Tails. Now things are not as nice and simple.
Nevertheless, using Wilf-Zeilberger algorithmic proof theory [PWZ],
we can derive the next-best thing, linear recurrences that enable very fast comptation of these quantites.
In the case of a fair coin and  tossing until getting $n$ Heads or $n$ Tails, we get, explicit expressions not only for the expectation and variance, but for many
moments, and prove that their centralized-scaled tend, rather than the standard normal distribution, $N(0,1)$,  to those of $-|N(0,1)|$.

While we (or rather our computer) can go pretty far, we can not prove it for {\it all} moments. In the second part of this article we will prove it completely.




{\bf References}

[BFV] Simon Blatt, Uta Freiberg, and Vladimir Shikhman, {\it The mathematics of family planning  in the Talmud}, Math. Intelligencer {\bf 47(2)} (Spring 2025), 120-125.

[PWZ] Marko Pektovsek, Herbert S. Wilf, and Doron Zeilberger, {\it ``A=B''}, AK Peters, 1996. Freely available from {\tt https://sites.math.rutgers.edu/\~{}zeilberg/AeqB.pdf} \quad .

[W] Wikipedia, {\it Negative Binomial Distribution}, \hfill\break
{\tt https://en.wikipedia.org/wiki/Negative$\_$binomial$\_$distribution} \quad .

\bigskip
\hrule
\bigskip
Svante Janson, Department of Mathematics,  Uppsala University, Box 480 751 06 Uppsala, SWEDEN. {\tt Svante.Janson@math.uu.se} \quad .
\bigskip
Lucy Martinez, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA.  {\tt lm1154@math.rutgers.edu} \quad .
 Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA.  {\tt DoronZeil@gmail.com}   \quad .


Written: {\bf Nov.  2025}.

\end
