Stay informed with the Stay informed with the
Recent Articles
Best of Donald Catlin

# Gaming Guru  ### Penney's Game

6 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.

 Player A Player B Odds favoring Player B HHH THH 7 to 1 HHT THH 3 to 1 HTH HHT 2 to 1 HTT HHT 2 to 1 THH TTH 2 to 1 THT TTH 2 to 1 TTH HTT 3 to 1 TTT HTT 7 to 1

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

 s1 = HHH s2 = HHT s3 = HTH s4 = HTT s5 = THH s6 = THT s7 = TTH s8 = TTT

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

or

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:

p1 = 1
p2 = 1
p3 = 0
p4 = 2/3
p5 = 1
p6 = 1/3
p7 = 2/3
p8 = 2/3

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

or

Prob(win) = 1/8 + 1/8 + 0 + 2/24 + 1/8 + 1/24 + 2/24 + 2/24

or

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 711cat@comcast.net

Recent Articles
Best of Donald Catlin
Donald Catlin Don Catlin is a retired professor of mathematics and statistics from the University of Massachusetts. His original research area was in Stochastic Estimation applied to submarine navigation problems but has spent the last several years doing gaming analysis for gaming developers and writing about gaming. He is the author of The Lottery Book, The Truth Behind the Numbers published by Bonus books.

#### Books by Donald Catlin:

Lottery Book: The Truth Behind the Numbers
Donald Catlin
Don Catlin is a retired professor of mathematics and statistics from the University of Massachusetts. His original research area was in Stochastic Estimation applied to submarine navigation problems but has spent the last several years doing gaming analysis for gaming developers and writing about gaming. He is the author of The Lottery Book, The Truth Behind the Numbers published by Bonus books.

#### Books by Donald Catlin:

Lottery Book: The Truth Behind the Numbers