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.