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.
How to Cite this Page:
Su, Francis E., et al. “Rising Sequences in Card Shuffling.” Math Fun Facts. <https://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.
Fun Fact suggested by:
Francis Su