What is the optimum number of shuffles to randomize any size deck of cards?
For a standard deck of 52 cards, the famous answer, of course, is seven. Wikipedia discusses this answer and presents an alternative.
I assume larger decks would require more shuffles. Is there a formula or a rule of thumb that correlates the size of the deck with the number of shuffles required for good randomization?
You mean minimum, not optimum. Extra shuffles don’t bring the cards back into order. They just randomize them further.
Perfectly consistent shuffles will bring the deck back to its initial position eventually. For example, a perfect alternating shuffle in which the top and bottom cards remain in position will bring the deck back to its exact initial position after exactly 8 shuffles. (I’ve heard that some magicians can do this! To be clear, the shuffle just described changes the deck 1-2-3-4-5-… to 1-27-2-28-3-…) The other way to do a perfectly alternating shuffle (change deck to 27-1-28-2-29-…) will restore the deck after, I think, 52 shuffles.
More than once I’ve heard the claim that seven imperfect shuffles is “optimal” (in the sense that an 8th shuffle would leave the deck less random). I don’t know if there’s any basis to it; perhaps the idea is derived by simulating imperfect shuffles, but of course some human shufflers are more imperfect than others.
The idea that an eighth shuffle is bad might derive from the fact that a magician can restore the deck with 8 perfect shuffles, but of course after seven such perfect shuffles, the deck won’t be random at all. (It will be 1-3-5-7-9-…)
When you shuffle, a card needs to have had a chance to have moved to any other position in the deck. When you halve and merge, the card could only have moved halfway. Halve again and the card could have moved 75% of the way. After six shuffles, it could have moved 98.4375%. Multiplied by 52 cards, that’s only 51.1875, you need one more shuffle to get a number that rounds up to 52 (51.59375).
Your formula, assuming I’m right, would be:
(1 - 0.5^n) * x >= x - 0.5
Where n is the number of shuffles and x is the number of cards. Solve for n.
I presume that we’re talking about imperfect shuffles. Perfect shuffles are simply a bad idea for randomization, no matter how many of them are used. I don’t believe the claim that seven imperfect shuffles is optimal. Do you have a citation for that?
And if the cards are in such a state that an additional shuffle will make them apparently less random, then they weren’t ever random to begin with. Without looking at the cards and making decisions about them, you can never get them any less random.
In the links from the wikipedia page, the shuffles they use are the Gilbert-Shannon-Reeds (GSR) riffle shuffle. A deck is divided into two piles (by the binomial distribution), of sizes A and B, and when combined the probability that the next card to to drop from the A or B pack is A/(A+B) or B/(A+B) respectively (so you don’t have a deterministic shuffle).
This PDF link (from the wiki article) shows that 7 GSR shuffles are not enough in all cases to be equivalent to a uniformly shuffled 52 card deck. They don’t seem to say how many shuffles are needed.
No. 52. I’ll demonstrate.
x -> 2x when x < 27
x -> 2x-53 when x > 26
Therefore,
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 11 -> 22 -> 44 -> 35 -> 17 -> 34 -> 15 -> 30 -> 7 -> 14 -> 28 -> 3 -> 6 -> 12 -> 24 -> 48 -> 43 -> 33 -> 13 -> 26 -> 52 -> 51 -> 49 -> 45 -> 37 -> 21 -> 42 -> 31 -> 9 -> 18 -> 36 -> 19 -> 38 -> 23 -> 46 -> 39 -> 25 -> 50 -> 47 -> 41 -> 29 -> 5 -> 10 -> 20 -> 40 -> 27 -> 1
)And, athough we need not digress into Kolmogorov Complexity theory, the simple answer to your 2nd question is that “random” is, at best, ambiguous in this context.
As to a citation for the claim that an 8th shuffle may reduce “randomness,” I don’t have one. I heard the claim from a PhD student in information theory describing a paper he’d just read, and I’ve heard the claim elsewhere as well. But I’m quite prepared to believe these claimants (incl. the PhD student) are misinformed. Note however that it isn’t completely implausible: after all, the deck may look quite random after 4 of the magician’s shuffle, even though 4 more restore it.
A perfect shuffle is not a randomization device. It changes the ordering in a very specific and ordered manner. Not surprisingly then, it turns out that there is a cycle within the group of all the transpositions of the cards so that the 52nd power of a perfect shuffle is the identity transposition. An inperfect shuffle doesn’t have any simple structure though. Note that there are a vast number of possible imperfect shuffles. I can’t see any way that eight imperfect shuffles would be less random on average than seven of them.
Let me repeat my position. The claim is one of I’ve heard, not made. Nevertheless:
If one models an “imperfect shuffle” as a “noisy” perfect shuffle, then the model might produce a result similar to that in the peculiar claim. My guess is that the noise (deviation from “perfection”) would have to be rather small to see the effect: certainly smaller than the noise in my own imperfect shuffles.
To save a round of pointless surrejoinders, let me point out the the claim almost certainly holds if the modeled imperfect shuffle is the “magician’s shuffle” (defined upthread) with a sufficently tiny level of noise.
So you’re defining something like an almost perfect shuffle which is a perfect shuffle with one (or whatever) change and you’re claiming that it might satisfy this condition of having more order after eight shuffles than after seven shuffles. That’s possible, I suppose, but I doubt it, based on my knowledge of randomization. I’m trying to answer the question in the OP, not some odd variation of it. The OP is presumably talking about imperfect shuffles, not perfect ones or almost perfect ones (assuming that such things actually exist). For imperfect shuffles, eight shuffles will be more random than seven shuffles.
If you ignore suits, there are only 13 unique cards. An imperfect shuffle could get you farthest from having the cards ordered by number near 6 or 7 (roughly 13/2 shuffles). Going to 8 shuffles then takes you closer to 13, where the cards are ordered again (although the ordering is different than what you started with when you include suits).
The best way to randomize a deck of cards (or anything else) is to not do the same thing over and over. Here’s a technique that will quickly randomize them. Admittedly, most regular card players are going to be irritated by you doing this, but it will be the surest way to randomize them. In the following, when I say shuffle the cards together, assume that I always mean imperfect shuffles except when I mention otherwise:
Shuffle the cards once. Splilt the deck into a half dozen (or so) smaller piles. Grab random pairs of the piles and, for each pair, shuffle the two piles together. Shuffle all the remaining piles together. Shuffle the cards again. Do this half a dozen times. Feel free to intersperse with other ways of randomization. For instance, grab a few cards from the top and push them into the middle. Grab a few cards from the bottom and push them into the middle. Or lay out a dozen or so piles from the deck and randomly stack them together again.
The reason that most card players like ordinary imperfect shuffles is that it’s a single, fast way that in most cases is good enough. They don’t like strange techniques that they haven’t seen before. They expect (possibly incorrectly) that the people that they play with aren’t dexterous enough to do a perfect shuffle. They expect (possibly incorrectly) that a single imperfect shuffle will be good enough.
Once when I was bored, I took a deck of cards in order, counted out exactly 26, and then played out cards one at a time, alternately from each side of the deck, in such a way as to exactly simulate a perfect shuffle. I repeated this process exactly 14 times, and ended up with the deck back in order.
Or at least, that’s what I thought happened, though I’m having trouble reconciling that with your convincing demonstration there. It’s possible that, first of all, I miscounted the number of shuffles I made, and second of all, that I got the cards into a different state than the original, but one which was equally-ordered.
Out of curiosity I tried to reconstruct what your 14th shuffle produced. I may as well report the results.
(I don’t know what SD policy is on long boring posts, but at least mine is more factual than the typical collection of political or global-warming half-truths over in the GD forum. 
To make this message look less tedious, I’ll place the details inside a “Spoiler”.)
(simulated 52 cards, but here display just first 14.)
0: 1 2 3 4 5 6 7 8 9 10 11 12 13 1 SSSSSSSSSSSSSH
1: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 DSDSDSDSDSDSDS
2: 1 1 1 1 2 2 2 2 3 3 3 3 4 4 CDHSCDHSCDHSCD
3: 7 1 7 1 8 1 8 1 8 2 8 2 9 2 HCSDCHDSHCSDCH
4: 10 7 4 1 11 7 4 1 11 8 4 1 11 8 SHDCCSHDDCSHHD
5: 5 10 2 7 12 4 9 1 6 11 2 7 12 4 SSHHHDDCCCSSSH
6: 3 5 8 10 13 2 5 7 10 12 1 4 6 9 DSDSDHCHCHSDSD
7: 2 3 4 5 7 8 9 10 12 13 1 2 3 5 CDHSCDHSCDDHSC
8: 8 2 9 3 10 4 11 5 13 7 1 8 2 9 CCDDHHSSCCCDDH
9: 11 8 5 2 12 9 6 3 13 10 7 4 1 11 CCCCDDDDHHHHHS
10: 12 11 9 8 6 5 3 2 13 12 10 9 7 6 HCHCHCHCSDSDSD
11: 13 12 11 11 10 9 8 8 7 6 5 5 4 3 DHSCDHSCDHSCDH
12: 7 13 6 12 5 11 4 11 4 10 3 9 2 8 CDDHHSSCCDDHHS
13: 10 7 3 13 9 6 2 12 9 5 2 11 8 4 HCHDSDSHCHCSDS
14: 12 10 8 7 5 3 1 13 11 9 8 6 4 2 DHSCDHSDHSCDHS
15: 6 12 4 10 3 8 1 7 12 5 11 3 9 1 HDSHCSDCSDCHDS
16: 10 6 2 12 8 4 1 10 6 3 12 8 5 1 DHSDHSCHSCHSCD
17: 5 10 1 6 11 2 7 12 3 8 13 4 9 1 HDSHDSHDSHDSHC
18: 9 5 1 10 6 1 10 6 2 11 7 2 11 7 SHDDCSSHDDCSSH
19: 5 9 1 5 10 1 5 10 1 6 10 1 6 10 DSCHCDSDHCHSDS
20: 3 5 7 9 12 1 3 5 7 10 12 1 3 5 CDHSCCDHSCDDHS
21: 8 3 10 5 13 7 2 9 4 12 6 1 8 3 HCSDCHCSDCHCSD
22: 11 8 5 3 13 10 8 5 2 13 10 7 4 2 DHSCHSCDHCDHSC
23: 6 11 3 8 13 5 11 3 8 13 5 10 2 8 CDDHSSCCDHHSSC
24: 10 6 2 11 7 3 12 8 4 13 9 5 1 11 CCCDDDHHHSSSSC
25: 12 10 8 6 4 2 13 11 9 7 5 3 1 12 CCCCCCDDDDDDDH
26: 13 12 11 10 9 8 7 6 5 4 3 2 1 13 CCCCCCCCCCCCCD
27: 13 13 12 12 11 11 10 10 9 9 8 8 7 7 HCHCHCHCHCHCHC
28: 13 13 13 13 12 12 12 12 11 11 11 11 10 10 SHDCSHDCSHDCSH
29: 7 13 7 13 6 13 6 13 6 12 6 12 5 12 DSCHSDHCDSCHSD
30: 4 7 10 13 3 7 10 13 3 6 10 13 3 6 CDHSSCDHHSCDDH
31: 9 4 12 7 2 10 5 13 8 3 12 7 2 10 CCDDDHHSSSCCCD
32: 11 9 6 4 1 12 9 7 4 2 13 10 8 5 HCHCHDSDSDCHCH
33: 12 11 10 9 7 6 5 4 2 1 13 12 11 9 SHDCSHDCSHHDCS
34: 6 12 5 11 4 10 3 9 1 7 13 6 12 5 SSHHDDCCSSSHHD
35: 3 6 9 12 2 5 8 11 1 4 7 10 13 3 SSSSHHHHDDDDDC
36: 2 3 5 6 8 9 11 12 1 2 4 5 7 8 DSDSDSDSCHCHCH
37: 1 2 3 3 4 5 6 6 7 8 9 9 10 11 HDCSHDCSHDCSHD
38: 7 1 8 2 9 3 10 3 10 4 11 5 12 6 SHHDDCCSSHHDDC
39: 4 7 11 1 5 8 12 2 5 9 12 3 6 10 DSDHCHCDSDSCHC
40: 2 4 6 7 9 11 13 1 3 5 6 8 10 12 HDCSHDCHDCSHDC
41: 8 2 10 4 11 6 13 7 2 9 3 11 5 13 DHCDSCHSCHSDHC
42: 4 8 12 2 6 10 13 4 8 11 2 6 9 13 HDCHDCSDCSDCSH
43: 9 4 13 8 3 12 7 2 11 6 1 10 5 13 DHCDHCDHCDHCDS
44: 5 9 13 4 8 13 4 8 12 3 7 12 3 7 CDHHSCCDHHSCCD
45: 9 5 13 9 4 13 9 4 13 8 4 13 8 4 HCSDSHCHDSDCHC
46: 11 9 7 5 2 13 11 9 7 4 2 13 11 9 SHDCSSHDCSHHDC
47: 6 11 4 9 1 7 12 5 10 2 8 13 6 11 DSCHSDSCHSDSCH
48: 3 6 9 11 1 4 6 9 12 1 4 7 10 12 HDCSDCSHDSHDCS
49: 8 3 11 6 1 9 3 11 6 1 9 4 12 6 SHHDCCSSHDDCCS
50: 4 8 12 3 7 11 2 6 10 1 5 9 13 3 SSSHHHDDDCCCCS
51: 2 4 6 8 10 12 1 3 5 7 9 11 13 2 SSSSSSHHHHHHHD
52: 1 2 3 4 5 6 7 8 9 10 11 12 13 1 SSSSSSSSSSSSSH
53: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 DSDSDSDSDSDSDS
54: 1 1 1 1 2 2 2 2 3 3 3 3 4 4 CDHSCDHSCDHSCD
55: 7 1 7 1 8 1 8 1 8 2 8 2 9 2 HCSDCHDSHCSDCH
As mentioned earlier, there are two flavors of alternating shuffle, one with 52-cycle, one with 8-cycle. Perhaps you accidentally mixed the two flavors. Color me lazy if you wish, but I did not simulate all such mixtures to look for one with a 14-cycle.
By the way, I also did the experiment I suggested about slightly noisy shuffles. To observe significant non-randomness after 8 shuffles, I had to set the noise so low that the 7th shuffle also produced significant non-randomness. (I was using a very crude randomness measure.) Checking a link posted in this thread I see mention of a 1992 paper, which would have been just the right timeframe for the excited PhD student I remember. I now suspect he either misinterpreted the paper, or I misinterpreted his comment.
And from looking at that output, it looks like the only other time in the cycle when it looks “ordered” is after 26 shuffles, when the deck is reversed. There’s also the possibility that I started with the deck ordered 1C 1D 1H 1S 2C 2D 2H 2S etc., but we can consider that possibility just by looking at shuffles 2-54 in your list, instead of 0-52, which leads to the same cycle, just with a different starting point in it.
And I don’t expect any more effort from you on this (you’ve already put forth a heroic showing), but now I’m really wondering what the heck it was that I did that got me that 14.
Far be it from me to suggest that you’re not playing with a full deck… but decks of 42, 43, and 44 cards have period 14 for at least one of the flavors of perfect shuffle. (As do decks of 128, 129, and 130 cards.)
I find no patterns of 14 mixed-flavor shuffles that return a 52-card deck to its original state.
What about a 54 card deck, with jokers?
I thought of that as well, but no. The shuffle that leaves the first and last cards fixed has period 52; the other one has period 20.
Which should be obvious after a moment’s thought, given that it’s the equivalent to setting the top and bottom cards aside and doing an out-shuffle on the rest.