One day I received an electronic mail from my coauthor, Steve Humble. In some excitement, he told me that a magician named Derren Brown was introducing an interest game on television. I was a little doubtful upon hearing the bible “ magician ”, but after cheeseparing interrogation I realised that the bet on had a mathematical background and was an matter to exercise in probability .
Heads or tails ? The game, called Penney Ante, involves flipping a mint, which you assume has adequate 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 model, 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 follow :
Reading: Winning odds
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 prison term, but is not wide known. Walter Penney first presented it in an article, only ten lines hanker, in the Journal of Recreational Mathematics in 1969. Martin Gardner later provided a more detail description in his Mathematical Games column in the October 1974 emergence of Scientific American, and late in his book Time Travel and other Mathematical Bewilderments .
When the game is played using patterns of length 3, no topic what sequence Player A chooses, Player B can always make a winning survival. here are the succeed ( 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 reaction 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 reaction to HTH gives a 2/3 or 66 % casual 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 opportunity of winning. ( You can try this strategy out for yourself either with your own mint or by playing the game online. )
Rock beats scissors beats paper beats rock
There is besides another curious aspect to this game. mathematically speaking, the watch 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.
trope 1 : The relationship between the eight triples. No matter which of the eight triples A chooses, there is constantly a triple that B can choose that has a better gamble of coming up first ( i.e. the triple that points to Player A ‘s choice ). Player B ‘s best choices form a coil relationship between the four inner triples in this name. But is this a true proposal for the Penney Ante crippled ? Gardner posed that this transitive verb kinship does not hold in the game. The loop in trope 1 illustrates the nontransitive kinship between the four inner triples. We know from the odds shown in board 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 option .
Rock beats scissors beats newspaper beats rock. such looped relationships may seem unfamiliar at first, but we all know an exercise : the old game of rockscissorspaper. In that game, it does not follow that because rock beats scissors and scissors beat newspaper that consequently rock beats paper. alternatively, rock loses to newspaper, consequently failing to uphold the transitive verb 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 win strategies. Once Player A has made a choice, Player B can use the following rules to choose a triple that is more probable 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 lapp algorithm will not necessarily work for early lengths. ( You can read more about this strategy for runs of length 3, and strategy ‘s for longer runs in Martin Gardner ‘s excellent bible, Time Travel and Other Mathematical Bewilderments. You can besides read a more technical composition by Daniel Felix which generalises the winning scheme to runs of any duration. )
To see why this method works, let ‘s first consider the scheme when Player A chooses HHH. Suppose that player A ‘s ternary does not come up properly at the start of the sequence, but further down the credit line, for example in positions 5,6 and 7. The fact that we ‘re looking at the first appearance of musician 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 exercise there must be a T in side 4, as otherwise the first appearance of HHH would be in positions 4,5 and 6. Using this argumentation, you can work out that the digit in military position 4 is constantly the opposite of player A ‘s moment call, namely T. Therefore in this situation, player B ‘s ternary, THH, chosen according to the rules above, will come before player A ‘s, namely in positions 4,5 and 6 .
The alone case in which this does n’t work is when player A ‘s treble comes up in the first three positions — this is why musician B has no absolute guarantee of winning .
What are the odds?
Assume that Player A selects HHH, and Player B follows the scheme and selects THH. If HHH appears in the first three tosses, Player A wins. In any early situation Player B wins ( as we saw above a T must precede the first appearance of HHH, otherwise it is n’t the foremost appearance of HHH ! ). The probability that the foremost three tosses will come up HHH is
Thus
Player B’s odds are therefore 7 to 1.
ThusPlayer B ‘s odds are therefore 7 to 1. It is a like subject when Player A chooses HHT. Again, according to the scheme Player B should choose THH ( as the onethird call option of Player A ‘s choice does n’t affect Player B ‘s choice ). ampere 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 This gives the countless sumUsing the rule for summing geometric series we can evaluate this union to get ( You can read more on geometric series on Plus . ) This calculation gives the probability of HHT winning. The probability of THH victorious is therefore
which translated into odds gives player 3:1 a chance of winning.
which translated into odds gives actor 3:1 a prospect of winning. Continuing in this manner, the individual odds for each couple in table 1 can be calculated. ( You can watch a dainty explanation by James Grime of some of the other probabilities on YouTube. )
Conway’s Algorithm
But there is an easier means to work out the odds. The celebrated mathematician John Conway proposed a beautiful algorithm to do this ( you can find out more about Conway in a past consultation with Plus ). Conway introduced leading numbers as an index indicating the academic degree of pattern overlap. Leading numbers are besides an index of the level of repetition of a given form within a predate form .
Conway ‘s algorithm for working out the leading count for two triples works as follows. First, put the two triples one above the early 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 lapp, 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 amphetamine triple, and shift it to the entrust, 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 lapp, place a 1 above the leading chemical element of the amphetamine sequence, or a 0 otherwise .
1  
H  H  
H  H  H 
repeat this procedure through to the last element of the upper berth 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 issue. In our case, the binary number 011 is equal to the decimal fraction count 3 .
Given two triples and , the leading numbers give us a way of working out the Player B ‘s odds. Write for the leading act we get using treble as the upper and lower sequence, for the leave number we get using trio as the upper sequence and triple as the lower succession, and so on. The odds of Player gain are given by the equality
In our case with A given the ternary 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
so Player B ’ sulfur odds are given as 7, which we take as intend 7:1, matching with the first entrance in table 1. Taking Player A ’ mho probability of winning as and Player B ’ randomness 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 mechanically generated by the Conway algorithm as shown in table 2. Taking the best odds for Player B with respect to Player A ‘s choice gives the results listed in table 1. Conway ‘s algorithm is identical herculean, in that it can give probabilities not only for sequences of length 3, but for those of any length, or even for sequences of unlike distance .
board 2 : The probabilities of winning for players A and B ( for sequences of distance 3 ) .
Applying a winning strategy to cards
In the precede sections we examined Penney ‘s Ante using heads and tails in a coin flip crippled. Steve Humble and I have been discussing how this might be applied to a more familiar context, such as a wag game .
There are 52 cards in a pack of cards, and the 26 black ( spades and clubs ) and 26 crimson ( hearts and diamonds ) cards can be used to substitute for the heads or tail 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 choose triples appears. The winning player takes the retrousse cards, having won that flimflam. The game continues with the rest of the idle cards, with players collecting tricks as their triples come up, until all the cards in the gang have been used. The achiever of the game is the actor that has won the most tricks .
A well randomize clique of cards The advantage of using cards lies in their ease of handling, and the fact that one does not need to keep path of the results. They can besides be well randomised. If all 26 bolshevik and black cards are used, then there is precisely a 1/2 prospect of choosing either color from the 52 sum cards. As cards are removed from the shuffled deck the probability of choosing either color will wobble around a half, but will never stray far for most of the game .
As an exemplar lashkaretaiba ‘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 whoremaster 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 flimflam. fortunately, playing the game with a hale pack of cards normally results in 79 tricks being played, which increases the odds of RRB winning. For exemplar, the probability of RRB winning a game with 7 tricks is
where the Ck are the k tricks (to win) out of the 7 tricks.
where theare the binomial numbers giving the number of ways of choosingtricks ( 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 polish. Playing the game using cards over 7–9 tricks, which is possible for all the possible matches using one gang 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 mint 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 pack of cards 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 teach via practical experiments. For more data on Dr Maths go to the Dr Maths web site 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 matter to 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 .
Leave a Comment