How to Answer Questions of the Type: If you toss a coin n times, how likely is HH to show up more than HT?

By
Shalosh B. Ekhad and Doron Zeilberger
.pdf   .tex  

(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)

First Written: May 20, 2024

Last update (of this web-page, and the Maple package, but not the paper): June 14, 2024

Dedicated to Dr. Tamar Zeilberger on her birthday.

On March 16, 2024, Daniel Litt, in an X-post, proposed the following brainteaser:

"Flip a fair coin 100 times. It gives a sequence of heads (H) and tails (T). For each HH in the sequence of flips, Alice gets a point; for each HT, Bob does, so e.g. for the sequence THHHT Alice gets 2 points and Bob gets 1 point. Who is most likely to win?"

(see also here)

We show the power of symbolic computation, in particular the (continuous) Almkvist-Zeilberger algorithm, to answer this, and far more general, questions of this kind.

Added May 24, 2024: Daniel Litt kindly pointed our attention to the following:

Mihai Nica's fascinating lecture

Added May 30,2024:

Challenge to Continuous Probabilists

We are offereing to donate 100 dollars to the OEIS foundation in honor of the first prover(s) of the following problem

Part 1: For any word a in the alpahbet {1,...,m} let A(n)(a) be the (discrete) r.v. "number of occurrences of a as a consecutive subword (aka "factor") in a (uniformaly) random n-letter word in {1,...,m}. It is well-known, and failry easy to prove, that it is asymptotically normal.

Prove For any two words a and b (of the same length k) , the pair [(A(n)(a) , A(n)(b)] are joint-asymptotically normal (of course not independently) and find the bi-variate pdf, fa,b(x,y), in the form

1/C*exp(-(x-μ)^2/s1^2-(y-μ)^2/s2^2+ρ(x-μ)(y-μ)) (C is such that the integral is 1, and μ=(1/m)^k)

where the variances and covariance are determined from the asymptotics for the disterete case (available from procedure MomsAB(m,A,B,n) in the Maple package)

Part 2: Obviously if |a|=k

E[A(n)(n)]=(n-k+1)*(1/m)^k

Let s1, s2, ρ be such that

Var(A(n)(n))=s12n + O(1)

Var(B(n)(n))=s22n + O(1)

Cov(A(n)(n), B(n)(n))=ρ*n+O(1)
[Note that this ρ may not be the same as the above ρ but they are simply related]

Use some kind of (local) bi-variate central limit theorem to find a nice (hopefully a simple rational function also involving π, of course) expression M(s1,s2,ρ) such that

Pr((An(n) > Bn(n))=1/2-M(s1,s2,ρ)/sqrt(n)+ O(1/n3/2)

[Note: see the paper for the background and details]

Added June 11, 2024: A version of this problem was brilliantly solved by Mihai Nica, who kindly allowed me to post his brilliant asymptotic formula . It was inspired by an email exchange with Svante Janson. Nica and Janson may collaborate in a paper making everyhing "rigorous", but being an experimental mathematician (DZ) and an experimental machine (SBE), we completely believe it, and we tested it in many examples (see the bottom of this page). The promised donation to the OEIS, in honor of Mihai Nica and Svante Janson, will be made soon.

Added June 14, 2024: The promised donation in honor of Svante Janson and Mihai Nica was made two days ago, and now it is acknoledged in the

OEIS Foundation Donation page (do ^F for Svante or ^F for Nica)

Thanks to Mihai Nica's formula, that we implemented in procedure Mihai(m,A,B), we formulated another cojecture:

The most unfair bet for a fair coin with words of length k is Hk-1T vs. Hk .

We tested it for k up to 6 (see bottom of this page). Also the analogous statement for larger alphabets seems to be true. We are offering another $100 to the OEIS for a proof of this new challenge.

Added June 12, 2024: Simon Segert also solved the problem, brilliantly. See his beautiful paper .

Added Aug. 30, 2024: read this nice Quanta article by Erica Klarreich.

Maple Package

Sample Input and Output files

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

Doron Zeilberger's Home Page