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:
- Numerically assign a unique value to each of the 52 cards in the deck.
- Shuffle the deck.
- For n=0 to n=51, record each value of (n - (n+1) mod 52) mod 52
- Count the number of occurrences of 0, 1, 2, ..., 49, 50, 51
- Normalize those records by dividing each by 52
- For i=1 to i=52, calculate -p_i * log(p_i)/log(2)
- 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)]
>>> 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.