Introduction

You are dealt 5 cards. You lift your cards to see 4 aces in your hand! The odds that you will be dealt four of any kind in a five card hand are clearly against you, so long as the deck is randomly ordered. This makes you wonder, was the deck not sufficiently shuffled, or were you very lucky? This leads to other questions about shuffling a deck of cards. How many times do you need to shuffle a deck of cards before the order of the deck is sufficiently random? Is there some minimum number of shuffles required to ensure the deck is not ordered, or not predictable? Is there a point where continued shuffling no longer helps make the deck less predictable? And just what do we mean by randomness, order, and predictability in a deck of cards?

Modeling the Problem

In order to answer these questions, one of the tools we have at our disposal is mathematical modeling. It is difficult to say explicitly what we mean when we say a deck is or is not "random". Without such an explicit definition, it would be extremely difficult to analyze the random properties of shuffling a deck of cards.

Using math to model the behavior of a deck of cards as it is shuffled will allow us to use mathematical notions of order and predictability to analyze the progress of the deck. Mathematical models are only an approximation to reality, but the sacrifice we make in accuracy when we use a mathematical model is more than made up for: Using a mathematical model allows us to use the robust toolset of mathematics to analyze the situation both quantitatively and qualitatively.

The Model

The normal way of shuffling a deck of cards is often called the riffle shuffle, because you riffle the cards together from two piles. In their paper Trailing the Dovetail Shuffle to Its Lair (Ann. Appl. Probability 2, 294-313, 1992), David Bayer and Persi Diaconis aptly describe a mathematical model of the riffle shuffle, called the GSR (Gilbert, Shannon, Reeds) model:

"A deck of n cards is cut into two portions according to a binomial distribution; thus the chance that k cards are cut off is for . The two packets are then riffled together in such a way that cards drop from the left or right heaps with probability proportional to the number of cards in each heap." -Bayer and Diaconis

This says that a deck of cards is usually cut about midway, and rarely cut close to the front or back of the deck. Next, as the deck is shuffled it can be seen as one card after another dropping from the left and right hands. This model assumes the probability that a card will drop from the left hand is L / (L + R) where L and R are the numbers of cards still in the left and right hands respectively. For example, if you had 10 cards in your left hand and 15 in your right, the probability that the next card would drop from your left hand would be 10/(10+15) and the probability that it would drop from the right would be 15/(10+15). Notice that the sum of 10/(10+15) and 15/(10+15) equals 1. Indeed, the probability that the next card will drop from either the left hand or the right hand is 1.

Using this model, Bayer and Diaconis investigate the evolution of randomness in a deck of cards shuffled some number of times. Each shuffle brings the deck from one state to another with some probability. This is where Markov chains become useful. Markov chains can model the behavior of a system that depends only on the previous experiment or state. That is, the next state of the system depends only on the current state where the outcome of each experiment is one of a discrete set of states. Markov chains require a transition matrix, P, where P(j,i) equals the probability of going from state i to state j.

Let us return our focus to the shuffling of cards. A set of discete states for our system could be defined as the n! possible orderings of a deck of n cards. Do you see a problem with this? The corresponding transition matrix for a deck of 52 cards would require a square matrix of dimension 52! x 52!. By our calculations*, the number of entries this matrix would require is astronomically larger than the number of atoms in the Earth.

We could sink into an abyss of hopeless dispair. Instead, let us define a rising sequence. Again, we borrow the definition from Bayer and Diaconis:

A rising sequence is a maximal subset of an arrangement of cards, consisting of successive face values displayed in order. Rising sequences do not intersect, so each arrangement of a deck of cards is uniquely the union of its rising sequences. -Bayer and Diaconis

For example, the sequence "1745236", as shown below, has exactly three rising sequences.

The first rising sequence is 123, shown below, because those numbers are found in order from left to right in the sequence.

The next rising sequence is 7:

The third and final rising sequence is 456:

The initial ordering of a deck of n cards is 123...n, which has one rising sequence. The minimum number of rising sequences for any ordering is 1, and there can be up to n rising sequences in a ordering of n cards. (Verify this for yourself.) Now, let us define state i as the situation where we have a ordering of cards containing i rising sequences. By redefining our states in this way, the transition matrix requires only n x n entries.

Specifically, the entries of the transition matrix P are:

where a(j)= Eulerian numbers. These numbers denote the number of permutations of the {1,2...,n} that have j rising sequences.

The question of how many shuffles is needed to randomize a deck still remains. To interactively explore this model and discover the answer, click here to see a simulation of the GSR model.