hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su

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

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

# Rising Sequences in Card Shuffling

In Seven Shuffles we saw that it takes about 7 random riffle shuffles to randomize a deck of 52 cards. This means that after 7 shuffles, every configuration is nearly equally likely.

An amazing fact is that five random riffle shuffles are not enough to randomize a deck of cards, because not only is every configuration not nearly equally likely, there are in fact some configurations which are not reachable in 5 shuffles!

To see this, suppose (before shuffling) the cards in a deck are arranged in order from 1 to 52, top to bottom. After doing one shuffle, what kind of sequences are possible? A moment's reflection reveals that only configurations with 2 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 you run through the cards from top to bottom. For instance, in an 8 card deck, 12345678 is the ordered deck and it has 1 rising sequence. After one shuffle,

16237845

is a possible configuration; note that it has 2 rising sequences (the black numerals form one, the red numerals form the other). Clearly the rising sequences are formed when the deck is cut before they are interleaved in the shuffle.

So, after doing 2 shuffles, how many rising sequences can we expect? At most 4, since each of the 2 rising sequences from the first shuffle have a chance of being cut in the second shuffle. So the number of rising sequences can at most double during each shuffle. After doing 5 shuffles, there at most 32 rising sequences.

But the reversed deck, numbered 52 down to 1, has 52 rising sequences! Therefore the reversed deck cannot be obtained in 5 random riffle shuffles!

Presentation Suggestions:
You can illustrate examples of rising sequences on the blackboard.

The Math Behind the Fact:
The analysis of shuffling involves both combinatorics, probability, and even some group theory. Though we've been discussing "random" riffle shuffles in this Fun Fact, you can also study the mathematics of Perfect Shuffles, which have no randomness.

Su, Francis E., et al. "Rising Sequences in Card Shuffling." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

References:

Keywords:    probability
Subjects:    combinatorics, probability
Level:    Medium
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
3.99
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!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity

Want another Math Fun Fact?

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