Fewer Shuffles Suffice 101
An anonymous reader writes "You may have heard that it takes about seven shuffles to mix up a deck of cards to near randomness. Turns out, though, that most of the time, perfect randomness is more than you need. In blackjack, for example, you don't care about suits. The same mathematician who developed the original result now says that for many games, four shuffles is enough. And the result isn't only important for card sharks. It helps reveal the math underlying Markov Chain Monte Carlo simulations, telling applied mathematicians when they can stop their simulations."
Re:Could have told you that decades ago. (Score:2, Informative)
never ascribe to a heck of a shuffling that which can be adequately explained by stacking the deck and bottom dealing.
Re:How is this random? (Score:3, Informative)
I think you needed to glance at the article:
We're not taking about perfect shuffling here.
Re:How is this random? (Score:5, Informative)
Yes, they model the imperfect interleave, and they assume that more cards will fall from the larger of the two stacks. The randomness comes, of course, from the fact that the number of cards which fall from each stack into each "leaf" is effectively non-deterministic and unobservable.
Your perfect observer would also argue that rolling a die is a deterministic process: he needs only to observe the force (acceleration) I apply to my hand/arm, and can in principle reconstruct the path of the die. However we assume that the observer can't do this, as long as I'm putting some effort into the shaking. [As a small semantic point, note that I could put up a screen and block your observer's view of my hand; by your definition, I have now made the die a "truly random" number generator even though I haven't really changed anything. We need to be careful saying things like "perfect observer" because there isn't really any such thing, just like there is no such thing as an unstoppable force, or impenetrable barrier.]
Regarding the seven shuffles thing, the result is rather robust to variation in the number of cards which drop. This is because the eigenstates of the deck-system, corresponding to unmixed-states, decay geometrically with respect to applying the shuffle operator. Intuitively, every time you apply a shuffle, it becomes less likely to see a given pre-existing pattern in the cards. Let's say it becomes x times as likely. If the shuffles are independent, then after seven it'll be approximately x^7 times as likely. You may object that you could shuffle back to the pre-existing pattern; the fact is, that probability is very small, and the theory does account for it.
Now, x^7 is going to be a pretty small number, whether x=0.5 or x=0.2 (but not if x=0.9). Establishing the upper bound on the relevant x is of course, part of the paper...
Re:4 shuffles... (Score:3, Informative)
Any decent brick and mortar casino will have an auto shuffler. Even the local dog tracks here in FL that run card games use them.
There is another variable (i.e. I call BS, YMMV) (Score:4, Informative)
I've played far more than my share of cards, from CCG [wikipedia.org]s and other proprietary games to standard 4-suit 52-card playing cards (learning to shuffle 200-card decks in Magic:TG before we discovered that a 60 card deck was optimal sure made me good at shuffling!), and let me say this: some people shuffle better than others.
Quality of shuffling varies widely; If I concentrate, I can get a clean broken-in deck to shuffle perfectly alternating cards from each half (though this is undesirable as it is not random). On the other end of the spectrum, many people shuffle very large chunks alternating, which is only as random as the cards are clean (which is to say, usually not very random).
Methods of shuffling also vary. There is the standard "Riffle" shuffle that was probably used in this study, there is overhand shuffling (taking small piles of cards from one or both sides of the deck and assembling them in a different order elsewhere), and there are several other methods. Because my riffle can sometimes be too precise, I will actually alternate riffle and overhand shuffles, performing three of each when I shuffle a deck.
In Magic: The Gathering, it is common to table-shuffle, which is essentially dealing out the cards into a set number of piles (usually 4-6 as they each divide a 60 card deck evenly, thus letting you ensure the cards are all there). This assures absolutely no clumping of dirty cards. Since it isn't very random, it should be followed by proper shuffling. (M:TG tournament rules now require three riffle shuffles since some people insist upon table-shuffling to preserve their expensive cards.) I use this method when dealing with dirty standard cards, too.
The WikiPedia page on Shuffling [wikipedia.org] is actually amazingly informative, covering different shuffling methods, fake shuffle tricks (for magic tricks or cheating), shuffle-tracking (for gamblers), and far more math than the article linked in this sciencenews.org article. Give it a gander.
Re:How is this random? (Score:5, Informative)
Since I've RTFA a little (I know, I know, this is slashdot), and IAAM (mathematician) allow me to try to answer.
Whether a deck of cards is "random" or not is a subtle (and somewhat meaningless question). Afterall, the deck might follow a pattern but if I don't know the pattern then it appears random to me. In fact, this is exactly how decks of cards work: you've assigned each card with a number from 1 to 52, and you deal the cards by picking the card that's assigned number 1 first, number 2 second, etc. If I don't know how the numbers are assigned, then I can't tell what's coming next so it looks random. On the other hand, if I know what order you've put the cards in, then nothing is a surprise.
Instead of considering whether a deck is "random" or not, we're more interested in how well one can predict what the order of the cards are: either without seeing any of the cards, or after seeing the first few deals. For instance, if I know that you only order your decks in increasing order of rank with the suits randomly ordered, then seeing that the first deal is an Ace of Hearts tells me what the next 12 cards must be. All because I know how you like to order your cards.
This example, of course, never happens. But if instead of being certain about how you order things, what if I knew that you were more likely to order in a certain way? What if you ordered them as above 50% of the time, and the other 50% you riffle shuffled them? Then seeing an Ace of Hearts on the first deal doesn't make me certain about what's coming next, but I have a pretty good idea. Seeing a Two of Hearts re-affirms my hunch, but I still can't be completely certain.
This still isn't quite a real-life example, but it's getting close. If we know that the person shuffling favors certain orders over other, then we can predict what's coming next with better than chance accuracy. So the idea of "randomizing" a deck of cards is to re-order them without having any bias in the new order that we choose.
The way to minimize the bias is to select a permutation of 52 cards, with each permutation equally likely to be chosen. So each permutation has a probability of 1/52! chance of being picked (that's 1 / (52*51*50*49*...*1) ). This "uniform distribution" is the best way to keep someone from being able to predict what card is next, even if they've already seen the previous cards. That's because we don't have any bias in how we are ordering, so there's no extra information for them to take advantage of.
When we do a riffle shuffle we are choosing a new ordering of the cards. Obviously we are choosing our re-ordering in a biased way: we're more likely to have cards from the top and bottom interleaved than we are to reverse the order of the deck for instance. So we have a certain distribution of probabilities on the possible permutations, and this distribution is not uniform.
But what if we riffle shuffle again? Given our original deck order, we now have certain probabilities of choosing the various permutations as our new order. And as it turns out, we're a little less likely to be biased in favor of certain permutations. If we keep riffle shuffling over and over again we're smoothing out our bias and heading towards a uniform distribution.
The question of "how many times do we need to shuffle?" is really "how many times do we need to shuffle to be pretty close to the uniform distribution?" There are technical definitions for what it means to be "close to the uniform distribution", but that's the idea.
So a deck of cards has been "randomized" if I tell you the order it started in, I tell how what procedure I'm going to use to pick a new re-ordering, and you still can't tell what order the deck is likely to be in because my procedure is going to choose any of the possible re-orderings with equal probability. Note that you don't get to peak at the deck after each shuffle, you only get to see it at the start.
As for the imperfection in the shuffling, TFA tells you the model they use: The c
Re:How is this random? (Score:3, Informative)
Sure it's observable. Record it and play back the film. They don't let you do that in a casino, so it's "random enough" for their purposes, but you can't turn a truly random process into a predictable one by observing it on a finer timescale.
You seem to be under the impression that observability creates non-randomness. It doesn't. It only creates non-randomness *if* observations done *before* the randomizing process can predict the results.
Suppose I had a device which used radioactive decay to produce perfect random whole numbers between 1 and any arbitrary number up to 52. I set an entire deck of cards in front of me, laid out side by side. I ask the device to pick a number from 1 to 52, take that card, and turn it over to one side. I then do the same again using a number between 1 and 51, placing the card face down on the first card. I continue, repeating until I have 52 perfectly chosen random cards stacked up next to me.
The deck is random, beyond any doubt, but anybody watching me knows exactly what order the deck was in. This ability to determine the final results by watching the randomizing process doesn't change the fact that it is a random result.
You can watch me shuffle from here to doomsday, but if your observations *before I begin* cannot tell you anything about the final result, this means nothing as to whether or not it is random. You have to predict the result, not observe it.
I'd disagree. It's a random system if knowing the state of the system at t0 doesn't allow you to predict the state of the system at t0+. The toss of a die might be "random in real time," because you can't predict it that way, but I'd dispute that it's random in the same way that, say, radioactive decay. Randomness is objective, not dependent on the observer, and there are theoretical observers who could predict the outcome of a die roll; there are no such observers for radioactive decay, or the emission of Hawking radiation, or of shot noise.
Nope. Not even a "perfect observer" could do what you describe, if the die roll is done correctly with sufficiently well-formed dice.
Quantum fluctuations influence the firing of my neurons in my brain and nerves, the twitching of my muscles, the elasticity of the dice impacts, and the movement of the molecules of the air. Further, a "perfect observer" who actually observed these quantum fluctuations would, according to quantum dynamics, inherently influence them, generating new randomness.
Further, the dice rolling is chaotic, with high sensitivity to initial conditions. Thus, even the tiniest random fluctuations in the base conditions produce completely different results. Since there is so much true unpredictability in the initial conditions, and so few possible results (only six per die), these tiny unpredictable factors translate to unpredictable macro effects.
In other words, even your "perfect observer" would still get a random result, if the die roll is rolled in such a way as to have both sufficient random fluctuations in the initial conditions and sufficient events that are sufficiently sensitive to initial conditions. However, it is theoretically possible for the perfect observer to spot when these factors do not apply, such as when a skilled dice thrower is throwing to minimize the randomizing effects.
Re:There is another variable (i.e. I call BS, YMMV (Score:3, Informative)
Riffle shuffling is "professional-grade" in that it is the most thorough, and it is standard in the States. Throughout Asia and other parts, the "Hindu shuffle," which is very similar to the overhand method, is the most prevalent (as explained at WikiPedia:Shuffling#Hindu shuffle [wikipedia.org]).
Most of the Asians and Australians I've played with actually use Hindu rather than overhand, so I'd guess that's what you saw. The difference is in the delivery of the cards from one pile to the other; in overhand, you're dropping them from one stack to the other (so the hand holding the original stack is doing all the action), whereas in Hindu, the action is in your free hand, which takes the cards from the main stack and slaps them back in a different position. This is typically done horizontally whereas overhand can be done in almost any position (usually at an almost vertical angle to use gravity).
Hmm, that's a better description than on Wikipedia. I'll be right back...
Re:4 shuffles... (Score:3, Informative)
This paranoia seems kind of funny considering a well practiced dealer can become a "mechanic" and deal exactly what he wants to the participants, with only the keenest eyes catching it.
It's funny because some of the same sentiment is heard in online poker circles from players that distrust the shuffling algorithms used. In the past this distrust was actually a valid sentiment, with predictable patterns being found in specific online card rooms. But these days it's still a very very small risk given that these shuffling algorithms are certified by 3rd party crypto experts (such as Cigital) these days.
But even pokerstars, one of the largest online poker rooms, has this quote on their shuffling page:
"Anyone who considers arithmetic methods of producing random digits is, of course, in a state of sin." - John von Neumann, 1951
But in poker and all other games it just doesn't pay for the house to cheat. They have the edge. In poker it's the rake. In other card games it's simply the game. There's is always a strong motivation to discourage cheating from all sides so players will continue playing.
I just find it kind of ironic that people are willing to gamble with a random deck of cards, yet unwilling to overlook the smallest risk of a rigged deck. Part of gambling for profit is managing risk, this included.