“Higher or Lower” – Easy card game? Part I
I was recently roped into joining some friends for a pub quiz. I hate pub quizzes. For a start, I don’t watch soaps or football or take any interest in divorcing celebrities. The sum total of my contribution is usually a question about the periodic table and another about some obscure ’90′s one-hit wonder.
At the end of this particular quiz there was a competition to win a pot of dosh. Those optimistic enough to enter first had to be lucky enough to have their number drawn from a hat, and then attempt to win the ominous game of Higher or Lower, or “Play Your Cards Right” as it is sometimes known, via a crudely written flash program running on the host’s laptop. If you win the game, you win the cash. Easy? Apparently not. Two players failed in succession and then the host declared that the contents of the pot would roll over to next week. Almost everyone in the pub had just lost a quid. Would anyone ever win the money? I didn’t know, but I was alarmed and it was my duty to discover the probability of winning this game.
Rules of Higher or Lower
A normal deck of 52 playing cards is shuffled and 9 cards are placed face down. The first card is turned over. The player must guess whether the next card’s value will be higher or lower than the previous card’s value. Ace is low, i.e. represents the value 1.
If a value is repeated immediately, e.g. two 9′s in a row, it is neither higher nor lower and the player loses.
To win, the player must make 8 correct guesses in a row, i.e. to turn all the cards over having guessed each one correctly - higher or lower.
First we must establish a strategy for playing this game; that is, a set of rules that you must follow depending on what cards come up. In the example pictured above, the first card is an ace, which has value 1. This is a lucky starting situation. You’d definitely say “higher”, because there are no cards with value less than 1, and you’d only lose if you were unlucky enough for the second card to be another ace. If the starting card had been a 2, you’d still say “higher” because there are only 7 cards out of the remaining 51 which would make you lose: the four aces and the remaining three 2′s. Similarly, if the first card had been a Queen, you’d say “lower” because it’s much more likely to be lower than higher.
The strategy, then, is to choose the direction that has the greater number of possibilities. (There is an occasional situation, often with a 7, where there are equal number of cards higher and lower; in this case it doesn’t matter which direction you choose, but for consistency we’ll opt to go with “higher” when this situation arises.)
With this strategy all players are equally skilled, and the problem boils down to working out how many of the permutations, out of all the possible permutations of 9 cards from a pack of 52, are winning ones. (A permutation is an ordered set of cards.) But the numbers are still astronomical; there are 52!/(52-9)! permutations of 9 cards from a pack of 52. That’s over a million billion permutations!
In order to understand how the numbers work here, it is, as always, important to consider a simpler version of the problem. Therefore in this post, instead of using a whole pack, we’ll just use one suit.
Single-Suit Higher or Lower
This version is much simpler because you can never have a repeated value, and that makes a big difference! We’re now only dealing with 13!/(13-9)!, or just shy of 260 million, permutations of 9 cards. Incredibly, this is actually a manageable number.
The first thing to recognise is that the first card could be any of the 13 possible values. There’s a 1/13 chance of it being any particular one of them. We will try to find a formula for the probability of correctly guessing the second card, then find a formula for correctly guessing the second AND third cards, and finally a formula for correctly guessing the second, third AND fourth cards. This will give us enough information to identify all the patterns and allow us to confidently predict the formula for the probability for making 8 out of 8 correct guesses.
- If the first card is the ace, you’re in luck. You’d say “higher” with complete confidence that whatever the next card is, it’ll be higher than ace.
- If the first card is 2, you’d still say “higher”, but only 11 out of the 12 remaining cards are higher than 2.
- If the first card is 3, you’d say “higher”, but only 10 out of the remaining 12 cards are higher than 2.
—- you should be seeing a pattern develop —-
- Similarly, if the first card is the King, you’d say “lower” with complete confidence.
- If the first card is the Queen, you’d say “lower”, but only 11 out of the remaining 12 cards are lower than Queen.
—- what happens in the middle? —-
- If the first card is 6, you’d say higher because 7/12 cards are higher.
- If the first card is 7, you could say either higher or lower because there are 6/12 cards either way (we’ll go with “higher”).
- If the first card is 8, you’d say lower because 7/12 cards are lower.
So there’s this “bouncing” of probabilities occurring - as the value of the first card increases from 1, the probability of success on the second card decreases from 12/12 to 11/12 to 10/12, etc. until it reaches 6/12, then it stops decreasing and starts increasing up to 12/12 again:
Fortunately there is an operator that allows us to describe this behaviour: we call it the “modulus” or “absolute value”, which outputs the SIZE of a value - effectively its distance from zero – and is denoted by placing the value in |vertical brackets|. In plain English, this means that if the value is positive we don’t touch it, but if it’s negative we simply take the minus sign away, for example, |2|=2, and |-2|=2. It means we can plot graphs with symmetry like in the above graph. This symmetry will be prevalent throughout the investigation – you should have a think about why this might be so. Incidentally, the formula for the above graph is (1/12)*(6+|7-c1|).
So, because when we get invited up to play Higher or Lower we don’t know what the first card is going to be, we need to add up these 13 probabilities but multiply them all by their chance of occurring, i.e. 1/13. Using summation notation, this is described thus:
(This “Sigma” notation means that the parameter c1 starts off equal to 1 and is put through the formula that appears after the sigma sign. Then c1 is set equal to 2 and is put through the formula and added to the previous value. c1 goes on to take every integer value from 1 to 13, with all the results being added up in a summation. See Further Reading for more info on Summations and Sigma Notation.)
Now let’s look at working out P(success on c3).
If we assume c1=1 and that we said “higher” (as our strategy dictates), c2 could take any value from 2 to king (13). The probability of success on c3 depends on what value c2 takes.
- c2 can’t equal 1.
- If c2=2, we’d say “higher” with complete confidence.
- If c2=3, we’d say “higher” but only 10/11 of the remaining cards are higher than 3.
- If c2=4, we’d say “higher” but only 9/11 of the remaining cards are higher than 4.
—- etc —-
- Similarly, if c2=King, you’d say “lower” with complete confidence.
—- etc —-
- And in the middle, the probabilities “bounce” again because if c2=7 there are 6/11 cards higher and if c2=8 there are 6/11 cards lower.
We would perform the same mini-analysis for c1=2, c1=3, etc, but I won’t bore you with figures any longer. Here’s a pretty graph showing all the info we need to know to advance:
And the same graph, viewed directly from above, clearly shows how the symmetry operates at this level of complexity:
Remember that Formula 1, for the probability of being successful on c2, involved a summation of all the different possibilities that could occur (13 different possibilities or “permutations” of c1). At the next level of complexity, for each of the 13 possibilities in the first instance there are 12 new possibilities. So there are 13×12 permutations of c1 and c2, and each of those yields its own probability for the player being successful on c3 (although some of those probabilities are zero and not shown in the above graphs). Also, spot that the violet line for c1=7 does not appear to have a twin: that’s because it is its own twin - it could be deleted and redrawn on the other side without affecting the ultimate probability – the real difference being that, purely for consistency, as mentioned in the strategy above, if c1 were 7 we would say “higher” even though it’s 50-50 either way.
Now let’s keep the momentum going. Compare Formula 2, for the probability of being successful on c3, with Formula 1. Using nested summations like this effectively says “set c1=1 and then add up the probabilities for all possible values of c2; then set c1=2 and do the same, etc, up to and including c1=13.”
(Note that the lower limit of the nested summation must follow the same symmetry rules as the summation formula. Also, see how values in the summed formula have changed by 0.5; that’s to accommodate the fact that the “bouncing” now occurs at 6.5 or 7.5, instead of 7 where it occurred in Formula 1.)
Now, let’s look at working out P(success on c4)
Phew!! Only one more level of complexity to go! But actually we’ve done the hard bit; there are several patterns emerging already, and with some intelligent analysis we can identify them all:
- Formula 3 is bound to have 3 nested summations.
- The parent summation will sum for c1 from 1 to 13.
- The first nested summation will sum for c2 from 8-|c1-7| to 13.
- There will be an extra 1/10 to include in the formula (when we’re looking at c4 there are 10 unknown cards left).
To formulate P(succecss on c4), we just need to have a think about:
- The formula for the lower limit of the c3 summation;
- The values in the summed formula.
1. (HARD!) The lowest value that c2 can have is 2, which is when c1=1 or c1=13. That’s not to say that the second card can’t be an ace – it can – but each time one card is used up, there are fewer remaining to sum over, so the point of symmetry in the lower limit must move to accommodate. Don’t dwell on this; I spent a week figuring it out!
2. (SLIGHTLY EASIER!) The “bouncing” now occurs at 6 or 8.
Final formula for P(success on c9)
So we’ve done it! We just need to extrapolate from Formulae 1-3. We simply follow all the patterns we’ve identified, and voila!
This looks absurdly complicated, and it is! This formula effectively separates all the winning permutations from over 260 million possible permutations. We should be proud at having arrived at something this complicated with our puny Earthling brains.
Computation & Results
Programming Formula 4 directly into a computer is chronocide. A rough calculation suggested my computer would take over a 1000 years to solve it, and that’s because the computer would have to remember hundreds of millions of values at the same time; extremely RAM intensive and frankly unpractical. (Although the theoretical quantum computer would have no trouble because it could calculate all possibilities at the same time.)
A much better way to ask a present-day computer to calculate a value for Formula 4 is to reorganise it into nested “do loops”. Then the computer simply looks at each winning permutation in turn and adds up their probabilities:
And it turns out that the probability of winning Single-Suit Higher or Lower is just 10.6%.
That means you’ve only about a 1-in-9.4 chance of winning. In fact we can use the ideas from the 1-in-10 Gay Problem posts to go as far as saying that if you played 10 games of Single-Suit Higher or Lower, you’d only be around 67% (roughly two-thirds) likely to win on at least one occasion.
So don’t pay a quid to enter this competition unless you know for a fact you will selected to have a go at it, and that there is at least a tenner up for grabs as the prize. If 15 people entered this competition, and only one person would be picked to play, you’d first need to beat 1/15 odds at being picked, then 1-in-9.4 odds of winning the game. That’s a paltry 1-in-141 chance of winning! (But note that if there were more than £141 in the pot it would actually still be worth entering.)
Here is a graph showing the probability of reaching each successive card. The 10.6% is at the bottom, i.e. for reaching the 9th card and winning the game.
It’s interesting to note that the probability of reaching a particular card once the previous card has already been reached maintains a fairly constant value of about 75%, but note this represents only an “average” probability of success on the next card; once you know which cards have already been revealed this figure will vary.
In the next post we will look at the full-blown 4-suit game and see how the probability of winning is even smaller!
1. Summations & Sigma Notation – Wikipedia http://en.wikipedia.org/wiki/Summation