From the Fun Fact files, here is a Random Fun Fact, at the Medium level: |
How many shuffles does it take to randomize a deck of cards?
The answer, of course, depends on what kind of shuffle
you consider. Two popular kinds of shuffles are the
random riffle shuffle and the overhand shuffle.
The random riffle shuffle is modeled
by cutting the deck binomially and dropping cards
one-by-one from either half of the deck with probability
proportional to the current sizes of the deck halves.
In 1992, Bayer and Diaconis showed that after
seven random riffle shuffles of a deck of 52 cards,
every configuration is nearly equally likely.
Shuffling more than this does not significantly
increase the "randomness"; shuffle less than this
and the deck is "far" from random.
In fact, it is possible to show that five shuffles are
not enough to bring about the reversal of a deck---see
Rising Sequences in Card Shuffling. So
it is somewhat surprising that just two shuffles later,
every configuration is possible and nearly equally likely.
By the way, the overhand shuffle is a really bad way to
mix cards: it takes about 2500 overhand shuffles
to randomize a deck of 52 cards!
Bring a deck of cards in and demonstrate how non-random
just 2 or 3 shuffles are by ordering the deck and then
letting someone shuffle. There will still be discernible
patterns after a small number of shuffles!
The Math Behind the Fact:
A well-written account of Bayer and Diaconis' result
may be found in the Mann reference. There are many
ideas in this result. Analysis of the
"distance from randomness" requires the choice of
a metric betwen probabilities. Combinatorics and
probability intertwine in the analysis of
rising sequences generated after a certain number
of shuffles, which is an important part of proving this
There are, of course, non-random shuffles:
see Perfect Shuffles.
How to Cite this Page:
Su, Francis E., et al. "Seven Shuffles."
Math Fun Facts.
The Link for this Fun Fact:
is directly accessible here.