Gilbert–Shannon–Reeds model

In the mathematics of shuffling playing cards, the Gilbert–Shannon–Reeds model is a probability distribution on riffle shuffle permutations that has been reported to be a good match for experimentally observed outcomes of human shuffling,[1] and that forms the basis for a recommendation that a deck of cards should be riffled seven times in order to thoroughly randomize it.[2] It is named after the work of Edgar Gilbert, Claude Shannon, and J. Reeds, reported in a 1955 technical report by Gilbert[3] and in a 1981 unpublished manuscript of Reeds.

The model

The Gilbert–Shannon–Reeds model may be defined in several equivalent ways.

Most similarly to the way humans shuffle cards, it can be defined as a random cut and riffle. The deck of cards is cut into two packets; if there are a total of n cards, then the probability of selecting k cards in the first deck and n − k in the second deck is ${\displaystyle {\tbinom {n}{k}}/2^{n}}$. Then, one card at a time is repeatedly moved from the bottom of one of the packets to the top of the shuffled deck, such that if x cards remain in one packet and y cards remain in the other packet, then the probability of choosing a card from the first packet is x/(x + y) and the probability of choosing a card from the second packet is y/(x + y).[2]

An alternative description can be based on a property of the model, that it generates a permutation of the initial deck in which each card is equally likely to have come from the first or the second packet.[2] To generate a random permutation according to this model, begin by flipping a fair coin n times, to determine for each position of the shuffled deck whether it comes from the first packet or the second packet. Then split into two packets whose sizes are the number of tails and the number of heads flipped, and use the same coin flip sequence to determine from which packet to pull each card of the shuffled deck.

Another alternative description is more abstract, but lends itself better to mathematical analysis. Generate a set of n values from the uniform continuous distribution on the unit interval, and place them in sorted order. Then the doubling map ${\displaystyle x\mapsto 2x{\pmod {1}}}$ from the theory of dynamical systems maps this system of points to a permutation of the points in which the permuted ordering obeys the Gilbert–Shannon–Reeds model, and the positions of the new points are again uniformly random.[2][4]

Among all of the possible riffle shuffle permutations of a card deck, the Gilbert–Shannon–Reeds model gives almost all riffles equal probability, 1/2ⁿ, of occurring. However, there is one exception, the identity permutation, which has a greater probability (n + 1)/2ⁿ of occurring.[5][6]

Inverse

The inverse permutation of a random riffle may be generated directly. To do so, start with a deck of n cards and then repeatedly deal off the bottom card of the deck onto one of two piles, choosing randomly with equal probability which of the two piles to deal each card onto. Then, when all cards have been dealt, stack the two piles back together.[2]

The effect of repeated riffles

Bayer & Diaconis (1992) analyzed mathematically the total variation distance between two probability distributions on permutations: the uniform distribution in which all permutations are equally likely, and the distribution generated by repeated applications of the Gilbert–Shannon–Reeds model. The total variation distance measures how similar or dissimilar two probability distributions are; it is zero only when the two distributions are identical, and attains a maximum value of one for probability distributions that never generate the same values as each other. Bayer and Diaconis reported that, for decks of n cards shuffled ${\displaystyle {\tfrac {3}{2}}\log _{2}n+\theta }$ times, where θ is an arbitrary constant, the total variation distance is close to one when θ is significantly less than zero, and close to zero when θ is significantly greater than zero, independently of n. In particular their calculations showed that for n = 52, five riffles produce a distribution whose total variation distance from uniform is still close to one, while seven riffles give total variation distance 0.334. This result was widely reported as implying that card decks should be riffled seven times in order to thoroughly randomize them.[7][8][9]

Similar analyses have been performed using the Kullback–Leibler divergence, a distance between two probability distributions defined in terms of entropy; the divergence of a distribution from uniform can be interpreted as the number of bits of information that can still be recovered about the initial state of the card deck. The results are qualitatively different: rather than having a sharp threshold between random and non-random at ${\displaystyle {\tfrac {3}{2}}\log _{2}n}$ shuffles, as occurs for total variation distance, the divergence decays more gradually, decreasing linearly as the number of shuffles ranges from zero to ${\displaystyle \log _{2}n}$ (at which point the number of remaining bits of information is linear, smaller by a logarithmic factor than its initial value) and then decreasing exponentially until, after ${\displaystyle {\tfrac {3}{2}}\log _{2}n}$ shuffles, only a constant number of bits of information remain.[10][11]

References

1. Diaconis, Persi (1988), Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Hayward, California: Institute of Mathematical Statistics, ISBN 978-0-940600-14-0, MR 0964069.
2. Bayer, Dave; Diaconis, Persi (1992), "Trailing the dovetail shuffle to its lair" (PDF), The Annals of Applied Probability, 2 (2): 294–313, doi:10.1214/aoap/1177005705, JSTOR 2959752, MR 1161056.
3. Gilbert, E. (1955), Theory of shuffling, Technical memorandum, Bell Labs
4. Lalley, Steven P. (1999), "Riffle shuffles and their associated dynamical systems", Journal of Theoretical Probability, 12 (4): 903–932, doi:10.1023/A:1021636902356, MR 1729462.
5. This follows immediately from Theorem 1 of Bayer & Diaconis (1992) together with the observation that the identity permutation has one rising sequence and all other riffle permutations have exactly two rising sequences.
6. Lalley (1999) instead states erroneously that all permutations are likely.
7. Austin, David (December 2010), How Many Times Do I Have to Shuffle This Deck?, AMS Feature Columns.
8. Numb3rs 519: Animal Rites, Numb3rs Math Activities, Cornell University Department of Mathematics.
9. Kolata, Gina (January 9, 1990), "In Shuffling Cards, 7 Is Winning Number", New York Times.
10. Trefethen, L. N.; Trefethen, L. M. (2000), "How many shuffles to randomize a deck of cards?", Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 456 (2002): 2561–2568, Bibcode:2000RSPSA.456.2561T, doi:10.1098/rspa.2000.0625, MR 1796496.
11. Stark, Dudley; Ganesh, A.; O'Connell, Neil (2002), "Information loss in riffle shuffling", Combinatorics, Probability and Computing, 11 (1): 79–95, doi:10.1017/S0963548301004990, MR 1888184.