Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

shuffle





riffle shuffle
How many shuffles does it take to randomize a deck of cards – in other words, to mix up the cards about as thoroughly as dropping them all the floor and stirring them around for several minutes (the author's usual method). The answer depends on the kind of shuffle used.

The beginner's overhand shuffle, for example, is a really bad way to mix cards: about 2,500 such shuffles are need to randomize a deck of 52 cards. A magician's perfect shuffle, on the other hand, in which the cards are cut exactly in half and them perfectly interlaced, never produces randomization (see below). One of the most effective ways to get a random deck is the riffle shuffle in which the deck is cut in half and imperfectly interlaced by dropping cards one by one from either half of the deck with a probability proportional to the current sizes of the deck splits.

In 1992 Persi Diaconis (then at Harvard) and David Bayer demonstrated that, starting with a completely ordered deck, it takes seven riffle shuffles to produce randomization.1 Any more than this and there's no significant increase in the randomness; any less and the shuffle is far from random. In fact, not only are five or six riffles not enough to randomize, there are some configurations of cards that are impossible to reach in this number of shuffles! To understand this, suppose the starting order of the cards is marked 1 to 52, top to bottom. After one shuffle, only configurations with two or fewer rising sequences are possible. A rising sequence is a maximal increasing sequential ordering of cards that appear in the deck (with other cards possibly interspersed) as it is run through from top to bottom. For instance, in an eight-card deck, 12345678 is the ordered deck and it has one rising sequence. After one shuffle, 16237845 is a possible configuration and there are two rising sequences (the underlined numerals form one, the non-underlined numerals form the other). Clearly the rising sequences are formed when the deck is cut before the cards are interleaved in the shuffle. After two shuffles, there can be at most four rising sequences, since each of the two rising sequences from the first shuffle has a chance of being cut in the second. This pattern continues: the number of rising sequences can at most double during each shuffle. After five shuffles, there at most 32 rising sequences. But the reversed deck, numbered 52 down to 1, has 52 rising sequences. Thus, this is one (of many) arrangements that are unattainable in five riffle shuffles. Interestingly, Diaconis and other researchers have also found that decks can undergo sudden changes in their degree of randomness; after six riffle shuffles, a deck is still visibly ordered, but this order vanishes one shuffle later.

Perfect shuffles do the exact opposite of randomizing: they preserve order at every stage. There are two kinds of perfect shuffles. The out-shuffle is one in which the top card stays on top; the in-shuffle is one in which the top card moves to the second position of the deck. Amazingly, eight perfect out-shuffles restore the deck to its original order! Magicians use combinations of out and in shuffles to perform a variety of baffling tricks and to control the position of any given card in a deck. How could you make the top card (call it position 0) go to position n? Easy: write n in binary (base 2), read the 0's and 1's from left to right, perform an out-shuffle for a 0 and an in-shuffle for a 1, and, as if my magic, the top card will have materialized at position n.


Reference

  1. Bayer, D. and Diaconis, P. "Trailing the Dovetail Shuffle to Its Lair." Annals of Applied Probability, 2(2): 294-313 (1992).

Related category

   • GAMES AND PUZZLES