# Alice and Bob flipping coins puzzle

Published on

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:

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.