Added to Favorites

Related Searches

Definitions

Shuffling is a procedure used to randomize a deck of playing cards 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.

A typical sequence between hands of poker, for example, is a wash, two riffles, a strip, a third riffle, and a cut.

For a deck of given size, the number of Mongean shuffles that it takes to return a deck to starting position, is known .

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 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 will 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.

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 about the right pressure when pushing the cards into each other. If one does perform eight perfect faro shuffles in a row, the order of the deck will return to the original order, 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 get weaved in during each shuffle then it takes 52 shuffles to return a deck back into original order (26 shuffles to reverse the order of a deck containing 52 cards).

Both performance magicians and card sharps regard the Zarrow shuffle as a particularly effective example of the false shuffle. In this shuffle, the entire deck remains in its original order, although spectators think they see an honest riffle shuffle.

A famous paper by mathematician and magician Persi Diaconis 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.

One sensitive test for randomness uses a standard deck without the jokers 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".

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, 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.

For an example of how this pigeonhole argument works on the n^{n} shuffle, consider the simple case of shuffling only three cards, so that n=3. Then there are n^{n} = 27 different possible execution paths (these are the 27 things to put in the pigeonholes). But there are only 3! = 6 ways to permute three cards (these are the 6 pigeonholes to put the things in). 27 is odd, and 6 is even, so 27 things cannot be divided evenly into 6 pigeonholes. Therefore, if we assume that the execution paths are equiprobable, then the outcomes cannot be, since at least two of the different outcomes must have different probabilities. Therefore the n^{n} shuffle cannot be unbiased for n=3. Similar reasoning can be applied for other values of n > 2.

Another very easy mistake to make is to overlook the possibility of swapping an element with itself. The consequence of this error is that an element (for example, the top element) can never remain in its same position after the shuffle, when in reality, 1/52 of the time, it should.

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 (weak) 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 supposedly "random" number source.

This form of bias can be avoided in a number of ways. Probably the easiest involves deliberately limiting the number of usable outputs of the random number generator to a multiple of the number of choices to be made prior to performing the modulo operator, and re-trying the random number generator until a value within that range is produced. Although this algorithm is, strictly speaking, not guaranteed to terminate, given a true random number generator, the probability of this algorithm not terminating in a reasonable time is so small that it can be neglected for all practical purposes.

It should also be noted that many pseudo-random number generators have non-random behavior in their low-order bits. If using the modulo operator as described above, with a small set of items to be shuffled, this non-random behavior in the low-order bits can produce very poor shuffles.

Mathematics of shuffling:

- Real World Shuffling In Practice
- Shuffle - MathWorld - Wolfram Research
- Generating random permutations
- Ivars Peterson's MathTrek: Card Shuffling Shenanigans

Real World (Historical) Application:

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday October 01, 2008 at 03:27:40 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday October 01, 2008 at 03:27:40 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.