Card Shuffling

In this series of interactives, we will explore various mathematical topics related to shuffling decks of cards. In the process, you will hopefully be convinced that riffle shuffling is actually a fairly good technique for shuffling cards.

Perfect Riffles

A riffle shuffle is performed by taking a deck of cards, dividing the deck in half ("cutting" the deck), and then interleaving the two halves. There are two possible ways of interleaving the two halves, one (an in-shuffle) where the top and bottom cards wind up inside the deck, and the other (an out-shuffle) where the top and bottom cards wind up in the same location.

The interactive below will allow you to visualize perfect riffle shuffles:

• Press "start" to begin the animation.
• Press "stop" and move the slider to manually watch the animation.
• Change the "Color Palette" to "Rainbow 1" to color each card differently to make it easier to follow each card.

The first couple of shuffles seem to mix up the deck fairly well, but what happens after many shuffles? Keep playing with the interactive until you're convinced that perfect riffle shuffles aren't a great way of shuffling cards.

Fixed Shuffles

One might wonder if the problem here is caused by the fact that we're shuffling the cards the same way each time, or have we just chosen a particularly bad choice of fixed shuffle? To answer this question, we need some way to talk about deterministic ways of reordering decks of cards. We'll have two ways of presenting a reordering. First, we can present a way of reordering the card as a table. Each column will have a card's original position in the deck above its new position in the deck.

For instance, if we had a three card deck and moved the top card to the bottom, we would represent this as:

Because the first (top) card moves into the third (bottom) position, the second card moves into the first (top) position, and the third card moves into the second position.

We can also represent these permutations using function diagrams. In these, we draw two decks of cards side by side and draw a line from a card's original position in the first deck to its new position in the second deck. Going back to our three card deck where we move the top card to the bottom, we would represent this as:

Below, you can experiment with various presentations for riffle shuffles:

We can also represent fixed shuffles using a transition diagram. In these, we draw an arrow from a to b if the card in position a winds up in position b.

Usage:

• To begin, press "New Random Shuffle" or "Copy Riffle Shuffle Above". This will show the table for the chosen type of shuffle.
• This will draw some circles with numbers in them. Your goal is to draw an arrow from the circle with the number a to the circle with the number b if the permutation takes a card in position a to position b. You can tell this from looking at the table.
  • For instance, if the first column of your table had a 1 over a 3, you should draw an arrow from the circled 1 to the circled 3.
• You can either select "draw arrow" under the "Mouse click to" drop down menu, or hold down the ctrl key while clicking to draw arrows.
• The interactive will only draw an arrow from the previously selected circle to the newly selected circle if there is supposed to be an arrow.
• You should move the circles around to try to make sense of the pattern. You can either select "drag" under the "Mouse click to" drop down menu or hold down the alt key while clicking and dragging to move circles around.
• Depending on your Color Palette, different colors will represent different cards (some will just loop through a fixed list of colors, causing repetition). Press the "Apply Shuffle to Colors" button to move the colors according to the shuffle rule. Notice that the cards on the right move the same way each time.

A Little Bit of Randomness

It should hopefully be clear at this point that just applying the same nonrandom shuffle each time to our deck of cards is a bad idea. There are 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000 different possible orders of cards in a 52 card deck, and we really don't want to just be cycling through a small handful of them.

So let's introduce a little bit of randomness to the deck, as follows:

1. Randomly pick out some (disjoint) adjacent pairs of cards,
2. For each pair, switch the cards in the pair.

Specifically, the top and bottom cards have a one in three chance of swapping with the next card in, and the cards in the middle of the deck have a one in four chance of moving up one space, one in two chance of staying put, and a one in four chance of moving down one space. Each card has a chance of moving, and if it does move, it will only move up or down one space in the deck. You also shouldn't worry about the mechanics of how we're going to implement this randomness in a real physical card deck -- I'll explain that later.

As before, this isn't a really great way of randomizing the cards in the deck. In this case, cards at the beginning of the deck stay in the beginning of the deck, and cards at the end of the deck stay in the end of the deck. We need to introduce randomness a fair number of times before these trends reduce in intensity, and even then their effects linger for a very long time (it may help to look at the "suits" color palette).

Let's look at this type of shuffling in another way. The interactive below will allow you to visualize the probability that a card starting in a certain position will wind up in a particular position after a certain number of shuffles. In the first column, only one cell is filled in, representing the position the card begins in. In the second column, we see the possible positions the card could wind up in after our first introduction of randomness, labeled by the probability of our card winding up in those positions. In the third column, we see the possible positions the card could wind up in after introducing randomness twice, labeled by the probability of our card winding up in those positions.

Hint: Hover your mouse over a box to get more information about what it's telling you.

Notice that even for a fairly small sized deck (12 cards) and a lot of shuffles (30 shuffles), our initial card is significantly more likely to wind up in some positions than others. This indicates that the deck is not nearly randomly shuffled. Play around with the interactive to get a sense of just how many shuffles you need before the card is roughly equally likely to wind up in any position in the deck.

A Normal Side Note

An interesting pattern emerges if we start with a card in the middle of a really large deck of cards and plot the probabilities of that card winding up in various positions, using a properly scaled bar chart.

As the number of shuffles increases, the tops of the bars in the bar graph above get closer and closer to forming a particular curve. This curve is called a Gaussian or Normal curve, and is given by a suitable transformation of the equation y=e^-x².

This is neat, but, alas, this is not what we're looking for. We're hoping that the distribution of probabilities is flat, that is, the probabilities are roughly equal that a card will wind up in any position.

Combining Shuffles

Finally, let's combine our two shuffling techniques to produce an imperfect riffle.

• First, we apply a perfect riffle shuffle to our deck as in the top of the page,
• Then, we introduce a small amount of randomness by swapping adjacent pairs, as above.

The interactive below will allow you to visualize the probability of a card starting in a particular position winding up in a particular position after some number of shuffles of this type.

How many shuffles does it take to even out the probabilities for 12 cards? 52 cards? 100 cards? Hint: use the horizontal bar graph (scaled) visualization.

It's clear that our imperfect riffle is much better than just doing our introduce a small amount of randomness operation. But why?

Chaos and Scale

A system is said to be chaotic if small changes in its input or initial configuration lead to large changes in its output or final configuration.

Note that this definition agrees in part with our intuitive use of the word chaotic in the sense of being unpredictable. Our ability to measure real-world systems is limited: small changes to a system might be too small for us to measure, but, if changes are magnified by the system, those immeasurably small initial changes may produce fairly substantial changes to the system that we weren't able to predict.

However our mathematical definition of chaotic doesn't exclude the possibility of the system being entirely unrandom in its behavior.

A good source of chaos is iterative systems, systems where the same operation is applied repeatedly, such as our card shuffling operation. Although our perfect riffle shuffle is entirely predictable in its behavior, it nonetheless meets our definition of chaotic. If two cards start out next to each other or near each other, their distance gets repeatedly doubled until they wind up in separate halves of the cut. (You can visualize this using the "First Two" or "Random Two" color palettes in the interactive at the top of the page.) We can alternately phrase this as: if we change the starting position of a card, the distance between where the card winds up and where it would have wound up gets repeatedly doubled (until they wind up in separate halves of the cut). While the first few doublings don't produce a significant effect, the effect becomes very significant as the number of doublings increases.

So what happens when we alternate our perfect riffle shuffle with our small introduction of randomness?

• The first perfect riffle doesn't actually do very much.
• The first small introduction of randomness introduces a very small change to the positions of cards in the deck.
• The second perfect riffle doubles the random change produced by the first small introduction of randomness. Specifically, instead of being a change in position of one space, the change is now a change in position of two spaces.
• The second small introduction of randomness introduces a very small change to the positions of cards in the deck. Note that this change is at a different scale (1 space) than the change introduced by the first small introduction of randomness (2 spaces).
• The third perfect riffle shuffle doubles both of the random changes above. The first random change is now a change in position of 4 spaces, and the second random change is now a change in position of 2 spaces, making room for the change in position introduced by the coming small introduction of randomness.

We can follow these changes in the table below:

Since these changes are all at different scales, they don't interfere with each other much, and the changes quickly get large enough to cover the entire deck.

Compare this with just applying the small introduction of randomness operation over and over again: Each operation introduces a change at the scale of one space, and so risk cancelling each other out.