Перемешивание карт: методы и математика случайности.

Procedure used to randomize a deck of playing cards

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 help ensure that the shuffler has not manipulated the outcome. TOC

One of the easiest shuffles to accomplish after a little practice is the overhand shuffle. Johan Jonasson wrote, "The overhand shuffle is the shuffling technique where you gradually transfer the deck from, say, your right hand to your left hand by sliding off small packets from the top of the deck with your thumb." In detail as normally performed, with the pack initially held in the left hand (say), most of the cards are grasped as a group from the bottom of the pack between the thumb and fingers of the right hand and lifted clear of the small group that remains in the left hand. Small packets are then released from the right hand a packet at a time so that they drop on the top of the pack accumulating in the left hand. The process is repeated several times. The randomness of the whole shuffle is increased by the number of small packets in each shuffle and the number of repeat shuffles performed. The overhand shuffle offers sufficient opportunity for sleight of hand techniques to be used to affect the ordering of cards, creating a stacked deck. The most common way that players cheat with the overhand shuffle is by having a card at the top or bottom of the pack that they require, and then slipping it to the bottom at the start of a shuffle (if it was on top to start), or leaving it as the last card in a shuffle and just dropping it on top (if it was originally on the bottom of the deck).

A common shuffling technique is called the riffle, or dovetail shuffle or leafing the cards, 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; it 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 casinos 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 second 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). The Gilbert–Shannon–Reeds model provides a mathematical model of the random outcomes of riffling that has been shown experimentally to be a good fit to human shuffling and that forms the basis for a recommendation that card decks be riffled seven times in order to randomize them thoroughly. Later, mathematicians Lloyd M. Trefethen and Lloyd N. Trefethen authored a paper using a tweaked version of the Gilbert–Shannon–Reeds model showing that the minimum number of riffles for total randomization could also be six, if the method of defining randomness is changed.

Also known as the "Indian", "Kattar", "Kenchi" (Hindi for scissor) or "Kutti Shuffle". 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. Indian 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.

Cards are simply dealt out into a number of piles, then the piles are stacked on top of each other. Though this is deterministic and does not randomize the cards at all, it ensures that cards that were next to each other are now separated. Some variations on the pile shuffle attempt to make it slightly random by dealing to the piles in a random order each circuit.

A person may throw a deck of cards into the air or across a surface, and then pick up the cards in random order, assembled with the cards facing the same direction. If specific cards are observed too closely as they are picked up, an additional 52 pickup or an additional shuffling method may be needed for sufficient randomization. This method is useful for beginners, but the shuffle requires a large clean surface for spreading out the cards, and it may take more time than is desired.

This method is similar to 52 pickup and also useful for beginners. Also known as the Chemmy, Irish, wash, scramble, hard shuffle, smooshing, schwirsheling, 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. Statistically random shuffling is achieved after approximately one minute of smoothing. Smooshing has been largely popularized by Simon Hofman.

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.

The Mexican spiral shuffle is performed by cyclic actions of moving the top card onto the table, then the new top card under the deck, the next onto the table, next under the deck, and so on until the last card is dealt onto the table. It takes quite a long time, compared with riffle or overhand shuffles, but allows other players to fully control cards which are on the table. The Mexican spiral shuffle was popular at the end of the 19th century in some areas of Mexico as a protection from gamblers and con men arriving from the United States.

Especially useful for large decks, a shuffler may divide a deck into two or more smaller decks, and give the other portion(s) to (an)other shuffler(s), each to choose their own shuffling method(s). Smaller decks or portions of smaller decks may be traded around as shuffling continues, then the smaller decks are combined (and briefly shuffled) into the original large deck. This also prevents one shuffler having unfair control of the randomization.

Typically performed after a previous shuffling method, the cut is of simply taking a deck, dividing it into two portions of random size, and putting the previously lower portion on top of the previously higher portion. This is occasionally performed by a second shuffler, for additional assurance of randomization, and to prevent either the shuffler or an observer from knowing the top or bottom card.

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 one or more cards (up to and including the entire deck) stays in the same position. It is also possible, though generally considered very difficult, to "stack the deck" (place cards into a desirable order) by means of one or more riffle shuffles; this is called "riffle stacking". Both performance magicians and card sharps regard the Zarrow shuffle and the Push Through False Shuffle as particularly effective examples of the false shuffle. In these shuffles, the entire deck remains in its original order, although spectators think they see an honest riffle shuffle.

Casinos often equip their tables with shuffling machines instead of having croupiers shuffle the cards, as it gives the casino a few advantages, including an increased complexity to the shuffle and therefore an increased difficulty for players to make predictions, even if they are collaborating with croupiers. The shuffling machines are carefully designed to avoid biasing the shuffle and are typically computer controlled. Shuffling machines also save time that would otherwise be wasted on manual shuffling, thereby increasing the profitability of the table. These machines are also used to lessen repetitive motion stress injuries to a dealer. Players with superstitions often regard with suspicion any electronic equipment, so casinos sometimes still have the croupiers perform the shuffling at tables that typically attract those crowds (e. g., baccarat tables).

There are 52 factorial (expressed in shorthand as 52!) possible orderings of the cards in a 52 card deck. In other words, there are 52 × 51 × 50 × 49 × ··· × 4 × 3 × 2 × 1 possible combinations of card sequence. This is approximately 8.0658 (80,658vigintillion) possible orderings, or specifically 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000. The magnitude of this number means that it is exceedingly improbable that two randomly selected, truly randomized decks will 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.

The number of shuffles that are sufficient for a "good" level of randomness depends on the type of shuffle and the measure of "good enough randomness", which in turn depends on the game in question. For most games, four to seven riffle shuffles are sufficient: for unsuited games such as blackjack, four riffle shuffles are sufficient, while for suited games, seven riffle shuffles are necessary. There are some games, however, for which even seven riffle shuffles are insufficient. In practice the number of shuffles required depends both on the quality of the shuffle and how significant non randomness is, particularly 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, 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. 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.

If a computer has access to purely random numbers, it is capable of generating a "perfect shuffle", a random permutation of the cards; beware that this terminology (an algorithm that perfectly randomizes the deck) differs from "a perfectly executed single shuffle", notably a perfectly interleaving faro shuffle. The Fisher–Yates shuffle, popularized by Donald Knuth, is simple (a few lines of code) and efficient (O(n) on an n card deck, assuming constant time for fundamental steps) algorithm for doing this. Shuffling can be seen as the opposite of sorting. A new alternative to Fisher Yates, which does not use any array memory operations, is the use a Pseudo Random Index Generator (PRIG) function algorithm. There are other, less desirable algorithms in common use. For example, one can assign a random number to each card, and then 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 by adjusting one of the pair's values randomly up or down by a small amount, 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) average and worst case algorithm.

These issues are of considerable commercial importance in online gambling, 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.