Shuffling a Deck: A Mathematical Analysis

1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, 20, 30, 39, 54, 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 110, 20, 100, 7, 14, 130, 18, 36, 68, 138, 46, 60, 28

Contents

  1. Introduction
  2. Anatomy of a Shuffle
  3. Defining a Shuffle
  4. Analysis
  5. Other Thoughts

Introduction

This page will discuss the curious properties of a sequence of numbers; a sequence which is simply computed, yet strangely complex. I'm going to try to keep the math as readable as possible; you should not need a Ph.D. in order to understand this (though it never hurts). If you find there is a part you don't understand, feel free to move on past it, as it is most likely just an interesting aside for those who have the proper background. The important parts have been kept as simple as possible. That said, there's a lot of math here all the same. You have been warned.

Before we can tak about the numbers in this sequence, we need to first talk about how they are calculated. These numbers are listed as sequence A002326 in the On-Line Encyclopedia of Integer Sequences, which in the densest possible language, defines them as the "least m such that n+1 divides 2m-1."[1] Even to the mathematically inclined, this definition may not be very meaningful (though we'll see where it comes from, and how we can use it to our advantage, later). Fortunately, there is another, much simpler and more meaningful way to define the sequence; those numbers which answer the question "given a deck of n unique cards (where n is an even number), how many times must one shuffle the deck before it returns to its original configuration?"

Unfortunately, this definition is not yet quite without ambiguity. What exactly does it mean to "shuffle" a deck? Experience tells us that shuffling a deck effectively randomizes it, and that further shuffling only causes it to go into a different, equally random state. This experience seems to imply that one would expect it to take roughly as many shuffles as there are permutations of the deck (n!) before it would return to its original configuration, and even then we would not be able to guarantee that it ever would. Our intuition, however, is based on the way we shuffle cards with our hands, which is far from consistent. Instead, if we are to make any progress here, we must talk about a "perfect shuffle."

Anatomy of a Shuffle

Our first attempt to define a "perfect shuffle" will be to say that it is one in which the deck is split in exactly half (this is the reason for restricting the deck to even numbers of cards[2]), each half being perfectly interwoven with the other, one card at a time. This is very close to our final definition, but there is one subtle point that prevents us from proceeding with it quite yet. When I split the deck in twain, I have an option of which half of the deck I start with when I interweave them. Say that I consistently put the top half of the deck (cards 1 through n/2-1) in my right hand, and the bottom half (cards n/2 through n) in my left hand. We can then call a shuffle where I start interweaving with the top card in my right hand (card 1) a right handed shuffle, and a shuffle where I start with the top card in my left hand (card n/2) a left handed shuffle. Let's see how these shuffles look with a 12 card deck.

Right Handed Shuffle
Original Deck 1 Shuffle 2 Shuffles 3 Shuffles
1
2
3
4
5
6
7
8
9
10
11
12
1
7
2
8
3
9
4
10
5
11
6
12
1
4
7
10
2
5
8
11
3
6
9
12
1
8
4
11
7
3
10
6
2
9
5
12
Left Handed Shuffle
Original Deck 1 Shuffle 2 Shuffles 3 Shuffles
1
2
3
4
5
6
7
8
9
10
11
12
7
1
8
2
9
3
10
4
11
5
12
6
10
7
4
1
11
8
5
2
12
9
6
3
5
10
2
7
12
4
9
1
6
11
3
8

You can see that the top and bottom cards don't move with the right handed shuffle, whereas the left handed shuffle causes all the cards to change position. Other than this, they appear to work mostly the same; and they are, in fact, identical. A single right handed shuffle is the exact equivalent of removing the top and bottom cards from the deck, performing a left-handed shuffle, and then replacing the removed cards. From this fact, it's easy to see (you can try it for yourself using real cards) that a deck of n cards being right handed shuffled will return to its original order in the same number of shuffles as a deck of n-2 cards being left handed shuffled. Because the right handed shuffle has this 2 card "overhead" associated with it, we declare it to be the inferior shuffle, and concentrate solely on the left handed shuffle.[3]

Performing the Shuffle

It is obvious that shuffling the cards by hand is not an option; such an endeavour would take far too long and be too prone to error. Instead, we must employ the aid of computers, and we have two options. We can have a computer simulate the shuffling of a deck of n card and check after each shuffle if the deck is back in order. Such a program is fairly straightforward to write, but such an algorithm is necessarily at best an O(n2) affair, as we have n cards to shuffle, and as we will soon see, roughly n shuffles are required per deck.[4] This is clearly too slow if we want to figure out the answer for large decks (a 2.8 GHz processor takes roughly a half hour to finish shuffling a 500,000 card deck). Instead, we can use the mathematical definition from above (the "least m such that n+1 divides 2m-1") and write a program that does something like this:

for (n = 0; true; n++) {
   for (m = 1; !((Math.pow(2,m)-1).mod(2*n+1) == 0); m++) {
   }
   out.println(n + ", " + m);
}

At first, this runs very fast, but quickly it runs into problems. First, the values for 2m-1 become much, much larger than a double variable allow (m can not exceed the number of bytes the variable takes up). This can be overcome by using container objects for large numbers, like the BigInteger class in Java. These container objects are also very slow, and due to the internals of how math is performed with them, are in practice slower than the simulation method itself!

However, not all hope for a quick algorithm is lost! Multiplication in modular arithmetic is not very intuitive, but there exists some multiplicative identities which are useful in the quest for an O(n) algorithm. Without getting too deep into why this works (the explanation of modular arithmetic is beyond the scope of this treatment), the following function can be written which in equivalent to the one above:

for (n = 0; true; n++) {
   a=1;
   m=0;
   do {
      a*=2;
      a%=(n+1);
      m++;
   }
   while (a != 1);
   out.println(n + ", " + m);
}

This is not only an O(n) algorithm in theory, but each operation in it is O(1) making it an O(n) algorithm in practice. After running this for a few days, the first 10 million numbers in the sequence were found, which we can now examine.

Analysis

Figure 1
The first 50 numbers.

When we look at Figure 1, a graphical representation of the first 50 numbers in this sequence (remember, we are skipping odd numbered deck sizes, so the 50th number is for a 100 card deck), we see very little in the way of order or pattern. One thing that seems clear, and that is that this sequence appears to be essentially random, in that it is not possible to find, or even estimate, the value of the nth number in the sequence given numbers 1 through n-1[5]. We can note, through this seeming randomness, that the number of shuffles required to return our deck to its original order tends to increase with the deck size, and that it seems to also not exceed the deck size (that is to say that an n card deck takes at most n shuffles to restore its order). Proving that no deck will require more than n shuffle is non-trivial, but it provides a lot of insight into what we'll see happening later.

Figure 2: Click for larger version.
The first 10 million numbers.

Perhaps the easiest way to convince yourself that the maximum number of shuffles a deck needs is equal to its size is to realize that any card that starts in position x before a shuffle will be moved to position y in the deck afterwards, regardless of its position in the original deck (in the left handed shuffle example, the "5" in the original deck moves to the 10th spot after the first shuffle. The "9" that took its place after the first shuffle is also moved to the 10th spot after the second shuffle). We can thus define a chain of positions which the cards occupy in order. For the 12 card deck example above, this chain is 1-2-4-8-3-6-12-11-9-5-10-7-1-2-4-8-3-6.... Upon repeated shuffling, cards will follow this loop, moving one step along it with each shuffle, but keeping their order. Thus, after a maximum of n steps around this loop, the cards will all be back to where they started (sort of like a game of musical chairs). The mechanics of the shuffle demand that this loop repeat with a period of no more than n (for it to do otherwise would require a card in spot x to be able to move to more than one possible spot after a shuffle, something that is disallowed by the very definition of a "perfect shuffle"). To put this in a far more concise, though slightly more esoteric way, we can say that shuffling is a bijective mapping of the cards. One final note is that though this shows that the number of shuffles can never exceed n, it may still be less than n. One can imagine, for example, two non-interacting loops of n/2 cards, which would require n/2 shuffles to traverse.

Figure 3: Click for larger version.
Shuffles required for the first 10 million decks, as a percentage of deck size.

We can further abstract this by thinking of the deck not as a linear array of n cards, but as a ring of n+1 cards (the "+1" is hard to explain, and it's not really worth bothering with the why, but suffice it to say it's one of those things you stick into your model "just because it makes it work." A card moves around this ring by by 2m-1 spaces on the mth shuffle (you can see this by following the cards in the example of a left handed shuffle above.[6] It's from this that the earlier, mathematical definition of "the nth element of the sequence contains the least m such that n+1 divides 2m-1." comes.[7] A card will circle the ring over and over until the total distance moved is a multiple of the ring's size.

Now we examine a larger section of the sequence, the first 10 million numbers, as shown in Figure 2. Suddenly, whereas before we saw only chaos, patterns erupt. The most striking are the radial lines emanating from the origin. Remember the discussion of the loops that the cards traveled around as the deck was shuffled. The topmost line in Figure 2 (which has a slope of 1) corresponds to a deck which had a loop that spanned all n cards in that deck, thus requiring n shuffles for the cards to return to their initial positions. The line directly below that has a slope of 2, indicating those decks which returned to their original configurations after only n/2 shuffles. These decks are the ones where there are two independent loops of length n/2 that the cards traverse.

Figure 4: Click for larger version.
The first 10 million numbers on a log plot.

Figure 3 shows the exact same data as Figure 2, but each data point has been divided by the size of the deck that created it. The resulting graph is really nothing more than a coordinate transformation of Figure 2, showing now the values of the slopes of the lines previously seen. Easily visible are lines for all values of 1/k, where k is an integer, corresponding to decks with k independent loops of size n/k. Also visible are a number of lines at various rational values. The points that lie along the slope of 2/5 would correspond to decks with three independent loops, one of which has n/5 elements, the other two of which have 2*n/5 elements. Cards will circle evenly around the small loop twice while other cards circle the larger loops once. Also visible here, though, are many lines that do not have such nice rational number slopes, especially visible between the slope values of 0.45 and 0.5. Unfortunately, I still am lacking in an explanation of how these came about.

Finally, we can look at Figure 4, which is the same data as Figure 2, only this time with the y-axis on a logarithmic scale. By using this scale, the straight lines of Figure 2 have been changed into curves, making yet one more feature a little easier to visually identify, the existence of horizontal lines. One such especially prominent line is at 150 shuffles. I'm not sure exactly why it is that many, many decks, across such a large range of deck sizes, require exactly 150 shuffles to return to their original position. As of now, I can only theorize that it implies that the value of 2149 (which is roughly 7.17 · 1044) has a much larger number of factors than other numbers of its order of magnitude, though I cannot say as to why that is.

Other Thoughts

Figure 5: Click for larger version.
The effect of deck size on the expectation value of shuffles. The red line is a power fit.

One possible application of this is sequence may be of importance to magicians. A slight-of-hand artist may become skilled at repeatedly and quickly performing one of the "perfect shuffles" described (in magic parlance, this is what is known a "Faro Shuffle," with left and right handed shuffles being know instead as in and out shuffles, respectively. Could such a magician use this skill to make a deck appear to be well shuffled when it has in fact returned to its original order? Well, for a standard deck of 52 cards, left handed shuffling would require 52 shuffles before this occurred, something that would strain both the magician's precision as well as the audience's patience. By instead using a right handed shuffle, however (remember that a right handed shuffle of 52 cards is equivalent to a left-handed shuffle of 50 cards), the deck would return in only 8 shuffles, which is just right to make the deck look really random, but not too much to be impractical to perform. So if nothing else, we have learned never to let a magician shuffle a deck exactly 8 times.

One other interesting pattern emerges. For a deck of 2k-2 cards for a left handed shuffle, or a deck of 2k cards for a right handed shuffle, where k is an integer, we find that the deck always takes k shuffles to restore its order. Indeed, it is rather trivial to show that the least m such that 2k-1 (the size of the deck plus 1) divides 2m-1 must be when m = k.

On a final note about the calculation of these numbers, we can examine the performance of our algorithm. The act of performing a single shuffle requires O(n) operations. By doing a simple average of all 10 million values that make up Figure 3, we are able to find that a deck will need to be shuffled 0.159102n times on average, giving a time of 0.159102·O(n) to perform the calculation of a single deck of size n. Another way to view this is that the average deck takes only one eighth as much time to shuffle back to order as the worst case deck (the deck which requires n shuffles) takes. This analysis, however, is a little simplistic, as the number of shuffles an average deck takes to return to its original position is dependant upon n (as n increases, the primes become more sparse, and so decks are increasingly likely to need fewer than the maximum shufflings). This dependence is shown in Figure 5, which shows the average number of shuffles per deck size in blue, and a power fit in red.[8] This power fit has a formula of 0.444n−0.1268+0.0987. As such, each deck will take not 0.159102·O(n) time, but instead (0.444n−0.1268+0.0987)·O(n) time, or 0.444O(n)0.8732+0.0987O(n) time, much better than the O(n) time it would have taken if the number of shuffles a deck needed scaled linearly.

1 The Integer Sequence Database actually uses "least m such that 2n+1 divides 2m-1." (emphasis added). However, throughout this analysis, I use "n" to refer not to the index of the number in the sequence, but to the number of cards in the deck that gives the number, which is a factor of two different. For consistency within this treatment, as opposed to with the Integer Sequence Database, I have modified their definition. Return to main text

2 If a deck were to have an odd number of cards (2n+1), we would see that the odd card out would simply stay on the top or bottom of the deck (depending on how we defined the shuffle), leaving only 2n of the 2n+1 cards actually being shuffled. This is both redundant and not very interesting, so we ignore it all together and stick with the even numbered decks. Return to main text

3 It doesn't really matter in the long run which shuffle we choose. Choosing one over the other would simply offset the sequence by two cards; in math we would say that a(nright - 2) = a(nleft). Technically, both are equally good, what is most important is that we choose one type of shuffle and use it consistently. Return to main text

4 In actuality, as discussed in the Other Thoughts section, the number of shuffles required for a deck of n cards tends towards about 0.1 shuffles per card, so the simulation of a full deck shuffle is really quite a bit quicker than O(n2). However, the numerical method also benefits from this fact, and so is still at the least a factor of n faster than the simulation method. Return to main text

5 I, sadly, do not have a proof for this statement, nor do I even know if it is provable, but all my observations of the sequence lead me to believe that this is true nonetheless. Return to main text

6 This ring is distinct from the loops of the preceding paragraph. The two are related, but should not be confused for one another (nor with the abstract mathematical idea of a ring, this is an entirely new meaning for the word). Return to main text

7 The card moves around the ring 2m-1 spaces each shuffle. If we write this as a summation, we can see that after adding n terms, that it will have moved 2n-1 spaces in total. This is easiest to see if you try writing out the summation in binary (1 + 10 + 100 + 1000... = 1e0 + 1e1 +1e2 +1e3 + ... + 1e(n-2) + 1e(n-1) = 1111... = 2n-1. Return to main text

8 Figure 5 is found by using a moving average (plotting the average number of shuffles that decks of size n-c through n+c took) where c is equal to 10,000. The reason for such a high value of c is both because it is needed in order to smooth the data to something that can be fit (the original function in Figure 3 has a standard deviation of 0.24, almost a quarter of its range) and also because with 10 million data points to work with, we can afford to average 20,000 at a time without losing much resolution. Return to main text