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