Subsequence of Coin Tosses


I got this problem from Rustan Leino, who got it from Joe Morris, who created it.

I solved it and wrote up my solution.


Each of two players picks a different sequence of two coin tosses. That is, each player gets to pick among HH, HT, TH, and TT. Then, a coin is flipped repeatedly and the first player to see his sequence appear wins. For example, if one player picks HH, the other picks TT, and the coin produces a sequence that starts H, T, H, T, T, then the player who picked TT wins. The coin is biased, with H having a 2/3 probability and T having a 1/3 probability. If you played this game, would you want to pick your sequence first or second?

Solution     Reveal