Alice and Bob flipping coins puzzle

Daniel Litt on Twitter suggests a puzzle with a surprising answer:

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?

— Daniel Litt (@littmath) March 16, 2024

Like many others, I intuitively assumed the answer would be Alice, since her winning segments can overlap, while Bob’s can’t. And yet the right answer is Bob:

The correct answer is “Bob.” Congrats to the 10% who got it right — those few brave dreamers.

— Daniel Litt (@littmath) March 17, 2024

To figure out the answer, let’s represent the game as the following Markov chain:

We start at \(S_1\), and every time a coin is flipped, we move to another state according to the diagram. When we reach state \(S_3,\) Alice gets a point, and when we reach \(S_4,\) Bob gets a point.

The transition matrix for this Markov chain is

\[ \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \\ 0 & 0 & 0.5 & 0.5 \\ 0 & 0 & 0.5 & 0.5 \\ 0.5 & 0.5 & 0 & 0 \end{pmatrix} = 0.5 \cdot \begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix}. \]

While raising this matrix to the \(n\)th power would allow us to compute the probabilities of ending up in different states after \(n\) steps, this is not enough to keep track of Alice’s and Bob’s scores. For that, let’s multiply the transition probabilities by \(x\) if Alice gets a point after a transition to that state and by \(x^{-1}\) if Bob does. Our matrix is then

\[A = 0.5 \cdot \begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & x & x^{-1} \\ 0 & 0 & x & x^{-1} \\ 1 & 1 & 0 & 0 \end{pmatrix}. \]

Transition probabilities computed using such a matrix are Laurent polynomials in \(x\), \(\sum a_k x^k\), where \(a_k\) is the probability of arriving at the given state and having Alice earn \(k\) more points than Bob. So to answer the original question, we need to see whether the sum of the coefficients of \(x^k\) for \(k>0\) is more, less, or equal to the sum of the coefficients of \(x^k\) for negative \(k\) after 100 steps. Since we start at \(S_1\) and can finish in any state, the polynomial of interest is the sum of the first row of \(A^{100}\).

To summarize, if

\[ P_{100}(x) = \begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} \cdot A^{100} \cdot \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \sum_{k > 0} a_k x^k + \sum_{k > 0} b_k x^{-k} + c, \]

then \(\sum a_k\) is the probability of Alice’s win, \(\sum b_k\) is the probability of Bob’s win, and \(c\) is the probability of a tie.

For the record, \(P_{100}(x)\) is:

0.5^100 (x^-50 + 1325 x^-49 + 294050 x^-48 + 26617290 x^-47 + 1330255815 x^-46 + 42919935835 x^-45 + 983156559210 x^-44 + 17033316749820 x^-43 + 233400608147735 x^-42 + 2614381239414735 x^-41 + 24550574713787010 x^-40 + 197150946519643550 x^-39 + 1375679410685414450 x^-38 + 8451073972164127108 x^-37 + 46210399961145343413 x^-36 + 227004362149489184022 x^-35 + 1009860516432421484187 x^-34 + 4096712177858121360399 x^-33 + 15247749308938974542421 x^-32 + 52350824044788156054216 x^-31 + 166607171077709190756060 x^-30 + 493645720376366009163516 x^-29 + 1367143433188619109053352 x^-28 + 3551954012109459164577376 x^-27 + 8686109884277283187997106 x^-26 + 20055225149893348816333554 x^-25 + 43844627549786945958589680 x^-24 + 91001422499460503626585260 x^-23 + 179763829541066577971612952 x^-22 + 338757354861894875655388932 x^-21 + 610315290987050592852426198 x^-20 + 1053386609896119310058220228 x^-19 + 1745118407135736558029089726 x^-18 + 2780043435628079169902430486 x^-17 + 4265870818552696769971996446 x^-16 + 6315241299298077313067374248 x^-15 + 9033468660829178932648222012 x^-14 + 12503156034451523603337781244 x^-13 + 16767474523347110492502105992 x^-12 + 21814598828347171620337357152 x^-11 + 27566098692592563661052910714 x^-10 + 33871849156423377148712374730 x^-9 + 40513231768576837533202703640 x^-8 + 47215173793461455702590625004 x^-7 + 53666145312218517883076816204 x^-6 + 59543892735365660957139789376 x^-5 + 64543704258920714616943515626 x^-4 + 68405570616760641713507980732 x^-3 + 70936793516426715075493432331 x^-2 + 72027343751505931141583428951 x^-1 + 71656412569848144755925222552 + 69889902879368773013173398330 x^1 + 66869833498941600008977020285 x^2 + 62797584077826886590138297533 x^3 + 57913469629702003919294540728 x^4 + 52475267875032276436535696432 x^5 + 46738074687809409100604254222 x^6 + 40937334350174219405131043774 x^7 + 35276210892780037700873584024 x^8 + 29917762478918476882474277364 x^9 + 24981757635389467855166986572 x^10 + 20545499627554709440186102728 x^11 + 16647734116451790331493872286 x^12 + 13294601803478278796908527364 x^13 + 10466633422619434205715329714 x^14 + 8125926604510988498320158730 x^15 + 6222846658893522578565699494 x^16 + 4701814476526100204432324608 x^17 + 3505952179066875448077681428 x^18 + 2580529813081249595335291068 x^19 + 1875284165409224711691937404 x^20 + 1345762480733919638881619816 x^21 + 953884541799647548467422492 x^22 + 667924788912881555961042316 x^23 + 462101645635764580234757556 x^24 + 315933195502895341298309504 x^25 + 213484478528509628644574020 x^26 + 142597606903299702697618140 x^27 + 94165295328566214405929076 x^28 + 61483190066811250498536216 x^29 + 39697162852338816024840079 x^30 + 25348214742043061522139419 x^31 + 16008996325093659482849398 x^32 + 10001161522302185560020758 x^33 + 6180791128771176344008963 x^34 + 3779023811996709991594019 x^35 + 2286066208917365558991896 x^36 + 1368359999967026032354752 x^37 + 810476154998045342538654 x^38 + 475041466638122452084414 x^39 + 275546274649221072591904 x^40 + 158178293697206665493492 x^41 + 89867648637382149651024 x^42 + 50533126782451168142548 x^43 + 28123845113051129416418 x^44 + 15491932054735130750508 x^45 + 8446422906616520626494 x^46 + 4558036012110548547798 x^47 + 2434549498994866786034 x^48 + 1287036656999057467424 x^49 + 673422983571685912648 x^50 + 348737888851294898280 x^51 + 178735377499734476360 x^52 + 90658265801360274016 x^53 + 45506194887963205806 x^54 + 22603387487011330494 x^55 + 11109477277752161064 x^56 + 5402634939088716388 x^57 + 2599348281853560988 x^58 + 1237186710532642568 x^59 + 582504495903896934 x^60 + 271258374586669636 x^61 + 124915774672520357 x^62 + 56888561881025689 x^63 + 25615767980815224 x^64 + 11399249487823014 x^65 + 5014926877132547 x^66 + 2180915576957059 x^67 + 936384359299208 x^68 + 397188128932528 x^69 + 166612052646818 x^70 + 68893011316114 x^71 + 28088731372888 x^72 + 11348888534124 x^73 + 4513130425164 x^74 + 1759354998368 x^75 + 683049732010 x^76 + 261506110220 x^77 + 96634341361 x^78 + 35818805501 x^79 + 13299438184 x^80 + 4606342574 x^81 + 1599386433 x^82 + 586908453 x^83 + 189264458 x^84 + 58562524 x^85 + 21967781 x^86 + 6714397 x^87 + 1655690 x^88 + 664210 x^89 + 206498 x^90 + 32856 x^91 + 14727 x^92 + 5330 x^93 + 390 x^94 + 198 x^95 + 101 x^96 + 2 x^97 + x^98 + x^99)

Tallying up the coefficients, Alice wins with probability \(580127949239420834381088427404/2^{100} ≈ 0.4576\), Bob wins with probability \(615866238418960422359689555420/2^{100} ≈ 0.4858\), and there is a tie with probability \(71656412569848144755925222552/2^{100} ≈ 0.0565\).

Here are the outcome probabilities for different numbers of tosses (cf. the simulation results here).

The Haskell code for computing the probabilities is available here.