“How to Answer Questions of the Type: If You Toss a Coin n Times, How Likely Is HH to Show up More Than HT?”, 2024-05-22 ():
On March 16, 2024, Daniel Litt, in an Twitter post, proposed the following brainteaser: “Flip a fair coin 100×. 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 eg. for the sequence THHHT Alice gets 2 points and Bob gets 1 point. Who is most likely to win?”
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. [generalization]