One day I received an email from my co-author, Steve Humble. In some excitement, he told me that a magician named Derren Brown was introducing an interesting game on television. I was a little dubious upon hearing the word "magician", but after close examination I realised that the game had a mathematical background and was an interesting exercise in probability.

The game, called Penney Ante, involves flipping a coin, which you assume has equal probability of coming up heads or tails. The game is played by two players, A and B, who each select a sequence of three flips. For example, assume that Player A selected "heads-heads-heads" (HHH) and Player B has selected "tails-heads-heads" (THH). Then the coin is flipped repeatedly, resulting in a sequence like the following:

HTHTHHHHTHHHTTTTHTHH...

The player whose sequence showed up first (HHH for Player A or THH for Player B) is declared the winner.

A winning strategy

This problem in probability has been around for some time, but is not widely known. Walter Penney first presented it in an article, only ten lines long, in the Journal of Recreational Mathematics in 1969. Martin Gardner later provided a more detailed description in his Mathematical Games column in the October 1974 issue of Scientific American, and later in his book Time Travel and other Mathematical Bewilderments.

When the game is played using patterns of length 3, no matter what sequence Player A chooses, Player B can always make a winning selection. Here are the winning (on average) selections for Player B for each of the eight possible selections for Player A (we will show how to calculate the odds of Player B winning shortly).

According to the table, Player B selecting THH in response to Player A's choice of HHH gives him a 7/8 or 87.5% chance of winning, selecting THH in response to HHT gives a 3/4 or 75% chance of winning , and selecting HHT in response to HTH gives a 2/3 or 66% chance of winning, and so on. And no matter which of the eight choices Player A makes, Player B can always choose a triple that has a greater chance of winning. (You can try this strategy out for yourself either with your own coin or by playing the game online.)

Rock beats scissors beats paper beats rock

There is also another curious aspect to this game. Mathematically speaking, the following is referred to as a transitive relationship:

If A implies B, and B implies C, then A implies C.

Rephrasing this in terms of a game, then we get

If player A beats player B and player B beats player C, then player A beats player C.

But is this a true proposition for the Penney Ante game? Gardner posed that this transitive relationship does not hold in the game. The loop in figure 1 illustrates the non-transitive relationship between the four inner triples. We know from the odds shown in table 1 that THH is stronger than HHH, TTH is stronger than THH, HTT is stronger than TTH, HHT is stronger than HTT, and THH is stronger than HHT. No one of these four triples is the strongest choice.

Such looped relationships may seem unfamiliar at first, but we all know an example: the old game of rock-scissors-paper. In that game, it does not follow that because rock beats scissors and scissors beat paper that therefore rock beats paper. Instead, rock loses to paper, therefore failing to uphold the transitive relationship. Similarly, transitive relationships do not hold in Penney Ante; as in rock-scissors-paper there is no "best play" and the second player can always win. There is no strongest selection for Player A.

Making the strongest choice

But let's return to the winning strategies. Once Player A has made a selection, Player B can use the following rules to choose a triple that is more likely to appear before Player A's:

• For the first call of Player B's triple, choose the opposite of the Player A's second call.

Assume that Player A chooses HHH. In this case, Player A's second call is for H. Flip that selection to a T, and move it to the beginning of Player B's sequence.

• Next, take the first two calls in Player A's sequence, and take those as the second and third call in Player B's.

  In our example doing so results in THH for Player B, a selection that will win against Player A (on average), with odds of 7 to 1.

• Player A's third call is not considered.

You can confirm that each of the selections for Player B in Table 1 follow this rule. But it works for runs of length 3 only — the same algorithm will not necessarily work for other lengths. (You can read more about this strategy for runs of length 3, and strategy's for longer runs in Martin Gardner's excellent book, Time Travel and Other Mathematical Bewilderments. You can also read a more technical paper by Daniel Felix which generalises the winning strategy to runs of any length.)

To see why this method works, let's first consider the strategy when Player A chooses HHH. Suppose that player A's triple does not come up right at the start of the sequence, but further down the line, for example in positions 5,6 and 7. The fact that we're looking at the first appearance of player A's triple gives player B a way of working out whether the digit in position 4 is a H or a T. In our example there must be a T in position 4, as otherwise the first appearance of HHH would be in positions 4,5 and 6. Using this argument, you can work out that the digit in position 4 is always the opposite of player A's second call, namely T. Therefore in this situation, player B's triple, THH, chosen according to the rules above, will come before player A's, namely in positions 4,5 and 6.

The only case in which this doesn't work is when player A's triple comes up in the first three positions — this is why player B has no absolute guarantee of winning.

What are the odds?

Assume that Player A selects HHH, and Player B follows the strategy and selects THH. If HHH appears in the first three tosses, Player A wins. In any other situation Player B wins (as we saw above a T must precede the first appearance of HHH, otherwise it isn't the first appearance of HHH!). The probability that the first three tosses will come up HHH is

Thus Player B's odds are therefore 7 to 1.

It is a similar case when Player A chooses HHT. Again, according to the strategy Player B should choose THH (as the third call of Player A's choice doesn't affect Player B's choice).

As soon as a T is flipped, THH will appear before HHT in the subsequent sequence. So the probability of flipping HHT, or HHHT, or HHHHT..., allowing HHT to win is

This gives the infinite sum Using the rule for summing geometric series we can evaluate this sum to get (You can read more on geometric series on Plus .)

This calculation gives the probability of HHT winning. The probability of THH winning is therefore

which translated into odds gives player 3:1 a chance of winning.

Continuing in this manner, the individual odds for each pair in table 1 can be calculated.(You can watch a nice explanation by James Grime of some of the other probabilities on YouTube.)

Conway's Algorithm

But there is an easier way to work out the odds. The famous mathematician John Conway proposed a beautiful algorithm to do this (you can find out more about Conway in a past interview with Plus). Conway introduced leading numbers as an index indicating the degree of pattern overlap. Leading numbers are also an index of the level of repetition of a given pattern within a preceding pattern.

Conway's algorithm for working out the leading number for two triples works as follows. First, put the two triples one above the other with the digits aligned, as we've done below for the two triples HHH and THH. Now compare the two triples: if they are the same, put a 1 above the first digit of the first sequence, if not put a 0.

0
T	H	H
H	H	H

Next, remove the leading digit from the upper triple, and shift it to the left, aligning the leading elements. Then, compare the first two digits of the upper sequence to the first two digits in the lower sequence: if they are the same, place a 1 above the leading element of the upper sequence, or a 0 otherwise.

1
H	H
H	H	H

Repeat this procedure through to the last element of the upper sequence.

1
H
H	H	H

Finally, compile the results as follows:

0	1	1
T	H	H
H	H	H

The resulting triple of 0s and 1s is an index of the overlap between the two sequences. It can be read as a binary number. In our example, the binary number 011 is equal to the decimal number 3.

Given two triples and , the leading numbers give us a way of working out the Player B's odds. Write for the leading number we get using triple as the upper and lower sequence, for the leading number we get using triple as the upper sequence and triple as the lower sequence, and so on. The odds of Player winning are given by the equation

In our example with A given the triple HHH and B by the triple THH we have

1 1 1 A: H H H A: H H H	0 0 0 A: H H H B: T H H
1 0 0 B: T H H B: T H H	0 1 1 B: T H H A: H H H

Converting these four values to decimal numbers (111 in binary equals 7, 000 equals 0, 100 equals 4 and 011 equals 3) and substituting them into the equation, we have

So Player B’s odds are given as 7, which we take as meaning 7:1, matching with the first entry in Table 1.

Taking Player A’s probability of winning as and Player B’s probability of winning as we obtain

Both Player A and Player B have eight possible selections. Because the players make their selections independently, there are possible matches, and the odds for each are automatically generated by the Conway algorithm as shown in table 2. Taking the best odds for Player B with respect to Player A's selection gives the results listed in table 1. Conway's algorithm is very powerful, in that it can give probabilities not only for sequences of length 3, but for those of any length, or even for sequences of dissimilar length.

Applying a winning strategy to cards

In the preceding sections we examined Penney's Ante using heads and tails in a coin flipping game. Steve Humble and I have been discussing how this might be applied to a more familiar context, such as a card game.

There are 52 cards in a deck, and the 26 black (spades and clubs) and 26 red (hearts and diamonds) cards can be used to substitute for the heads or tails results of a coin flip. Let B represent black cards, and R red cards, so that HHH versus THH when flipping coins could be represented as BBB versus RBB when using cards.

The game is played as follows. Turn the cards over one at a time, placing them in a line, until one of the chosen triples appears. The winning player takes the upturned cards, having won that trick. The game continues with the rest of the unused cards, with players collecting tricks as their triples come up, until all the cards in the pack have been used. The winner of the game is the player that has won the most tricks.

The advantage of using cards lies in their ease of manipulation, and the fact that one does not need to keep track of the results. They can also be well randomised. If all 26 red and black cards are used, then there is exactly a 1/2 chance of choosing either color from the 52 total cards. As cards are removed from the shuffled deck the probability of choosing either colour will wobble around a half, but will never stray far for most of the game.

As an example let's consider BBB and RBB. As for their equivalent version using coins, the probabilities for BBB and RBB are 1/8 and 7/8 respectively, giving RBB overwhelming odds of 7:1 in a single trick versus BBB. If the sequences are RBR versus RRB, however, the odds for RRB are only 2:1. Such odds imply no guarantee of winning in a single trick. Fortunately, playing the game with a whole pack of cards normally results in 7-9 tricks being played, which increases the odds of RRB winning. For example, the probability of RRB winning a game with 7 tricks is

where the C_k are the binomial numbers giving the number of ways of choosing k tricks (to win) out of the 7 tricks.

Playing 7 tricks is a clear advantage for Player B over the 0.667 probability for a single round. Playing the game using cards over 7–9 tricks, which is possible for all the possible matches using one pack of cards, we can expect a very high probability that Player B will win.

We believe that Penney's game is more suited to being played with cards than with coin tosses. We would like to present this new card-based version as the Humble-Nishiyama Randomness Game, and hope that our readers will try it with a deck of cards at home.

References

• Walter Penney, Journal of Recreational Mathematics, 1969, p. 241.
• Martin Gardner, Mathematical Games, Scientific American, 1974, 231(4), 120-125.
• Martin Gardner, Time Travel and Other Mathematical Bewilderments, W. H. Freeman, 1988, 55-69
• Stanley Collings, Coin Sequence Probabilities and Paradoxes, Bulletin of the Institute of Mathematics and its Applications, 18, 1982, 227-232.

---

About the authors

Steve Humble (aka Dr Maths) works for The National Centre for Excellence in the Teaching of Mathematics in the North East of England. He believes that the fundamentals of mathematics can be taught via practical experiments. For more information on Dr Maths go to the Dr Maths website at the IMA.

Yutaka Nishiyama is a professor at the Osaka University of Economics, Japan, where he teaches mathematics and information. He is proud to be known as the "boomerang professor". He is interested in the mathematics of daily life and has written eight books about the subject. The most recent one, "The Mystery of Five in Nature", investigates, amongst other things, why many flowers have five petals.