Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.
Get a random Fun Fact!
or
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  The Math Fun Facts App!
 
  List All : List Recent : List Popular
  About Math Fun Facts / How to Use
  Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su
All rights reserved.

From the Fun Fact files, here is a Fun Fact at the Medium level:

Seven Shuffles

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!

Presentation Suggestions:
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 result.

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. <http://www.math.hmc.edu/funfacts>.

References:
    Brad Mann, "How many times should you shuffle a deck of cards?"
    UMAP J. 15 (1994), no. 4, 303--332.
    Dave Bayer and Persi Diaconis, "Trailing the dovetail shuffle to its lair",
    Ann. Appl. Probab. 2(1992), no. 2, 294--313.

Keywords:    card shuffling, probability
Subjects:    combinatorics, probability
Level:    Medium
Fun Fact suggested by:   Brad Mann
Suggestions? Use this form.
4.28
 
current
rating
Click to rate this Fun Fact...
    *   Awesome! I totally dig it!
    *   Fun enough to tell a friend!
    *   Mildly interesting
    *   Not really noteworthy
and see the most popular Facts!
Get the Math Fun Facts
iPhone App!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!