Shuffle

The term shuffle can also refer to the act of dragging one's feet on the ground while walking, running or dancing.

The riffle

A poker deck of playing poker cards is randomized by a procedure called shuffling to provide an element of chance in poker card games. Shuffling is often followed by a cut, to ensure that the shuffler has not manipulated the outcome.

Shuffling techniques

Several techniques are used to shuffle a poker deck of poker 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 most common shuffling technique is called a riffle, in which half of the poker deck is held in each hand with the thumbs inward, then poker cards are released by the thumbs so that they fall to the table intertwined.

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 a bit more difficult, it is often used in casinos because it minimizes the risk of exposing poker cards during the shuffle.

Stripping

Another procedure is called stripping, where small groups of poker cards are removed from the top or bottom of a poker 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 and fanning

"Pushing" is the procedure of pushing the ends of two halves of a poker deck against each other in such a way that they naturally intertwine. This requires skill and practice; as does fanning, which involves spreading the halves into fan shapes and intertwining them.

Pile shuffle

The pile shuffle is not a randomization technique, but a method to dissolve clumps of sticky poker cards. Poker cards are arranged in piles by putting the top poker card from the poker deck in turn on one of several piles. Then the piles are stacked on top of each other. This ensures that poker cards that were next to each other are now separated.

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 poker cards, and can produce any number of poker 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 poker card shuffling, and an author of a famous paper on the number of shuffles needed to randomize a poker 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 poker 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 poker card games is still open.

Here is an extremely sensitive test to experiment with. Take a standard poker 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 poker decks already come ordered this way when new.) Shuffle to your satisfaction. Then go through the poker deck trying to pull out each suit in the order ace, two, three ... When you reach the top of the poker 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 poker deck.

Shuffling algorithms

In a computer, shuffling is equivalent to generating a random permutation of the poker 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 poker card, and then to sort the poker 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, 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 poker card in turn with another poker 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 produced biased shuffles. For example, working your way through the pack swapping each poker card in turn with a random poker card from any part of the pack is an algorithm with nⁿ 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.

References

• D. Aldous and P. Diaconis, "Shuffling poker cards and stopping times", American Mathematical Monthly 93 (1986), 333–348
• Trefethen, L. N. and Trefethen, L. M. "How many shuffles to randomize a poker deck of poker cards?" Proceedings of the Royal Society London A 456, 2561–2568 (2000)