Alice and Bob are playing a game. They flip a fair coin 100 times, noting the resulting sequence of 100 heads (H) or tails (T). For each HH in the sequence, Alice scores a point; for each HT, Bob scores a point. For example, given the sequence THHHT, Alice scores 2 points and Bob scores 1 point. Whoever scores the most points wins the game. Who is most likely to win?
I was referred to this problem, which I suspect originally came from this recent tweet. I reeallly like this problem… but not just for the usual reasons of involving probability and having a very unintuitive solution. (Alice’s expected total score is exactly equal to Bob’s expected score, so maybe it’s most likely a tie? On the other hand, Alice’s maximum score is 99, since her pattern can overlap with itself, while Bob can score at most 50 points, so maybe Alice is most likely to win?)
I also like this problem because I didn’t even recognize it– as a special case of a problem I had not only seen before, but discussed here before.
Because I didn’t recognize it, I ended up solving it in a different way, this time using generating functions. It’s a nice obligatory follow-on puzzle to do this in a one-liner in Mathematica or Wolfram Alpha, but it’s not too bad in Python either using SymPy:
from sympy import symbols, expand
n = 100
x = symbols('x')
h, t = 0, 1
for k in range(n):
h, t = expand(h * x + t), expand(h / x + t)
g = h + t
alice, bob, tie = (sum(g.coeff(x, k) for k in range(1, n)),
sum(g.coeff(x, k) for k in range(-n, 0)),
g.coeff(x, 0))
This counts the number of equally probable outcomes where Alice wins, Bob wins, or they tie.
Possibly Wrong 
I ran your script and if I did it right, it says that Alice wins 45.7% of the time, and Bob wins 48.6% of the time, and the last 5.7% is a tie. My intuition is the same as yours, that Alice has more opportunities to win points — i.e. if tails, nothing happens, but if heads, either person has equal opportunity to win a point on the next roll, but if Alice wins, she’s immediately a candidate for a subsequent point, but if Bob wins, he has to wait for another heads for his next opportunity.
Yep, that’s what I like about this problem– it’s essentially exactly the same unintuitive “hot hand fallacy fallacy,” for the shortest streak length
.
I arrived at the same solution via dynamic programming. The idea is to start with the solution for n=1 coin flips, then use that to compute n=2, 3, … all the way to 100.
Here’s the code!
I would love to understand the generating functions approach! It seems elegant, but I have no idea how it works.
Nice! The generating function implementation is effectively also dynamic programming, just in a compact disguise. At each iteration (or inductively if you like), h(x) and t(x) are the generating functions for the number of possible sequences of coin flips (i.e., the coefficients), weighted (i.e., grouped by powers of x) by the *difference* between Alice’s and Bob’s current score, given that the most recent coin flip was heads or tails, respectively.
Great post! I love this problem, and the connection with the hot hand was very interesting.
There is tricky combinatorics problem hidden in here, and it is one which lets you quantify Bob’s advantage over Alice exactly.
Let A(n) be the set of sequence of length n where Alice wins. Let B(n) be the set of sequences where Bob wins. Let B(n+1, H) be the set of sequence of length n + 1, such that Bob wins, AND such that the last flip is heads.
You can prove that for all n > 3, A(n) is exactly equal to B(n+1). Since B(n+1,H) is in bijection with a subset of B(n), by removing the Heads at the end, it follows that A(n) – B(n) is exactly equal to the number of strings where Bob beats Alice by exactly one, and which end with an H.
For example, A(4) contains the four sequences HHHH, HHHT, THHH, and TTHH, while B(5, H) contains the four sequences HTHTH, HTTTH, THTTH, and TTHTH.
Very interesting! For those reading, in the context of the generating function approach in the post, A(n) is (until I get the comment LaTeX formatting figured out):
sum(k>0) of [x^k](h(x)+t(x))
and B(n+1,H) is
sum(k<0) of [x^k](x h(x)+t(x))
which you can verify are indeed equal at every iteration, where we start with
. (I’m not sure I understand the n>3 constraint, since this equality holds right out of the gate? I don’t yet see a nice combinatorial argument, bijective proof, etc., that is maybe only applicable for n>3?)
You are right, there is no need for the n > 3 constraint. For all n ≥ 1, A(n) = B(n + 1, H).
I proved this using a tricky bijection. To be precise, I didn’t directly map A(n) to B(n + 1, H); I had to first enlarge both sets by adding an identical set of elements to both, and then I bijectively paired the enlarged sets.
You might also be interested in this paper which rigorously proves that Bob wins more often: https://arxiv.org/abs/2405.16660
I’m a few months late here, but I’ve been enjoying catching up on these! This problem is a fantastic example of why it’s important to carefully select the right statistics when describing probability distributions. It’s easy to latch onto the fact that both players have equal expected scores, which can mislead our intuition and prevent us from digging deeper to uncover the positive skewness in Alice’s scores.
Here’s my 139-character submission of a Mathematica “one-liner” implementing the dynamic programming approach:
The matrix in my example being diagonalizable leads to very short run times and might imply there is some closed form solution for the scores of each player… This would involve too many applications of the binomial theorem for me to attempt willingly!
It’s worth noting the code could be made shorter using Part instead of Exponent and NumeratorDenominator for special cases like n = 100, but the above answer should be robust for all valid n.
This answer fits tightly into the classic 140-character limit for the Wolfram Tweet-a-Program contest. With the extra character budget of an X post you could prepend “N[#/2^100]&” and convert everything to readable fractions.
Hi Clint! I like the NumeratorDenominator handling of the negative exponents. I cheated a bit in my generating function approach, multiplying everything by
so CoefficientList wouldn’t complain. It’s always a weirdly interesting/frustrating exercise to try to shoehorn a Mathematica expression into something that Wolfram Alpha will accept: this is the best I could do, but I left off the grouping since I couldn’t find a way to get the Take[List] wrapper to work.
Pingback: Alice and Bob on Two-Pi Day | Possibly Wrong