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 .
Maple Package
-
Litt.txt
A Maple package for solving any problems of the type: probability of winning a bet between Alice and Bob, if Eve rolls a fair m-sided die, and
Alice's score is the number of occurrences of a member of the set of words A, and Bob's score
is the number of occurrences of occurrences of a member of the set of words B, for any set of words A,B, in {1,...,m}
Sample Input and Output files
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 11 in a (uniformly-at-) random word on {1,2} of length n,
for all possible choices of Alice of occurrences of 2-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 111 in a (uniformly-at-) random word on {1,2} of length n,
for all possible choices of Alice of occurrences of 3-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 1111 in a (uniformly-at-) random word on {1,2} of length n,
for all possible choices of Alice of occurrences of 2-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 11111 in a (uniformly-at-) random word on {1,2} of length n,
for all possible choices of Alice of occurrences of 2-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 11 in a (uniformly-at-) random word on {1,2,3} of length n,
for all possible choices of Alice of occurrences of 2-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 111 in a (uniformly-at-) random word on {1,2,3} of length n,
for all possible choices of Alice of occurrences of 3-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 1111 in a (uniformly-at-) random word on {1,2,3} of length n,
for all possible choices of Alice of occurrences of 4-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 11 in a (uniformly-at-) random word on {1,2,3,4} of length n,
for all possible choices of Alice of occurrences of 2-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 111 in a (uniformly-at-) random word on {1,2,3,4} of length n,
for all possible choices of Alice of occurrences of 3-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 1111 in a (uniformly-at-) random word on {1,2,3,4} of length n,
for all possible choices of Alice of occurrences of 4-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 11 in a (uniformly-at-) random word on {1,2,3,4,5} of length n,
for all possible choices of Alice of occurrences of 4-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of 111 in a (uniformly-at-) random word on {1,2,3,4,5} of length n,
for all possible choices of Alice of occurrences of 4-letter words (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of a 2-letter word in {1,2}, w1,
and Alice's score is a 2-letter word in {1,2}, w2, in a uniformly-at-random n-letter word in {1,2},
for all possible choices of w1 and w2 (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of a 3-letter word in {1,2}, w1,
and Alice's score is a 3-letter word in {1,2}, w2, in a uniformly-at-random n-letter word in {1,2},
for all possible choices of w1 and w2 (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of a 4-letter word in {1,2}, w1,
and Alice's score is a 4-letter word in {1,2}, w2, in a uniformly-at-random n-letter word in {1,2},
for all possible choices of w1 and w2 (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of a 2-letter word in {1,2,3}, w1,
and Alice's score is a 2-letter word in {1,2,3}, w2, in a uniformly-at-random n-letter word in {1,2,3},
for all possible choices of w1 and w2 (up to equivalence)
the input file produces
the output file
-
If you want to see the probability of Alice winning a bet against Bob, if Bob's score is the number of occurrences of a 3-letter word in {1,2,3}, w1,
and Alice's score is a 3-letter word in {1,2,3}, w2, in a uniformly-at-random n-letter word in {1,2,3},
for all possible choices of w1 and w2 (up to equivalence)
the input file produces
the output file
-
If you want to see more precise asympototics and simpler recurrences for the original Litt problem of HT vs. HH
the input file produces
the output file
-
If you want to see more precise asympototics and simpler recurrences for HHT vs. HHH
the input file produces
the output file
-
If you want to see more precise asympototics and simpler recurrences for HTT vs. HHH
the input file produces
the output file
-
If you want to see more precise asympototics and simpler recurrences for a fair three-sided coin labeled {1,2,3} of 12 vs. 11
the input file produces
the output file
-
If you want to see more precise asympototics and simpler recurrences for a fair three-sided coin labeled {1,2,3} of 123 vs. 111
the input file produces the output file
Added June 11, 2024:
-
In order to confirm Mihai Nica's brilliant asymptotic formula
(inspired by an email exchange with Svante Janson, initiated by us) for
Pr(A > B)- Pr(B > A),
for many cases, the input file produces the output file
-
In order to find all the ranked counterbets and confirmation that the most unfair bets with words in {H,T} of length k, is Hk-1T vs. Hk , for k from 2 to 6,
the input file produces the output file
-
In order to find all the ranked counterbets and confirmation that the most unfair bets with words in {1,2,3} of length k, , for k from 2 to 5, is 1k-223 vs. 1k
the input file produces the output file
-
In order to find all the ranked counterbets and confirmation that the most unfair bets with words in {1,2,3,4} of length k, , for k from 2 to 4, is 1k-3234 vs. 1k
the input file produces the output file
Added June 14, 2024:
-
In order to confirmof Mihai Nica's conjecture that the limit of Third Moment/SecondMoment as n goes to infinity is 3*(HO(m,A)-HO(m,B)) (see Maple code for definition) for words in 2 letters, with length up to length 7,
words in 3 letters, with length up to length 5, words in 4 letters, with length up to length 4:
the input file produces the output file
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page