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,

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.

How to Cite this Page:
Su, Francis E., et al. "Rising Sequences in Card Shuffling." 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), 294-313. B. Morris, Magic Tricks Card Shuffling and Dynamic Computer Memories. Keywords:    probability Subjects:    combinatorics, probability Level:    Medium Fun Fact suggested by:   Francis Su Suggestions? Use this form. 3.80 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!