Shuffle
|
|
The term shuffle can also refer to the act of dragging one's feet on the ground while walking, running or dancing.
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 |
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 most common shuffling technique is called a riffle, 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 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 cards during the shuffle.
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 and fanning
"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. 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 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.
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] (http://www.nist.gov/dads/HTML/fisherYatesShuffle.html), 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.
References
- D. Aldous and P. Diaconis, "Shuffling cards and stopping times", American Mathematical Monthly 93 (1986), 333–348
- Trefethen, L. N. and Trefethen, L. M. "How many shuffles to randomize a deck of cards?" Proceedings of the Royal Society London A 456, 2561–2568 (2000)
External links
- http://www.math.washington.edu/~chartier/Shuffle/
- http://www.nature.com/nsu/001005/001005-8.html
- Shuffle - MathWorld - Wolfram Research (http://mathworld.wolfram.com/Shuffle.html)
- Generating random permutations (http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE151.HTM)
- Ivars Peterson's MathTrek: Card Shuffling Shenanigans (http://www.maa.org/mathland/mathtrek_11_18_02.html)de:Mischen (Spielkarten)