Stay informed with the
NEW Casino City Times newsletter!
Best of Donald Catlin
Penney's Game6 March 2010
Every now and then in this column I like to look at so-called proposition bets (for example see my archived article An Earful of Cider that appeared in December of 1999). These are wagers that sound like either a sure thing, or at worst a fair bet, and are anything but. A dandy example of this is Penney's Game named after its inventor Walter Penney (Journal of Recreational Mathematics, October 1969, p. 241). I wish to thank my friend The Midnight Skulker for bringing this game to my attention.
The game consists of a series of coin tosses that produce a sequence of H's (heads) and T's (tails). At the start of the game two players agree on the length of the sequences to be generated. This length is usually taken to be three, but can be any larger number. For this article I will use three. Player A then selects a sequence of heads and tails of the required length and shows this sequence to player B. Player B then selects another sequence of heads and tails of the same length. Then a fair coin is tossed until either player A's sequence or player B's sequence appears as a subsequence of these tosses. The player whose sequence appears first wins the game.
The surprising thing about Penney's Game is that as long as sequences of at least length three are used, player B has a considerable advantage over player A. For the three sequence game, the second player can optimize his odds by choosing sequences according to the following table.
Note that in each case the second player's choice is to precede the first player's sequence with the opposite of the second symbol and drop the last symbol. For example, with player A choosing HTH player B changes the second symbol from T to H and places it in front of player A's sequence obtaining HHTH and then drops the last H.
The question is: how do we obtain those odds? Here is one solution. For notational convenience let us define eight sequences according to the following table
In other words, pj represents the conditional probability that we end up with a winning sequence, s2, given that we start out with sj. Notice that if we start out with either s1 or s2 we will end up with a winning sequence. Hence p1 = 1 and p2 = 1. p3 is obviously zero since s3 is A's choice. If we start out with s8 the next sequence is either TTT, s8 again, or TTH which is s7. Since the probability of flipping either a head or a tail is ½ we see that
p8 = ½ p7 + ½ p8
This equation reduces to ½ p8 = ½ p7 or in other words p7 = p8. Noting this if we start out with s4 we obtain either s7 or s8, each with probability ½ so
p4 = ½ p7 + ½ p8 = p7 (or p8)
Hence p4 = p7 = p8. s5 produces either s1 or s2 on the next flip and since both of these have probability 1 of winning p5 = 1. If we begin with s6 the next flip will produce either s4 or s3 so
p6 = ½ p4 + ½ p3
which reduces to p6 = ½ p4 since p3 = 0. Finally, if we begin with s7 the next flip produces either s6 or s5 so
p7 = ½ p6 + ½ p5
p4 = ½ p6 + ½
since p5 = 1 and p4 = p7. Since p6 = ½ p4 we can substitute this in our last equation to obtain
p4 = ¼ p4 + ½
This last equation can be solved for p4 to obtain p4 = 2/3. Hence we have the following:
Since each of the beginning three term sequences occur with probability 1/8 the probability of a win for B is
Prob(win) = 1/8 p1 +1/8 p2 + … + 1/8 p8
Prob(win) = 1/8 + 1/8 + 0 + 2/24 + 1/8 + 1/24 + 2/24 + 2/24
Prob(win) = 16/24 = 2/3
It follows that the probability of a win for A is 1/3 so B is twice as likely to win in this situation as is A. Thus B's advantage is 2 to 1.
All of the other starting sequences for A can be handled using the above technique. It is quite surprising that in a game that sounds fair, that player B has such a large advantage over A. Thanks again to the Midnight Skulker for showing me this interesting game. See you next month.
Don Catlin can be reached at firstname.lastname@example.org
This article is provided by the Frank Scoblete Network. Melissa A. Kaplan is the network's managing editor. If you would like to use this article on your website, please contact Casino City Press, the exclusive web syndication outlet for the Frank Scoblete Network. To contact Frank, please e-mail him at email@example.com.
Best of Donald Catlin