A month ago, I was playing the card game Crazy Eights with one of my children. During the middle of one game, we went through the entire deck, so we shuffled the cards in the discard pile a few times and started playing again. Hmmm. The cards were still grouped too closely by suits; that is, in spite of the shuffles, we were still seeing long sequences of, say, clubs when drawing from the pile. The ordering from the first part of the game persisted after the shuffles; it would seem that the shuffles hadn’t affected the ordering of the deck as much as we wished.

This led me to wonder how many shuffles would be needed to give a good guarantee that the deck had been put in random order. Curiously, I soon came across an essay in Aigner and Ziegler’s wonderful book Proofs from the Book that addressed just this issue and that led me to a remarkable paper by Aldous and Diaconis that gives an answer to this question.

This column will explain a few of the techniques and results from that paper. What is surprising is that a mathematical analysis of this seemingly innocuous question is linked to a wide range of mathematical questions, in areas such as Lie algebras, Hochschild homology, and random walks on graphs, and has been generalized in significant ways.

Let’s begin by supposing that we have a deck of n cards; to keep things simple, we will assume that the cards are decorated only with the numbers1to n. Initially, the cards are in numerical order and we will shuffle them using some technique that we agree upon. The usual shuffle is called ariffle shuffle and will be discussed later. For now, we’ll begin with a simpler type of shuffle called the top-in-at-random shuffle. In this shuffle, we remove the top card from the deck and place it, with equal probability, in any of the n available positions.

For instance, with n=3, there are three possibilities, each of which is equally likely.

Let’s be quantitative about this shuffle. The set of all orderings of the deck will be denoted by Sn, which is often called the symmetric group onnletters. There are n! possible orderings. If π is a particular ordering of the deck, we will denote the probability that π is obtained after one shuffle byQ(π).Consider the example above in which n=3. If we write the ordering of the deck from left to right, we see that

π	Q(π)
1 2 3	0.333
1 3 2	0.000
2 1 3	0.333
2 3 1	0.333
3 1 2	0.000
3 2 1	0.000

This shows that three of the six possible orderings are equally likely, and the other three are not at all possible. So we shuffle again … and again. The possible orderings of the deck are shown below after 1, 2, and 3 shuffles. For convenience, the cards are here represented by colors rather than numbered.

By Qk(π), we will mean the probability that the ordering π occurs after k shuffles. A little computation shows that

	Q1(π)	Q2(π)	Q3(π)	Q4(π)	Q5(π)	Q6(π)	Q7(π)	Q8(π)	Q9(π)	Q10(π)
1 2 3	0.333	0.222	0.185	0.173	0.169	0.167	0.167	0.167	0.167	0.167
1 3 2	0.000	0.111	0.148	0.160	0.165	0.166	0.166	0.167	0.167	0.167
2 1 3	0.333	0.222	0.185	0.173	0.169	0.167	0.167	0.167	0.167	0.167
2 3 1	0.333	0.222	0.185	0.173	0.169	0.167	0.167	0.167	0.167	0.167
3 1 2	0.000	0.111	0.148	0.160	0.165	0.166	0.166	0.167	0.167	0.167
3 2 1	0.000	0.111	0.148	0.160	0.165	0.166	0.166	0.167	0.167	0.167

Notice that as we perform more shuffles, the frequency with which we see the different orderings becomes more uniform. By U(π), we will denote the probability density in which each ordering π is equally likely; that is, U(π)=1/n! The results in the table above indicate that

To make this statement precise, and to faciliate a quantative analysis of shuffling, we need to introduce a notion of distance between probability densities. Therefore, suppose that Q1 and Q2 are two probability densities on Sn. First, we define the difference in Q1 and Q2 for A, a subset of Sn, by adding together the differences over all the elements of A:

Then the distance between Q1 and Q2 is the maximum distance over all the subsets of Sn:

Note that this is a very sensitive measure of the distance between the two densities. First, notice that 0≤∥Q1−Q2∥≤1. Next, imagine that U, the uniform distribution on Sn, and Q is a density resulting from a particular type of shuffle. If this type of shuffle leaves a single card in its original place, then

which is a rather large distance considering that the maximum distance between sets is 1.You may wish to check that the distance between the initial distribution I, which has I(12…n)=1 and I(π)=0 for all other orderings, satisifies:

With this definition, our example indicates that ∥Qk−U∥→0 as k→∞, which means that shuffling the deck using top-in-at-random shuffles will eventually produce all orderings of the deck with equal probability.

Strong uniform stopping rules

Given a technique for shuffling the deck, and its resulting probability density function Q, we would like to be able to estimate how far away from the uniform distribution we are after k shuffles; that is, we would like to understand the distance ∥Qk−U∥.

The notion of a strong uniform stopping rule gives us a tool for understanding this distance. First, imagine that we look at each shuffle in a sequence of shuffles and that we have a criterion that stops the sequence when satisfied.

For example, imagine that we have a sequence of top-in-random shuffles and that we stop the sequence when the card that was originally at the bottom of the deck (and labeled by n) rises to the top and is then inserted somewhere in the deck.

This is illustrated below for the case n=3. The bottom card is shown in red so we stop the sequences at the orderings in the gray box.

We call such a criterion a strong uniform stopping rule if when the sequence is stopped after k shuffles, then the resulting orderings are uniformly distributed. As a little thought shows, the rule described above for top-in-at-random shuffles satisfies this condition since at every step the ordering of the cards below card n is uniform. This is apparent, for the case n=3 and k=3, in the figure above.Why are strong uniform stopping rules useful? The following remarkable fact explains.

Suppose that T denotes the stopping time for a sequence of shuffles and P(T>k) denotes the probability that the stopping time of a sequence is larger than k. Then we have the following bound on the distance beween Qk and U: ∥Qk−U∥≤P(T>k).

In other words, this reduces the problem of comparing the distance between the density after k shuffles and the uniform density to an analysis of the stopping time. As we’ll see, this can be a much simpler problem.Where does this bound come from? It’s fairly straightforward. Remember that the distance ∥Qk−U∥ is defined by looking at the difference in the densities on subsets A of Sn. By Xk, we will denote the ordering that results from shuffling k times.

We’ll begin by noting that we may partition the sequences of shuffles in which Xk is in A by their stopping times:

We will rewrite both of the terms on the right. Consider the first term: here’s where we use the fact that the orderings that result from a fixed stopping time are uniform:

We will rewrite the second term using the conditional probability:

Combining these two expressions gives

which is the same as saying

Now since P(Xk∈A|T>k) and U(A) are both probabilities, their values are between 0 and 1. Therefore, the absolute value of their difference is as well as we obtain:

Since this holds for every set A, we obtain the desired bound:

Riffle shuffles

Armed with this tool, we may study how fast a particular shuffling process converges to the uniform distribution by finding a strong uniform stopping rule and determining the probability that the stopping time is larger than k. We will apply this tool to a study of riffle shuffles, which model the usual way in which a deck of cards is shuffled.

To perform a riffle shuffle, we choose c cards from the top of the deck according to the binomial distribution. That is, the probability that we choosec cards is

We hold these cards in our left hand and the other n−c cards in our right. A card now falls from either our left or right hand with the probability that the card falls from one hand being proportional to the number of cards in that hand.

This description models the physical act of shuffling cards. However, an alternate way to describe this shuffle is like this: choose the c cards off the top according to the binomial distribution. For instance, here we choose c=3 cards.
Now choose, with equal probability, a set of c positions within the deck of n cards.
Place the chosen cards, in order, in these positions, and the remaining n−c cards, in order, in the other positions.

We will denote by R the probability density on Sn defined by one riffle shuffle. We wish to study Rk, the density that results after k riffle shuffles, and determine when it is sufficiently close to the uniform density to consider the deck well shuffled.

It turns out that it is easier to answer this question by considering what happens when we undo a riffle shuffle. To do this, simply walk through the deck labeling every card, with equal probability, with a “0” or “1.”
Then use the labels to divide the cards into two ordered groups and place the group labeled “0” on top.

This results in the inverse riffle shuffle:

The probability density R¯¯¯¯ defined by the inverse riffle shuffle is the same distance from the uniform distribution as the original riffle shuffle. To see this, think of π, an ordering of the cards, as defining a permutation of the n cards. If π¯¯¯ is the inverse permutation, then we haveR¯¯¯¯(π)=R(π¯¯¯). Given a set of permutations A, we will let A¯¯¯¯ be the set of inverses of A. We therefore have

which implies that ∥R¯¯¯¯k−U∥=∥Rk−U∥.

A stopping rule for inverse riffle shuffles

Now that we have seen that the densities defined by inverse riffle shuffles lie the same distance from the uniform density as those defined by riffle shuffles, we would like to develop a strong uniform stopping rule for inverse riffle shuffles. But first, let’s describe a means of enumerating inverse riffle shuffles.

Suppose we perform a sequence of k inverse riffle shuffles. In each shuffle, each card is labeled with a “0” or a “1.” If we concatenate the labels from each shuffle, then each card is labeled with a string of k 0’s and 1’s. (We usually call such strings k-bit strings.)

To summarize, a sequence of k inverse riffle shuffles defines an ordering of the n cards as well as a set of n k-bit strings. Conversely, if we choose an ordering of the cards π and a set of n k-bit strings, we may define a sequence of k inverse shuffles: begin with the standard ordering of the cards and perform inverse shuffles, based on the appropriate bit:

The ordering on the deck of cards that results is π.The stopping rule is simple: stop when the cards have distinct labels. To see that this is a strong uniform stopping rule, simply notice that the choices of an ordering π and a set of n k-bit strings are independent. Therefore, if B is a set of distinctk-bit strings and π1 and π2 are two orderings of the deck, then (π1,B) and (π2,B) give two sequences of inverse riffle shuffles that are equally likely and that lead to π1 and π2, respectively. Therefore, we are just as likely to see π2 as π1 as a result of a sequence of inverse riffle shuffles with stopping time k.

Now we’re in great shape. If T is the stopping time of a sequence of inverse riffle shuffles, we may apply our earlier result:

We’ll compute P(T>k), the probability that the stopping time is greater than k, by working instead with P(T≤k)=1−P(T>k). Suppose we have a sequence of k inverse riffle shuffles with T≤k (if T<k, just shuffle a few more times for a total of k shuffles). As before, this leads to an ordering π and a set of n distinct k-bit strings. The number of orderings π is n! and the number of n ordered distinct k-bit strings is n!(2kn) since there are 2k k-bit strings. This means that the number of sequences of k inverse riffle shuffles with a stopping time less than kis

Now the total number of sequences of k inverse riffle shuffles is the number of orderings π times the number of length n k-bit strings, which is n!(2k)n. This gives:

This leads to the estimate

With this in hand, let’s consider shuffling a typical deck of n=52 cards using riffle shuffles. We find the following bounds on the distance of Rk and U, which we will denote by d(k):

k d(k) 1 1.00 2 1.00 3 1.00 4 1.00 5 1.00 6 1.00 7 1.00 8 1.00 9 0.93 10 0.73 11 0.48 12 0.28 13 0.15 14 0.08 15 0.04 16 0.02 17 0.01 18 0.01 19 0.00

With this as our guide, we see that d(k) is relatively constant for small k but decreases exponentially for larger k. There is consequentially a region of transition where d(k) changes from roughly constant to decaying exponentially. It seems reasonable that some value k in the middle of this transition gives an appropriate number of shuffles to guarantee that the deck is sufficiently randomized. Using this model, it appears thatk=12would be a good recommendation for the number of shuffles.

Summary

A more sophisticated study enabled Diaconis and Bayer to improve this bound: for a deck of n=52 cards, they found

k d(k) 1 1.00 2 1.00 3 1.00 4 1.00 5 0.92 6 0.61 7 0.33 8 0.17 9 0.09 10 0.04

Based on this analysis, Diaconis has written that “seven shuffles are necessary and suffice to approximately randomize 52 cards.” Of course, our technique has just given an upper bound for the distance between Rk and U. In fact, J. Reeds, in an unpublished manuscript, introduced a technique to find a lower bound: ∥R6−U∥≥0.1. This lends further evidence to the fact that seven shuffles should be used. Please see the Postscript to this article for a further discussion. .Of course, we could use a computer to generate random orderings of the deck, but we still need a reliable method to ask the computer for the next ordering. Bridge Clubs originally swapped 60 cards at random, but Diaconis and Shahshahani showed that this is not enough to generate sufficiently random orderings.

Knuth describes a process that proceeds in stages beginning at i=1. Choose a random number j so that i≤j≤n and interchange the cards at positionsi and j. This generates the uniform probability density with 51 swaps.

A description of the current process using by Bridge Clubs is given by the website Bridge Hands.

Does it really matter? Yes! Martin Gardner describes some card tricks that rely on the fact that three riffle shuffles is not enough to generate random orderings. For example, suppose that a deck is shuffled three times and cut in between the shuffles. If a card is taken out, recorded, and put back in the deck in a different position, then that card can be determined almost all the time. De Bruijn also describes a similar trick.

The model we have adopted for the riffle shuffle seems reasonable, but how well does it model shuffles performed by a human? It depends on the human. Studies show that professional dealers drop single cards from one hand roughly 80% of the time and pairs about 18% of the time. Less experienced shufflers drop single cards about 60% of the time. Of course, when you’re playing Crazy Eights with a kid, the cards sometimes get thrown all over the room resulting in the uniform distribution after one toss!

Mathematical Card Deal Theory and it’s  Advantage