# 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, 1__6__23__78__45
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).