One day I received an email from my coauthor, 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.
Heads or tails?
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 "headsheadsheads" (HHH) and Player B has selected "tailsheadsheads" (THH). Then the coin is flipped repeatedly, resulting in a sequence like the following:
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).
Table 1
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:
Rephrasing this in terms of a game, then we get
Figure 1: The relationship between the eight triples. No matter which of the eight triples A chooses, there is always a triple that B can choose that has a better chance of coming up first (i.e. the triple that points to Player A's choice). Player B's best choices form a looped relationship between the four inner triples in this figure.
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 nontransitive 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.
Rock beats scissors beats paper beats rock.
Such looped relationships may seem unfamiliar at first, but we all know an example: the old game of rockscissorspaper. 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 rockscissorspaper 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.
 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.
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.
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
$$(\frac{1}{2})^3=\frac{1}{8}.$$ Thus $$P(\mbox{THH appearing before HHH})= 1\frac{1}{8}=\frac{7}{8}.$$ 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 $$P(\mbox{HHT in first 3 flips})+P(\mbox{HHHT in first 4 flips})+P(\mbox{HHHHT in first 5 flips})+....$$ This gives the infinite sum $$1/8+1/16+1/32+... = \sum_{n=3}^{\infty}(\frac{1}{2})^n.$$ Using the rule for summing geometric series we can evaluate this sum to get $$\sum_{n=3}^{\infty}(\frac{1}{2})^n = \frac{\frac{1}{8}}{1\frac{1}{2}}=\frac{1}{4}.$$ (You can read more on geometric series on Plus .)
This calculation gives the probability of HHT winning. The probability of THH winning is therefore $$1\frac{1}{4}=\frac{3}{4},$$ 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 $A$ and $B$, the leading numbers give us a way of working out the Player B's odds. Write $AA$ for the leading number we get using triple $A$ as the upper and lower sequence, $AB$ for the leading number we get using triple $A$ as the upper sequence and triple $B$ as the lower sequence, and so on. The odds of Player $B$ winning are given by the equation $$(AAAB)/(BBBA).$$
In our example with A given the triple HHH and B by the triple THH we have

 


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 $$\frac{AAAB}{BBBA}=\frac{70}{43}=7.$$ 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 $p$ and Player B's probability of winning as $q,$ we obtain $$p=\frac{1}{1+7}=\frac{1}{8}, q=\frac{7}{1+7}=\frac{7}{8}.$$
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.
Table 2: The probabilities of winning for players A and B (for sequences of length 3).
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.
A well randomised pack of cards
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 79 tricks being played, which increases the odds of RRB winning. For example, the probability of RRB winning a game with 7 tricks is $$P(RRB,7)=C_7(\frac{2}{3})^7+C_6(\frac{2}{3})^6(\frac{1}{3})+C_5(\frac{2}{3})^5(\frac{1}{3})^2+C_4(\frac{2}{3})^4(\frac{1}{3})^3=0.827,$$ 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 cardbased version as the HumbleNishiyama 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), 120125.
 Martin Gardner, Time Travel and Other Mathematical Bewilderments, W. H. Freeman, 1988, 5569
 Stanley Collings, Coin Sequence Probabilities and Paradoxes, Bulletin of the Institute of Mathematics and its Applications, 18, 1982, 227232.
About the authors
Steve Humble
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
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.
Comments
Penny Ante game
I've been studying the Penny Ante game and took a look at some of the math involved. The game is logically flawed and it can be shown. No triplet combination has better odds of coming out than any other. Also, at least, some of the math here is onesided. For example, the probability of TTH coming out is also 1/8(i.e. 1/2 X 1/2 X 1/2) and the probability of HHH coming out would be 11/8 giving 7/8. This gives the same probability for both triplets. Aside from this, I've manually worked through all combinations and ,undoubtably, all triplets have an equal chance of coming out.
Penny Ante game
Actually, I have to correct myself on the math part. The probability of TTH coming out is 1/8(i.e. 1/2 X 1/2 X 1/2) and the probability of HHH coming out is also 1/8(i.e. 1/2 X 1/2 X 1/2). This is because there are 8 possible triplet combinations.
Penny Ante Game
Please look more closely at the article Submitted by Anonymous on November 24 2012.
The article is not really looking at the odds of a combination of three flips of a coin where there are 8 possible combinations and as you have stated TTH is one of those eight combinations, and as an equal chance of coming up as the other seven combinations.
The article is looking at a number of flips and the first occurance of a combination, they looked at the easiest combination to see HHH and said that if HHH was not the first three flips then if you kept flipping THH must come up before HHH.
This is a random number of flips TTHTHTTHHH as you can see HHH occurs at the end on flips 8,9 and 10 but just before it flips 7,8 and 9 have THH so THH comes up first.
So as long as there is a T in one of the first three flips THH will always come up before HHH, you can write T's and H's all day long and as long as you have a T in the first three flips then THH will always come up before HHH.
the proof of Collings's theorems
Hi,
Thank you for the posting. I really enjoy the reading. I do have a question about the proof of Conway's algorithm. Professor Nishiyama uses theorem X, Y, Z from Stanely Colings (1982) for the proof. But I couldn't find a copy of this 1982 article and it would be great if you can post the proof of the 3 theorems from Collings.
Thank you.
Nice Stuff
One flaw. This is flawed a little bit. If you go by symbols on paper, then yes, you can use this info. But if you actually flip a coin in real life, heads will come up way more times than tails. Always pick Heads. The weight of the head on that side of the coin makes a difference. Along with gravity. So, on paper, yeah, you can use your info. But in real life, you can't.
More Often Heads
Yeah, um, this is not true. I'm not sure what country you live in or what kind of currency is used there but this is not the case in most places with standardized currency. Just because the head side weighed more does not mean that it is more likely to be heads. In fact, it is a 5149 relationship, the advantage being to the side of the coin that started up. Look to Numberphile on youtube and their video of "How Random is a Coin Toss"
https://www.youtube.com/watch?v=AYnJv68T3MM
No flaw
Any background bias due to mass distribution would have to be too small to be relevant to probabilities of Penney's.
The probability of:
1. the total number of tosses it will take (for each of the eight possible sequences)
NOT
2. getting the sequence in three flips
YES we all know that for any random 3 flips, each sequence has equal probability of 1/8
For greater than 3 flips it is no longer equal, but that doesn't seem to explain everything.
Logic would suggest that:
"if no matter what sequence you choose, there is always one of the other seven that will beat it"
should lead to an infinite regression, but it doesn't, its like that voting paradox (for 3 people) when everyone beats someone and hence everyone is beaten by someone.
I came across this in an edx.org course on Quantum Mechanics dealing with 'spin'.
The video starts the explanation from the point of HH vs HT, and moves on from there.
The video is unlisted, but as the course can be viewed for free, and its a plug for the course I hope they don't mind.
https://youtu.be/rfzG7Iomfrg
Odds not quite true for cards
> 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.
That's not quite true. If starting with a full deck of cards, the odds of BBB winning are (26/52)*(25/51)*(24*50)=1/8.5. Similarly, the odds of RBB winning are 7.5/8.5, giving RBB even more overwhelming odds of 7.5:1 in a single trick versus BBB.
Youtube
I found a Youtube of HumbleNishiyama Randomness Game on the website.
http://yutakanishiyama.sakura.ne.jp/index.html