Shuffle
Encyclopedia
Shuffling is a procedure used to randomize
a deck of playing card
s to provide an element of chance in card game
s. Shuffling is often followed by a cut
, to help ensure that the shuffler has not manipulated the outcome.
A common shuffling technique is called the riffle or dovetail shuffle, in which half of the deck is held in each hand with the thumbs inward, then cards are released by the thumbs so that they fall to the table interleaved. Many also lift the cards up after a riffle, forming what is called a bridge which puts the cards back into place. This can also be done by placing the halves flat on the table with their rear corners touching, then lifting the back edges with the thumbs while pushing the halves together. While this method is more difficult, it is often used in casino
s because it minimizes the risk of exposing cards during the shuffle. There are two types of perfect riffle shuffles: if the top card moves to be 2nd from the top then it is an in shuffle
, otherwise it is known as an out shuffle
(which preserves both the top and bottom cards).
Riffle shuffling does, however, carry a risk of damaging cards from excessive bending. Casinos often replace their playing cards to prevent cheating from players that detect deformations in the cards. However, collectible card game
cards are considerably less replaceable than playing cards, and CCG cards can be damaged from riffle shuffling, even when protected with card sleeves.
The now-often-used name Corgi originated in Yorkshire, England. It has spread and is used in many parts of the UK, and often heard in international poker rooms or tournaments such as the WSOP
or EPT
. It is quite common in casino poker rooms for dealers to use this method upon introducing a brand new deck, which are packaged in ranked order by suits, before shuffling it by some other means (i.e., a riffle shuffle or shuffling machine).
, would be a deck with the cards in the following order: 
.
For a deck of given size, the number of Mongean shuffles that it takes to return a deck to starting position, is known . Twelve perfect Mongean shuffles restore a 52-card deck.
The faro shuffle
is performed by cutting the deck into two, preferably equal, packs in both hands as follows (right-handed):
The cards are held from above in the right and from below in the left hand. Separation of the deck is done simply lifting up half the cards with the right hand thumb slightly and pushing the left hand's packet forward away from the right hand. The two packets are often crossed and slammed into each other as to align them. They are then pushed together by the short sides and bent (either up or down). The cards then alternately fall into each other, much like a zipper
. A flourish can be added by springing the packets together by applying pressure and bending them from above. The faro is a controlled shuffle which does not randomize a deck when performed properly.
A perfect faro shuffle, where the cards are perfectly alternated, is considered one of the most difficult sleights by card magicians, simply because it requires the shuffler to be able to cut the deck into two equal packets and apply just the right amount of pressure when pushing the cards into each other. Performing eight perfect faro shuffles in a row restores the order of the deck to the original order only if there are 52 cards in the deck and if the original top and bottom cards remain in their positions (1st and 52nd) during the eight shuffles. If the top and bottom cards are weaved in during each shuffle, it takes 52 shuffles to return the deck back into original order (or 26 shuffles to reverse the order).
s employ automatic shuffling machine
s. They also save time that would otherwise be spent shuffling, allowing several more hands per hour to be played and increasing the profitability of the table. These machines are also used to lessen repetitive motion stress injuries to a dealer. Note that the shuffling machines have to be carefully designed, as they can generate biased shuffles otherwise: the most recent shuffling machines are computer-controlled, though they have not yet fully been integrated into gaming.
(expressed in shorthand as 52!
) possible orderings of the cards in a 52-card deck. This is approximately 8 possible orderings. The magnitude of this number means that it is exceedingly improbable that two randomly selected, truly randomized decks, will ever, in the history of cards, be the same. However, while the exact sequence of all cards in a randomized deck is unpredictable, it may be possible to make some probabilistic predictions about a deck that is not sufficiently randomized.
A famous paper by mathematician
and magician Persi Diaconis
and mathematician Dave Bayer
on the number of shuffles needed to randomize a deck concluded that the deck did not start to become random until five good riffle shuffles, and was truly random after seven, in the precise sense of variation distance described in Markov chain mixing time
; of course, you would need more shuffles if your shuffling technique is poor. Recently, the work of Trefethen et al. has questioned some of Diaconis' results, concluding that six shuffles are enough. The difference hinges on how each measured the randomness of the deck. Diaconis used a very sensitive test of randomness, and therefore needed to shuffle more. Even more sensitive measures exist and the question of what measure is best for specific card games is still open. Diaconis released a response indicating that you only need four shuffles for un-suited games such as blackjack
.
On the other hand variation distance may be too forgiving a measure and seven riffle shuffles may be many too few. For example, seven shuffles of a new deck leaves an 81% probability of winning New Age Solitaire where the probability is 50% with a uniform random deck (Mann, especially section 10).
One sensitive test for randomness uses a standard deck without the joker
s divided into suits with two suits in ascending order from ace to king, and the other two suits in reverse. (Many decks already come ordered this way when new.) After shuffling, the measure of randomness is the number of rising sequences that are left in each suit.
In practice the number of shuffles that you need depends both on how good you are at shuffling, and how good the people playing are at noticing and using non-randomness. Two to four shuffles is good enough for casual play. But in club play, good bridge players take advantage of non-randomness after four shuffles, and top blackjack
players supposedly track aces through the deck; this is known as "ace tracking", or more generally, as "shuffle tracking".
of the cards. There are two basic algorithms for doing this, both popularized by Donald Knuth
.
The first is simply to assign a random number to each card, and then to sort the cards in order of their random numbers. This will generate a random permutation, unless any of the random numbers generated are the same as any others (i.e. pairs, triplets etc). This can be eliminated either assigning new random numbers to these cases, or reduced to an arbitrarily low probability by choosing a sufficiently wide range of random number choices. If using efficient sorting such as mergesort or heapsort
, this is an O
(n log n) algorithm.
The second, generally known as the Knuth shuffle or Fisher–Yates shuffle, is a linear-time algorithm which involves moving through the pack from top to bottom, swapping each card in turn with another card from a random position in the part of the pack that has not yet been passed through (including itself). Providing that the random numbers are unbiased, this will always generate a random permutation.
, where the randomness of the shuffling of packs of simulated cards for online card games is crucial. For this reason, many online gambling sites provide descriptions of their shuffling algorithms and the sources of randomness used to drive these algorithms, with some gambling sites also providing auditors' reports of the performance of their systems.
Mathematics of shuffling:
Real World (Historical) Application:
Randomization
Randomization is the process of making something random; this means:* Generating a random permutation of a sequence .* Selecting a random sample of a population ....
a deck of playing card
Playing card
A playing card is a piece of specially prepared heavy paper, thin cardboard, plastic-coated paper, cotton-paper blend, or thin plastic, marked with distinguishing motifs and used as one of a set for playing card games...
s to provide an element of chance in card game
Card game
A card game is any game using playing cards as the primary device with which the game is played, be they traditional or game-specific. Countless card games exist, including families of related games...
s. Shuffling is often followed by a cut
Cut (cards)
After a deck of cards is shuffled by the dealer, it is often given to a player other than the one who performed the shuffle for a procedure called a cut.- Procedure :...
, to help ensure that the shuffler has not manipulated the outcome.
Shuffling techniques
Several techniques are used to shuffle a deck of cards. Some techniques are easy to learn while others achieve better randomization or are better suited to special decks.Riffle
Casino
In modern English, a casino is a facility which houses and accommodates certain types of gambling activities. Casinos are most commonly built near or combined with hotels, restaurants, retail shopping, cruise ships or other tourist attractions...
s because it minimizes the risk of exposing cards during the shuffle. There are two types of perfect riffle shuffles: if the top card moves to be 2nd from the top then it is an in shuffle
In shuffle
An in shuffle is a type of perfect shuffle done in two steps:#Split the cards exactly in half and then#Interweave each half of the deck such that every-other card came from the same half of the deck....
, otherwise it is known as an out shuffle
Out shuffle
An out shuffle is a type of perfect shuffle done in two steps:#Split the cards exactly in half and then#Interweave each half of the deck such that every-other card came from the same half of the deck....
(which preserves both the top and bottom cards).
Riffle shuffling does, however, carry a risk of damaging cards from excessive bending. Casinos often replace their playing cards to prevent cheating from players that detect deformations in the cards. However, collectible card game
Collectible card game
thumb|Players and their decksA collectible card game , also called a trading card game or customizable card game, is a game played using specially designed sets of playing cards...
cards are considerably less replaceable than playing cards, and CCG cards can be damaged from riffle shuffling, even when protected with card sleeves.
Stripping or overhand
Another procedure is called stripping, overhand, or slide shuffle, where small groups of cards are removed from the top of a deck and placed in the opposite hand (or just assembled on the table) in reverse order.Hindu shuffle
Also known as "Kattar" or "Kenchi" (Hindi for scissor). The deck is held face down, with the middle finger on one long edge and the thumb on the other on the bottom half of the deck. The other hand draws off a packet from the top of the deck. This packet is allowed to drop into the palm. The maneuver is repeated over and over, with newly drawn packets dropping onto previous ones, until the deck is all in the second hand. Hindu shuffle differs from stripping in that all the action is in the hand taking the cards, whereas in stripping, the action is performed by the hand with the original deck, giving the cards to the resulting pile. This is the most common shuffling technique in Asia and other parts of the world, while the overhand shuffle is primarily used in Western countries.Pile shuffle
Cards are simply dealt out into a number of piles, then the piles are stacked on top of each other. This ensures that cards that were next to each other are now separated. The pile shuffle does not provide a good randomization of the cards (but this can be enormously improved by dealing to the piles in a different order each circuit). It is sometimes used in collectible card games where other forms of shuffling might damage rare cards.Corgi, Chemmy, Irish or Wash shuffle
Also known as the scramble, beginner shuffle, or washing the cards, this involves simply spreading the cards out face down, and sliding them around and over each other with one's hands. Then the cards are moved into one pile so that they begin to intertwine and are then arranged back into a stack. This method is useful for beginners and small children or if one is inept at shuffling cards. However, the beginner shuffle requires a large surface for spreading out the cards and takes longer than the other methods.The now-often-used name Corgi originated in Yorkshire, England. It has spread and is used in many parts of the UK, and often heard in international poker rooms or tournaments such as the WSOP
World Series of Poker
The World Series of Poker is a world-renowned series of poker tournaments held annually in Las Vegas and, since 2005, sponsored by Harrah's Entertainment...
or EPT
European Poker Tour
The Pokerstars European Poker Tour is a series of poker tournaments similar to those in the World Poker Tour , created by John Duthie, winner of the inaugural Poker Million tournament. It began in 2004 as part of the worldwide explosion in Texas Hold 'em popularity...
. It is quite common in casino poker rooms for dealers to use this method upon introducing a brand new deck, which are packaged in ranked order by suits, before shuffling it by some other means (i.e., a riffle shuffle or shuffling machine).
Mongean shuffle
The Mongean shuffle, or Monge's shuffle, is performed as follows (by a right-handed person): Start with the unshuffled deck in the left hand and transfer the top card to the right. Then repeatedly take the top card from the left hand and transfer it to the right, putting the second card at the top of the new deck, the third at the bottom, the fourth at the top, the fifth at the bottom, etc. The result, if one started with cards numbered consecutively, would be a deck with the cards in the following order: .For a deck of given size, the number of Mongean shuffles that it takes to return a deck to starting position, is known . Twelve perfect Mongean shuffles restore a 52-card deck.
Weave and Faro shuffles
Weaving is the procedure of pushing the ends of two halves of a deck against each other in such a way that they naturally intertwine. Sometimes the deck is split into equal halves of 26 cards which are then pushed together in a certain way so as to make them perfectly interweave. This is known as a Faro Shuffle.The faro shuffle
Faro shuffle
The faro shuffle is a method of shuffling playing cards.In a perfect shuffle or perfect faro shuffle, the deck is split into equal halves of 26 cards which are then pushed together in a certain way so as to make them perfectly interweave....
is performed by cutting the deck into two, preferably equal, packs in both hands as follows (right-handed):
The cards are held from above in the right and from below in the left hand. Separation of the deck is done simply lifting up half the cards with the right hand thumb slightly and pushing the left hand's packet forward away from the right hand. The two packets are often crossed and slammed into each other as to align them. They are then pushed together by the short sides and bent (either up or down). The cards then alternately fall into each other, much like a zipper
Zipper
A zipper is a commonly used device for temporarily joining two edges of fabric...
. A flourish can be added by springing the packets together by applying pressure and bending them from above. The faro is a controlled shuffle which does not randomize a deck when performed properly.
A perfect faro shuffle, where the cards are perfectly alternated, is considered one of the most difficult sleights by card magicians, simply because it requires the shuffler to be able to cut the deck into two equal packets and apply just the right amount of pressure when pushing the cards into each other. Performing eight perfect faro shuffles in a row restores the order of the deck to the original order only if there are 52 cards in the deck and if the original top and bottom cards remain in their positions (1st and 52nd) during the eight shuffles. If the top and bottom cards are weaved in during each shuffle, it takes 52 shuffles to return the deck back into original order (or 26 shuffles to reverse the order).
Shuffling machines
Because standard shuffling techniques are seen as weak, and in order to avoid "inside jobs" where employees collaborate with gamblers by performing inadequate shuffles, many casinoCasino
In modern English, a casino is a facility which houses and accommodates certain types of gambling activities. Casinos are most commonly built near or combined with hotels, restaurants, retail shopping, cruise ships or other tourist attractions...
s employ automatic shuffling machine
Shuffling machine
A shuffling machine is a machine for randomly shuffling packs of playing cards.Because standard shuffling techniques are seen as weak, and in order to avoid "inside jobs" where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines to...
s. They also save time that would otherwise be spent shuffling, allowing several more hands per hour to be played and increasing the profitability of the table. These machines are also used to lessen repetitive motion stress injuries to a dealer. Note that the shuffling machines have to be carefully designed, as they can generate biased shuffles otherwise: the most recent shuffling machines are computer-controlled, though they have not yet fully been integrated into gaming.
Randomization
There are exactly 52 factorialFactorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
(expressed in shorthand as 52!
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
) possible orderings of the cards in a 52-card deck. This is approximately 8 possible orderings. The magnitude of this number means that it is exceedingly improbable that two randomly selected, truly randomized decks, will ever, in the history of cards, be the same. However, while the exact sequence of all cards in a randomized deck is unpredictable, it may be possible to make some probabilistic predictions about a deck that is not sufficiently randomized.
A famous paper by mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and magician Persi Diaconis
Persi Diaconis
Persi Warren Diaconis is an American mathematician and former professional magician. He is the Mary V. Sunseri Professor of Statistics and Mathematics at Stanford University....
and mathematician Dave Bayer
Dave Bayer
Dave Bayer is an American mathematician. He is currently a professor of mathematics at Barnard College, Columbia University. He was math consultant for the film A Beautiful Mind, and also acted in it as one of the "Pen Ceremony" professors. He is also one of few people to have both an Erdős number...
on the number of shuffles needed to randomize a deck concluded that the deck did not start to become random until five good riffle shuffles, and was truly random after seven, in the precise sense of variation distance described in Markov chain mixing time
Markov chain mixing time
In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution.More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has a unique stationary distribution π and,...
; of course, you would need more shuffles if your shuffling technique is poor. Recently, the work of Trefethen et al. has questioned some of Diaconis' results, concluding that six shuffles are enough. The difference hinges on how each measured the randomness of the deck. Diaconis used a very sensitive test of randomness, and therefore needed to shuffle more. Even more sensitive measures exist and the question of what measure is best for specific card games is still open. Diaconis released a response indicating that you only need four shuffles for un-suited games such as blackjack
Blackjack
Blackjack, also known as Twenty-one or Vingt-et-un , is the most widely played casino banking game in the world...
.
On the other hand variation distance may be too forgiving a measure and seven riffle shuffles may be many too few. For example, seven shuffles of a new deck leaves an 81% probability of winning New Age Solitaire where the probability is 50% with a uniform random deck (Mann, especially section 10).
One sensitive test for randomness uses a standard deck without the joker
Joker (playing card)
Joker is a special type of playing card found in most modern decks, or else a type of tile in some Mahjong game sets.-Name:It is believed that the term "Joker" comes from a mispronunciation of Jucker, the German/Alsatian name for the game Euchre. The card was originally introduced in about 1860 for...
s divided into suits with two suits in ascending order from ace to king, and the other two suits in reverse. (Many decks already come ordered this way when new.) After shuffling, the measure of randomness is the number of rising sequences that are left in each suit.
In practice the number of shuffles that you need depends both on how good you are at shuffling, and how good the people playing are at noticing and using non-randomness. Two to four shuffles is good enough for casual play. But in club play, good bridge players take advantage of non-randomness after four shuffles, and top blackjack
Blackjack
Blackjack, also known as Twenty-one or Vingt-et-un , is the most widely played casino banking game in the world...
players supposedly track aces through the deck; this is known as "ace tracking", or more generally, as "shuffle tracking".
Shuffling algorithms
In a computer, shuffling is equivalent to generating a random permutationRandom permutation
A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and simulation...
of the cards. There are two basic algorithms for doing this, both popularized by Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
.
The first is simply to assign a random number to each card, and then to sort the cards in order of their random numbers. This will generate a random permutation, unless any of the random numbers generated are the same as any others (i.e. pairs, triplets etc). This can be eliminated either assigning new random numbers to these cases, or reduced to an arbitrarily low probability by choosing a sufficiently wide range of random number choices. If using efficient sorting such as mergesort or heapsort
Heapsort
Heapsort is a comparison-based sorting algorithm to create a sorted array , and is part of the selection sort family. Although somewhat slower in practice on most machines than a well implemented quicksort, it has the advantage of a more favorable worst-case O runtime...
, this is an O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n log n) algorithm.
The second, generally known as the Knuth shuffle or Fisher–Yates shuffle, is a linear-time algorithm which involves moving through the pack from top to bottom, swapping each card in turn with another card from a random position in the part of the pack that has not yet been passed through (including itself). Providing that the random numbers are unbiased, this will always generate a random permutation.
In online gaming
These issues are of considerable commercial importance in online gamblingOnline gambling
Online gambling, also known as Internet gambling and iGambling, is a general term for gambling using the Internet.-Online poker:Online poker tables commonly offer Texas hold 'em, Omaha, Seven-card stud, razz, HORSE and other game types in both tournament and ring game structures...
, where the randomness of the shuffling of packs of simulated cards for online card games is crucial. For this reason, many online gambling sites provide descriptions of their shuffling algorithms and the sources of randomness used to drive these algorithms, with some gambling sites also providing auditors' reports of the performance of their systems.
External links
Physical card shuffling:Mathematics of shuffling:
- Real World Shuffling In Practice
- Shuffle - MathWorld - Wolfram Research
- Ivars Peterson's MathTrek: Card Shuffling Shenanigans
Real World (Historical) Application: