Correlation between two Decks of cards?

Question

I've written a program to simulate an overhand card shuffle.

Each card is numbered, with suit going from CLUBS, DIAMONDS, HEARTS, SPADES and the rank from Two up to Ten then Jack, Queen, King and Ace. Thus the Two of Clubs has a Number of 1, the Three of Clubs a 2 ....Ace of Clubs is 13... Ace of Spades is 52.

One of the methods to determine how shuffled the cards are is to compare it to an unshuffled card and see if the order of cards is correlated.

That is, I might have these of cards, with the unshuffled card for comparison:

Unshuffled	Shuffled	Unshuffled number	Shuffled number
Two of Clubs	Three of Clubs	1	2
Three of Clubs	Two of Clubs	2	1
Four of Clubs	Five of Clubs	3	4
Five of Clubs	Four of Clubs	4	3

The correlation by the Pearson method would be: 0.6

With a large set of cards (all 52) you might see patterns emerge. My Hypothesis is that after more shuffling you'll get less correlation.

However, there are lots of ways to measure correlation.

I've tried my hand at Pearson's correlation but I'm not sure if this is the right correlation to use in this situation.

Is this a suitable correlation measure? Is there a more suited measure?

Bonus Points I sometimes see this sort of data in my results:

Clearly there is some correlation, because there are multiple separate lines of with different gradients, but I don't know how you measure the separate 'trendlines'?

Answer 1

You can measure the relative level of correlation (or more precisely, the increasing level of randomness) using the Shannon entropy of the difference in face value between all pairs of adjacent cards.

Here's how to compute it, for a randomly shuffled deck of 52 cards. You start by looping once through the entire deck, and building a sort of histogram. For each card position $i=1,2,...,52$, calculate the difference in face value $\Delta F_{i} = F_{i+1} - F_{i}$. To make this more concrete, let's say that the card in the $(i+1)$th position is the king of spades, and the card in the $i$th position is the four of clubs. Then we have $F_{i+1} = 51$ and $F_{i} = 3$ and $\Delta F_{i} = 51-3 = 48$. When you get to $i=52$, it's a special case; you loop around back to the beginning of the deck again and take $\Delta F_{52} = F_{1} - F_{52}$. If you end up with negative numbers for any of the $\Delta F$'s, add 52 to bring the face value difference back into the range 1-52.

You will end up with a set of face value differences for 52 pairs of adjacent cards, each one falling into an allowed range from 1-52; count the relative frequency of these using a histogram (i.e., a one-dimensional array) with 52 elements. The histogram records a sort of "observed probability distribution" for the deck; you can normalize this distribution by dividing the counts in each bin by 52. You will thus end up with a series of variables $p_{1}, p_{2}, ... p_{52}$ where each one may take on a discrete range of possible values: {0, 1/52, 2/52, 3/52, etc.} depending upon how many pairwise face value differences ended up randomly in a particular bin of the histogram.

Once you have the histogram, you can calculate the Shannon entropy for a particular shuffle iteration as $$E = \sum_{k=1}^{52} -p_{k} ln(p_{k})$$ I have written a small simulation in R to demonstrate the result. The first plot shows how the entropy evolves over the course of 20 shuffle iterations. A value of 0 is associated with a perfectly ordered deck; larger values signify a deck which is progressively more disordered or decorrelated. The second plot shows a series of 20 facets, each containing a plot similar to the one that was originally included with the question, showing shuffled card order vs. initial card order. The 20 facets in the 2nd plot are the same as the 20 iterations in the first plot, and they are also color coded the same as well, so that you can get a visual feel for what level of Shannon entropy corresponds to how much randomness in the sort order. The simulation code that generated the plots is appended at the end.

library(ggplot2)

# Number of cards
ncard <- 52 
# Number of shuffles to plot
nshuffle <- 20
# Parameter between 0 and 1 to control randomness of the shuffle
# Setting this closer to 1 makes the initial correlations fade away
# more slowly, setting it closer to 0 makes them fade away faster
mixprob <- 0.985 
# Make data frame to keep track of progress
shuffleorder <- NULL
startorder <- NULL
iteration <- NULL
shuffletracker <- data.frame(shuffleorder, startorder, iteration)

# Initialize cards in sequential order
startorder <- seq(1,ncard)
shuffleorder <- startorder

entropy <- rep(0, nshuffle)
# Loop over each new shuffle
for (ii in 1:nshuffle) {
    # Append previous results to data frame
    iteration <- rep(ii, ncard)
    shuffletracker <- rbind(shuffletracker, data.frame(shuffleorder,
                            startorder, iteration))
    # Calculate pairwise value difference histogram
    freq <- rep(0, ncard)
    for (ij in 1:ncard) {
        if (ij == 1) {
            idx <- shuffleorder[1] - shuffleorder[ncard]
        } else {
            idx <- shuffleorder[ij] - shuffleorder[ij-1]
        }
        # Impose periodic boundary condition
        if (idx < 1) {
            idx <- idx + ncard
        }
        freq[idx] <- freq[idx] + 1
    }
    # Sum over frequency histogram to compute entropy
    for (ij in 1:ncard) {
        if (freq[ij] == 0) {
            x <- 0
        } else {
            p <- freq[ij] / ncard
            x <- -p * log(p, base=exp(1))
        }
        entropy[ii] <- entropy[ii] + x
    }
    # Shuffle the cards to prepare for the next iteration
    lefthand <- shuffleorder[floor((ncard/2)+1):ncard]
    righthand <- shuffleorder[1:floor(ncard/2)]
    ij <- 0
    ik <- 0
    while ((ij+ik) < ncard) {
        if ((runif(1) < mixprob) & (ij < length(lefthand))) {
            ij <- ij + 1
            shuffleorder[ij+ik] <- lefthand[ij]
        }
        if ((runif(1) < mixprob) & (ik < length(righthand))) {
            ik <- ik + 1
            shuffleorder[ij+ik] <- righthand[ik]
        }
    }
}
# Plot entropy vs. shuffle iteration
iteration <- seq(1, nshuffle)
output <- data.frame(iteration, entropy)
print(qplot(iteration, entropy, data=output, xlab="Shuffle Iteration", 
            ylab="Information Entropy", geom=c("point", "line"),
            color=iteration) + scale_color_gradient(low="#ffb000",
            high="red"))

# Plot gradually de-correlating sort order
dev.new()
print(qplot(startorder, shuffleorder, data=shuffletracker, color=iteration,
            xlab="Start Order", ylab="Shuffle Order") + facet_wrap(~ iteration,
            ncol=4) + scale_color_gradient(low="#ffb000", high="red"))

Answer 2

I know that this post is almost 4 years old, but I am a hobbyist cryptanalyst, and have been studying playing card ciphers. As a result, I have come back to this post over and over to explain deck shuffling as a source of entropy for randomly keying the deck. Finally, I decided to verify the answer by stachyra by shuffling the deck by hand, and estimating the deck entropy after each shuffle.

TL;DR, to maximize deck entropy:

• For only riffle shuffling, you need 11-12 shuffles.
• For cutting the deck first then riffle shuffling, you only need 6-7 cut-and-shuffles.

First off, everything that stachyra mentioned for calculating Shannon entropy is correct. It can be boiled down this way:

1. Numerically assign a unique value to each of the 52 cards in the deck.
2. Shuffle the deck.
3. For n=0 to n=51, record each value of (n - (n+1) mod 52) mod 52
4. Count the number of occurrences of 0, 1, 2, ..., 49, 50, 51
5. Normalize those records by dividing each by 52
6. For i=1 to i=52, calculate -p_i * log(p_i)/log(2)
7. Sum the values

Where stachyra makes one subtle assumption, is that implementing a human shuffle in a computer program is going to come with some baggage. With paper-based playing cards, as they get used, oil from your hands transfers to the cards. Over an extended time, due to oil buildup, cards will begin sticking together, and this will end up in your shuffle. The more heavily used the deck, the more likely two or more adjacent cards will stick together, and the more frequently it will happen.

Further, supposed the two of clubs and jack of hearts stick together. They may end up stuck together for the duration of your shuffling, never separating. This could be imitated in a computer program, but this isn't the case with stachyra's R routine.

Also, stachyra has a manipulation variable "mixprob". Without fully understanding this variable, it is a little bit of a black box. You could incorrectly set it, affecting the results. So, I wanted to make sure his intuition was correct. So I verified it by hand.

I shuffled the deck 20 times by hand, in two different instances (40 total shuffles). In the first instance, I just riffle shuffled, keeping the right and left cuts close to even. In the second instance, I cut the deck deliberately away from the middle of the deck (1/3, 2/5, 1/4, etc.) before doing an even cut for the riffle shuffle. My gut feeling in the second instance was that by cutting the deck before shuffling, and staying away from the middle, I could introduce diffusion into the deck more quickly than stock riffle shuffling.

Here are the results. First, straight riffle shuffling:

And here is cutting the deck combined with riffle shuffling:

It seems that entropy is maximized in about 1/2 the time of the claim by stachyra. Further, my intuition was correct that cutting the deck deliberately away from the middle first, before riffle shuffling did introduce more diffusion into the deck. However, after about 5 shuffles, it didn't really matter much anymore. You can see that after about 6-7 shuffles, entropy is maximized, versus the 10-12 as the claim made my stachyra. Could it be possible that 7 shuffles is sufficient, or am I being blinded?

You can see my data at Google Sheets. It is possible that I recorded a playing card or two incorrectly, so I can't guarantee 100% accuracy with the data.

It's important that your findings are also independently verified. Brad Mann, from the Department of Mathematics at Harvard University, studied how many times it would take to shuffle a deck of cards before the predictability of any card in the deck is completely unpredictable (Shannon entropy is maximized). His results can be found in this 33-page PDF.

What's interesting with his findings, is that he is actually independently verifying a 1990 New York Times article by Persi Diaconis, who claims that 7 shuffles are sufficient for thoroughly mixing a deck of playing cards via the riffle shuffle.

Brad Mann walks through a few different mathematical models in shuffling, including Markov chains, and comes to the following conclusion:

This is approximately 11.7 for n=52, which means that, according to this viewpoint, we expect on average 11 or 12 shuffles to be necessary for randomizing a real deck of cards. Note that this is substantially larger than 7.

Brad Mann just independently verified stachyra's result, and not mine. So, I looked closer at my data, and I discovered why 7 shuffles is not sufficient. First off, the theoretical maximum Shannon entropy in bits for any card in the deck is log(52)/log(2) ~= 5.7 bits. But my data never really breaks much above 5 bits. Curious, I created an array of 52 elements in Python, shuffled that array:

>>> import random
>>> r = random.SystemRandom()
>>> d = [x for x in xrange(1,52)]
>>> r.shuffle(d)
>>> print d
[20, 51, 42, 44, 16, 5, 18, 27, 8, 24, 23, 13, 6, 22, 19, 45, 40, 30, 10, 15, 25, 37, 52, 34, 12, 46, 48, 3, 26, 4, 1, 38, 32, 14, 43, 7, 31, 50, 47, 41, 29, 36, 39, 49, 28, 21, 2, 33, 35, 9, 17, 11]

Calculating its entropy-per-card yields about 4.8 bits. Doing this a dozen times or so shows similar results varying between 5.2 bits and 4.6 bits, with 4.8 to 4.9 as the average. So looking at the raw entropy value of my data isn't enough, otherwise I could call it good at 5 shuffles.

When I look closer at my data, I noticed the number of "zero buckets". These are buckets where there is no data for deltas between card faces for that number. For example, when subtracting the value of two adjacent cards, there is no "15" result after all 52 deltas have been calculated.

I see that it eventually settles around 17-18 "zero buckets" around 11-12 shuffles. Sure enough, my shuffled deck via Python averages 17-18 "zero buckets", with a high of 21 and a low of 14. Why 17-18 is the settled result, I can't explain ... yet. But, it appears that I want both ~4.8 bits of entropy AND 17 "zero buckets".

With my stock riffle shuffling, that's 11-12 shuffles. With my cut-and-shuffle, that's 6-7. So, when it comes to games, I would recommend cut-and-shuffles. Not only does this guarantee that the top and bottom cards are getting mixed into the deck on each shuffle, it's also just plain quicker than 11-12 shuffles. I don't know about you, but when I'm playing card games with my family and friends, they're not patient enough for me to perform 12 riffle shuffles.