If scientific reasoning were limited to the logical processes of arithmetic, we should not get very far in our understanding of the physical world.
One might as well attempt to grasp the game of poker entirely by the use of the mathematics of probability.

- Vannevar Bush
 

The mathematics of card shuffling is not just of interest to inveterate gamblers.  It also has important applications in the sciences.

You are the dealer.  You know that the top five cards are the ace, king, queen, jack and ten of spades.  If you are playing poker with three other people, how can you deal these cards to yourself?

The most elegant way is to do two perfect shuffles.  A perfect shuffle - when the pack is cut exactly in half and the cards are then dropped one at a time from alternate sides until the two halves are interleaved evenly - is the crooked gambler's dream.  After one perfect shuffle, the five cards previously at the top of the deck will now be every second card; after two such shuffles, they will be every fourth card.

However, you must remember to do what magicians call "inshuffles".  That is, if you cut the cards and pick up the top half of the pack in your right hand, you must start dropping the cards from the right-hand side.  This way, the top card will become the second card, and then the fourth.  If you make a mistake and do "outshuffles", starting instead from the left-hand side, the top card will stay on top, and you will deal the royal flush to the person lucky enough to be sitting to your left.

Perfect shuffles are one way to manipulate cards: to move the ace of spades from the top card to the 13th takes two inshuffles followed by two outshuffles.  There is an intriguingly simple procedure for working out the necessary manipulations.  Write down the places by which you would like the ace to move - in this case, 12.  Then, write the number in its binary format (that is, using only 0s and 1s): for 12, this is 1100.  This tells you how to shuffle: inshuffles are represented by 1s, outshuffles by 0s.

Even better, after eight outshuffles in a row the pack returns to the order it started off in (it takes 52 inshuffles to achieve the same result).  Strangely, this rule only applies for a pack of 52 cards.  The cyclical behaviour of a pack of 48 cards (used for games such as bezique and pinochle) or of 104 cards is different.  Moreover, it cannot be predicted using any mathematical formula.  Although this sounds like a simple problem, it is in fact an example of a deeply puzzling question in number theory.

The number of outshuffles required to restore any pack of cards to its original order does obey a simple rule.  The problem is that one of the variables in the rule cannot be known in advance.  So the only way to work out the number of perfect shuffles needed to return a pack to its original order is to do them.  There is an exception: when the number of cards in a pack is exactly equal to two raised to the power of a whole number (that is, if the pack has 4, 8, 16, or 32 cards, and so on).  Then, the number of outshuffles is the same as the exponent: for a pack of four cards it takes two outshuffles, for a pack of 32 cards it takes five.

More generally, it turns out that the number of outshuffles needed to get a pack back to its starting point is the smallest power of two - call it x such that two raised to the power of x and then divided by a figure that is one less than the number of cards in the pack leaves a remainder of one.  For example, in the case of 52 cards, the number of outshuffles needed is eight (2⁸ equals 256, and 256 divided by 51 has a remainder of one).  But for all pack sizes that are not powers of two, x cannot be calculated, and the number of outshuffles required to return the cards to their original order cannot be worked out.

The behaviour of perfect shuffles is not just of interest to magicians and card sharps.  Engineers and physicists sometimes refer to "perfect-shuffle networks" - networks that look as if they are busily engaged in perfect shuffles.  For example, if a parallel computer network consists of an array of simple processors acting in tandem, the way that it manipulates numbers looks remarkably like a pack of cards being shuffled perfectly over and over again.

Mixing It

Fortunately for honest card players, few people are capable of doing even one perfect shuffle; perhaps only 30 people in the world can reliably do eight in under a minute (the sort of speed necessary for it not to be obvious that something peculiar is going on).  So when most people shuffle a deck, they mix up the cards.  But how long does it take before the deck is really mixed?

For mathematicians and statisticians, a pack of cards is randomly mixed when every card is equally likely to be at all positions in the deck.  (A pack of 52 cards has 52-factorial possible arrangements, or 52 multiplied by 51 multiplied by 50 ...and so on all the way down to one.  This is a large number: 8.065 times 10⁶⁷.)

According to Persi Diaconis, a magician-turned-mathematician at Harvard University (but currently visiting Cornell), shuffling with "riffle" shuffles - that is, cutting the pack and then dropping cards from each side, but not interleaving them perfectly - is highly effective at mixing up cards.  After seven shuffles, the pack is close to being random.  In contrast, shuffling overhand - that is, dropping little clumps of cards on to the back of the pack - is ridiculously ineffective.  The pack will not be random until the procedure has been repeated 2,500 times.

Moreover, Dr Diaconis (who can do eight perfect shuffles in a row) and his colleagues - Laurent Saloff-Coste, David Bayer, Ron Graham (who also works on the mathematics of juggling) and William Kantor - have recently discovered an even more bizarre phenomenon: in some systems, the switch to randomness is abrupt.  In other words, after six riffle shuffles, a pack is still visibly ordered.  But after the seventh, it suddenly becomes random.

The presence of this cut-off turns out to be important.  Card shuffling, when imperfect, is a good example of something called a "Markov chain".  This is a random process in which the future depends only on the present, not on the past.  For instance, what a shuffle does to a pack of cards depends only on the order they are in before that shuffle, not on how they got to be in that order.  Or think of a drunkard staggering about.  His next step depends only on where he is now, not on where he came from.

But at the start of a random process, it takes a while before a system actually becomes random.  When the drunkard first sets off from the pub, he is not immediately likely to be anywhere between the pub and his house: he will be close to the pub.  Likewise with card shuffling.  Buy a new pack of cards, and it obviously takes a bit of shuffling before the cards are mixed up.

With the advent of powerful computers, which make big random simulations much easier, Markov chains have become popular in fields from statistics to biology.  Most simulations start at some fixed position, but eventually reach an equilibrium state of randomness.  But it is often important to know how long this takes.  Otherwise, the results of the model may be affected by the state that the system started out in.  In the case of a pack of cards, without enough shuffles (particularly if shuffling overhand) the current order will still partly depend on the original one.

Mathematicians have long been able to predict how close a system is to being random after a large number of steps - for example, how likely the drunk is to be anywhere after he has taken lm steps, or how likely a pack of cards is to be mixed after 20,000 shuffles.  But this says nothing about how long it takes to become random from a fixed starting point.

This is where the cut-off comes in.  Dr Diaconis and his colleagues have worked out methods for identifying which systems have such sudden breaks - these can drastically speed up the approach to randomness - and for working out where they are.  Systems that do not have a cut-off - the drunkard's walk is one - will approach a state of randomness gradually.  Some of them can take a long time to do so.  For instance, if the space the drunkard is walking in is large, it will be a long time before he is equally likely to be anywhere within it.

Dr Diaconis argues that this information is crucial.  For the users of Markov models, it can prevent embarrassing errors.  For everybody else, perhaps it is just handy to know that seven imperfect riffle shuffles are enough to mix up a pack of cards.

Source: The Economist 12 October 1996

-------- Original Message --------
Subject: Suggestions
Date: 30 Dec 2005 11:53:06 -0000
This message was posted via the Feedback form.
Name: Bill L.
Email: havspace@yahoo.com

I found the 2 paragraphs (#7 and 8 perhaps) in the first article about determining the number of perfect outshuffles that will return a pack to its original order to be a bit misleading or at least confusing.  The first of the paragraphs starts with:

The number of outshuffles required to restore any pack of cards to its original order does obey a simple rule.  The problem is that one of the variables in the rule cannot be known in advance.

While I may have peculiar tendencies in my usage, I don't like saying "cannot be known in advance".  I, for example, DID know in advance that x=8 for a pack of 52 cards.  I'm not sure offhand how I would suggest re-wording it.  The next sentence, however, says:

So the only way to work out the number of perfect shuffles needed to return a pack to its original order is to do them.

Which is utterly absurd.  It's much easier to simulate the shuffles than do them, and far easier still to just calculate y = 2^x modulo (c-1) (where c = # of cards in the deck) for x = 1,2,3,... until you find that x that makes y=1.  I would change that sentence to something like:

So the only way to work out ... original order is through trial and error

(if that is indeed the case).

I like your description of the math involved, except for the last sentence.  It has been a while since I was a math major, so maybe saying "x cannot be calculated" is appropriate, but I would be inclined to say something like "x cannot be easily calculated" or "there is no known formula that will calculate x" (and are you confident there has been no development in number theory along these lines?).  Some mention of "brute force methods" (such as the one I specify below) might be worthwhile.

Concluding by saying "the number of outshuffles ... cannot be worked out" is what really prompted me to respond because the math you supplied virtually defines an algorithm for working out what x will be.

c = 52 (or whatever)
If Mod(C,2) = 1 return

* perfect outshuffles only work on packs with an even number of cards. *

z = c - 1
x = 1, y = 0
while (y != 1){
y = Mod(2^x,z)
if (y = 1) return x
x = x+1
}

I suspect, but don't know if there is a proof that this algorithm is guaranteed to terminate for all even c.  Placing an upper bound on the size of x could be an interesting problem.

At any rate, rather than ending with "cannot be worked out" you could just leave it with "no known formula" or some mention of brute force (feel free to use or adapt the obvious algorithm above).

The site looks pretty interesting (how can I fail to like something that mentions Diaconis, the Trefethen's and tons of other random and non random subjects ;), and sorry for my ramblings ... I think really need to return to grad school.

Bill L.

Shuffling: What's the Deal?

by Philip Ball

How many times do you really need to shuffle that deck of cards to rule out any chance of dodgy dealing?

Two mathematicians hit the headlines in 1990 when they claimed that it took seven shuffles to make a pack of cards fully random, with no vestige of its original card order.  Now comes a challenge to that claim.  Five shuffles will almost do the job of randomisation, and six will make it certain, according to a paper in the Proceedings of the Royal Society*.

It all depends on how you define "random", say Nick Trefethen and Lloyd Trefethen, respectively of Oxford University, UK, and Tufts University in Massachusetts in the US.

The magic number of seven shuffles was proposed by David Bayer and Persi Diaconis in the USA, who considered how shuffling affected a quantity called the "total variation norm."  This is a complicated measure of how effectively an ingenious gambler could be expected to win bets that the arrangement of cards in the deck was not completely arbitrary.

Bayer and Diaconis chose to define randomness in this way because they were interested in how shuffling might affect play in casinos.  Some professional card players will go to any lengths to exploit an element of non-randomness in a card deck.  Most casino dealers shuffle between two and four times - which, according to Bayer and Diaconis, was nowhere near enough to lose all trace of the starting configuration of the pack.  In fact, they claimed that there is virtually no true randomisation, as they defined it, until the 5th shuffle.  Only after the 7th, they said, does their measure of "orderliness" of the deck fall below half the initial value - enough to consider the pack well mixed.

Diaconis, himself a card magician, realised that astute card players could capitalise on this.  He said that in his experience, shuffling seven times was almost unheard of in casinos.  And he once spotted how bridge players in a New York club could anticipate the order of a deck shuffled four times between each hand.

But the Trefethens say that the total variation norm, while a respectable measure of randomness, is not the only way to define it.  They have instead considered a pack of cards as a package of information - a definition that stems from early work in telecommunications.  If one knows the complete order of the pack, one has all the relevant information about it.  If the pack is then shuffled until it is truly random, this information is reduced to zero - one has no idea where any particular card is.  But how quickly does this information fall to zero?

The researchers simulated shuffling on a computer, using the same idealised kind of riffle shuffle as Bayer and Diaconis, in which the pack is divided roughly in two and the cards are dropped on top of one another more or less alternately from each half.  They found that, according to their definition of the "information" remaining about the order of the cards, the randomness accumulates steadily right from the first shuffle, and is virtually complete by the 6th.  Even four shuffles does a fair job of reducing the "information content" of the pack.

So which answer is correct: seven shuffles or six, or maybe just five?  Even experts will dispute the significance of the two different measures of "randomness" in the pack.  As far as card sharps are concerned, the differences will probably depend on what game one is playing.

But it would be an extraordinary gambler indeed who could make money on the difference between 6 and 7 shuffles.

References

*Trefethen, L N & Trefethen, L M "How Many Shuffles to Randomise a Deck of Cards?" Proceedings of the Royal Society London A 456, 2561 - 2568 (2000)

Source: nature.com 4 October 2000 © Nature News Service / Macmillan Magazines Ltd 2001

Is It Luck of the Draw or Skill?

Case Western Reserve University Psychologist Places His Bets on Skill

Is it luck of the draw in poker?  No, says Michael DeDonno, a doctoral student from Case Western Reserve University.  He suggests putting your bets on skills over luck when playing the card game.  DeDonno's findings from two poker-related studies with college students have implications for the gaming industry, and possibly even legal cases that challenge the theory of luck over skills.  According to DeDonno, the person who takes home the winnings is likely to pay higher taxes when money is considered earned by luck.

His article, "Poker is a Skill," written with Douglas Detterman, Case Western Reserve psychologist, caught the attention of the journal, Gaming Law Review, which has been examining this luck-skill debate and recently published psychologists' findings.  "This article provides empirical evidence that it is skill and not luck," concluded DeDonno from his two studies.

In the first study, DeDonno had 41 college students play 8 games, totaling 200 hands, of Turbo Texas Hold'em, a computerised simulation of 10-player Hold'em poker.  The game consists of being dealt 2 cards in the first round.  The player must decide whether to play or quit based on the hand.  If the person decides to play, then 3 cards are dealt for the community pot.  Again, the player has to decide whether to play or stop.  The player must also consider the betting patterns of the other players in making a decision in moving to the next round.  If continuing, then the player sees another card and has to decide again to bet or lay down the cards.  This is repeated until there are 5 cards on the table.

Overall most of the students had little experience playing poker, said DeDonno.  Half of the students in the first group were given charts that ranked the 2-card combinations from best to the worst and also learned that professional poker players typically play about 15% of the hands dealt them.  The other group was given background on the history of poker with no strategies.  He found that students given some strategies to make decisions did better than those without the strategies.  When starting the study, almost 2/3 of the students (64%) felt that winning at poker was 50% luck.

"If it had been pure luck in winning, then the strategies would not have made a difference for the two groups," said DeDonno.

To statistically verify the results from the first study, he conducted a second study, but had students play 720 hands.  Again the group was divided into those provided with strategies and those with just a history of playing poker.  While all students improved their playing with practice over the large number of hands, the group given strategies continued to do better than those without the added information.  He also found that students reduced the average number of hands played at the beginning (27) to 15 hands after given strategies, which improved their games and validated that "fewer hands does result in improved performance."

DeDonno's research evolved from his interest in playing poker.  He wanted to determine if there was a correlation between intelligence and the ability to play the game.  But the focus shifted to the luck-skill issue.  According to DeDonno, using poker strategies has some real life applications in such areas as investments and buying a home where partial information is available.  He also discovered that the poker simulation has applications in psychological testing for decision making and risk taking.

But in DeDonno's final analysis, skill wins out in playing poker.

Source: blog.case.edu 18 March 2008

Poker Skills Could Sway Gaming Laws

by Celeste Biever

Is poker a game of skill or luck?  For regular players that's a no-brainer, but showing that skill wins out has proven surprisingly difficult for mathematicians.  Now two studies that tapped the vast amounts of data available from online casinos have provided some of the best evidence yet that poker is skill-based.  Many hope that the results will help to roll back laws and court decisions that consider poker gambling, and therefore illegal in certain contexts.

Most players insist that poker is predominantly skill.  "I depended solely on that skill for my food and rent," says Darse Billings, a former professional player who co-founded the Computer Poker Research Group at the University of Alberta in Edmonton, Canada.  In many jurisdictions, however, poker websites and organised games are heavily regulated or even banned under gambling laws, partly because chance is considered the dominant factor.

Previous attempts to quantify the relationship between skill and chance have involved building theoretical models or playing software bots against each other.  However, Ingo Fiedler and Jan-Philipp Rock at the University of Hamburg's Institute of Law and Economics in Germany argue that these methods fail to reflect real games, and this may explain why some courts and lawmakers have yet to be swayed by them.  So over three months, the pair recorded the outcomes of 55,000 online players playing millions of hands of poker's most popular variant, "no-limit Texas hold 'em".  They reasoned that if skill dominated, this would eventually show itself over many hands, so they chose two factors to define this threshold.  Firstly, they measured how much each player's winnings and losses fluctuated: the higher this variance, the greater the role of chance.  Secondly, they measured the average value of a player's winnings or losses: highly skilled or terrible players would do noticeably better or worse than would be expected by chance alone.

Based on these factors, they found that the threshold at which the effects of skill start to dominate over chance is typically about 1000 hands, equivalent to about 33 hours of playing in person or 13 hours online, where the rate of play is brisker.  So although chance plays a role, they suggest that because most players easily play this many hands in a lifetime, poker is more a game of skill (Gaming Law Review and Economics, DOI: 10.1089/glre.2008.13106).  "Our results should have greater impact on the legislators than the results of other studies; they refer to reality," says Fiedler.

However, Sean McCulloch, a computer scientist at Ohio Wesleyan University in Delaware, says the results may fail to sway a judge or jury.  "If you want to use a mathematical argument as the basis for legislation or court decisions, it has to be easy to explain, easy to follow and intuitive," he says.  McCulloch used an alternative method to explore skill and chance in poker, also based on real games.  Together with Paco Hope of the software consultancy Cigital of Washington DC, he looked at 103 million hands of Texas hold 'em played at the PokerStars online site and calculated how many were won as the result of a "showdown" - in which players win thanks to their cards beating their opponents' cards - versus those that were won because all the other players folded.  They argue that the latter hands must be pure skill, because no one shows their cards.  Their analysis, released on 27 March, revealed that 76% of games did not end in a showdown, suggesting that skill is the dominant factor.

John Pappas of the Poker Players Alliance (PPA) in Washington DC says both studies are badly needed to help properly define the law.  In many US states, judges and juries use a so-called "predominance test" to gauge skill and chance, based on the opinions of expert witnesses.  Although courts in Pennsylvania, Colorado and South Carolina have all ruled this year that poker is a game of skill, not all courts do.  "It would not be wise for any of us to rest on our laurels," Pappas says.  The PPA expects the Cigital study will now be used as evidence to fight appeals against court rulings that decided poker is a skill game.

However, Preston Oade of law firm Holme Roberts and Owen in Denver, Colorado, who worked on a separate poker case in Colorado, cautions that the studies still may not persuade juries, as this is a "moral, political and social issue", as well as a mathematical one.  Pappas hopes the studies will help to persuade the US Congress to grant poker an exemption from the Unlawful Internet Gambling Enforcement Act, due to come into force in December 2009.  The act will make it illegal in some states for banks to process transactions from gambling websites.

Source: newscientist.com New Scientist issue 2702 4 April 2009

Clicking the "Next" button below will take you to Tells: The Fine Art of Losing at Poker.  Clicking the "Up" button takes you to the Table of Contents for this section where you can view thumbnails of Andrew Jones' curious deck of art cards.