A deck of playing cards is randomized by a procedure called shuffling to provide an element of chance in card games. Shuffling is often followed by a cut, to ensure that the shuffler has not manipulated the outcome.
Contents:
1 Shuffling techniques
1.1 Riffle
1.2 Stripping
1.3 Pushing
1.4 Pile shuffle
1.5 Beginner shuffle
2 False Shuffles
3 Shuffling machines
4 Randomization
5 Shuffling algorithms
Shuffling techniques:
Several techniques are used to shuffle a deck of cards. While some techniques achieve a better randomization than other techniques, other techniques are easier to learn and easier to handle or better suited for special situations.
Riffle:
The riffle shuffle (sometimes called a faro shuffle) is the traditional method of shuffling. The deck is divided approximately in half, one part going into the left hand and the other part going into the right hand. Then by riffling the thumbs over the edges of the cards, the two halves of the deck are interleaved together. With practice a person can sometimes achieve a perfect shuffle, with every other card coming from alternating hands. This is not recommended, as will be shown below. Sometimes, computer programs that shuffle cards do several riffle shuffles, rather than just determine each card at random.
One riffle shuffle reorders the cards significantly. But the reordering is not random, by any means. The top card is still near the top. The bottom card is still near the bottom. Most pairs of cards are either still adjacent to each other, or not very far apart. And so, several shuffles are necessary. How many shuffles? Mathematics shows that at least seven shuffles are needed to randomize the cards. More shuffles than that do not affect the randomness. Bridge players often complain about the poor hands that result from computer dealt cards. This would seem to indicate that these people are used to inadequate shuffling.
A perfect shuffle occurs when the deck is divided exactly in half, and the cards are perfectly interlaced, with one card coming from one hand, then one card coming from the other hand, then one card coming from the first hand, etc. There are two types of perfect shuffles, the "in-shuffle" and the "out-shuffle." Let's assume that the deck is divided in two with the top cards going into the left hand and the bottom cards into the right hand. Then an in-shuffle begins with the first card coming from the left, the second from the right, the third from the left, etc. An out-shuffle begins with the first card coming from the right. If the right hand originally took the top cards, then the definitions are reversed (the in-shuffle begins with the first card coming from the right...). It has been shown that eight perfect out-shuffles returns the 52-card deck to its original order. Apparently, it takes more in-shuffles to do that. So, perfect shuffles do not randomize a deck, far from it.
Stripping:
Another procedure is called stripping, where small groups of cards are removed from the top or bottom of a deck and replaced on the opposite side (or just assembled on the table in reverse order). This is a much less effective randomizing procedure, and is thus mainly used in conjuction with riffling, or by younger players whose hands are not large enough for other methods.
Pushing:
"Pushing" 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 and is quite difficult to master.
Pile shuffle:
The pile shuffle is not a randomization technique, but a method to dissolve clumps of sticky cards. Cards are arranged in piles by putting the top card from the deck in turn on one of several piles. Then the piles are stacked on top of each other. This ensures that cards that were next to each other are now separated.
Beginner shuffle:
This involves simply spreading the cards out face down, and sliding them around and over each other with one's inexperienced 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.
This is also used periodically in casinos, where it is called a "wash" or "scramble". A typical sequence between hands of poker, for example, is a wash, two riffles, a strip, a third riffle, and a cut, which an experienced dealer can accomplish in as little as five seconds.
False Shuffles:
Magicians, sleight-of-hand artists, and card cheats employ various methods of shuffling whereby the deck appears to have been shuffled fairly, when in reality the order of the cards stays exactly the same.
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 casinos employ automatic shuffling machines which perform continuous shuffles on a pack of cards, and can produce any number of cards on demand. 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.
Randomization:
The mathematician and magician Persi Diaconis is an expert on the theory and practice of card shuffling, and an author of a famous paper on the number of shuffles needed to randomize a deck, concluding that it did not start to become random until five good riffle shuffles, and was truly random after seven. (You would need more shuffles if your shuffling technique is poor, of course.) Recently, the work of Trefethen et al. has questioned some of Diaconis' results, concluding that six shuffles is 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.
Here is an extremely sensitive test to experiment with. Take a standard deck without the jokers. Divide it 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.) Shuffle to your satisfaction. Then go through the deck trying to pull out each suit in the order ace, two, three ... When you reach the top of the deck, start over. How many passes did it take to pull out each suit?
What you are seeing is how many rising sequences are left in each suit. It probably takes more shuffles than you think to both get rid of rising sequences in the suits which were assembled that way, and add them to the ones that were not!
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. 2–4 shuffles is good enough for casual play. But in club play, good bridge players take advantage of non-randomness after 4 shuffles, and top blackjack players literally track aces through the deck.
Shuffling algorithms:
In a computer, shuffling is equivalent to generating a random permutation 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 two of the random numbers generated are the same. This can be eliminated either by retrying these cases, or reduced to an arbitrarily low probability by choosing a sufficiently wide range of random number choices.
The second, generally known as the Knuth shuffle or Fisher-Yates shuffle[1], is a linear-time algorithm (as opposed to the previous O(n log n) algorithm if using efficient sorting such as mergesort or heapsort), 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.
Notice that great care needs to be taken in implementing the Knuth shuffle; even slight deviations from the correct algorithm will produce biased shuffles. For example, working your way through the pack swapping each card in turn with a random card from any part of the pack is an algorithm with nn different possible execution paths, yet there are only n! permutations. A counting argument based on the pigeonhole principle will clearly show that this algorithm cannot produce an unbiased shuffle, unlike the true Knuth shuffle, which has n! execution paths which match up one-to-one with the possible permutations.
Whichever algorithm is chosen, it is important that a source of truly random numbers is used as the input to the shuffling algorithm. If a biased or pseudo-random source of random numbers is used, the output shuffles may be non-random in a way that is hard to detect, but easy to exploit by someone who knows the characteristics of the "random" number source.
