Slashdot Mirror
Fewer Shuffles Suffice
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."
My reply was shuffled 4 times and it's now at a completely random position!
I realize that you are joking; but the link between probability theory and mathematicians with raging gambling habits is about as old as probability theory. In fact, I suspect that, given a suitable supply of wit, an analog to the philosopher's drinking song featuring mathematicians and gambling could be constructed without substantial violence to the truth.(Heck, just look at Pascal, he couldn't put the dice down when he was writing about Theology.)
"We're all enthusiastic," Diaconis says, "because you can describe it to your mom, the math is hard, and the results are interesting."
RTFA just for it to turn out to be a Your-Mom joke. Thanks guys. You really got me.
Not so obligatory link: http://xkcd.com/221/
Any life is made up of a single moment, the moment in which a man finds out, once and for all, who he is.
First! (this shuffling really works!)
Extreme Programming - Redundant Array of Inexpensive Developers
I thought about spending several paragraphs and a couple of examples explaining this, but from past experience I have learned that probability is sometimes counter-intuitive and some people just never get it.
Feel free to read the paper. After all, this story is about a science paper. How a "shuffle" works is defined in the abstract. It's pretty silly to criticize a paper without even reading it.
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...
"They were pure niggers." – Noam Chomsky
I've played far more than my share of cards, from CCGs 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 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.
Use my userscript to add story images to Slashdot. There's no going back.
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
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.
Geek Prophet to the Technologically Declined
There's a subtle point that isn't obvious -- the revealed door is never the winning door.
You have a 2/3 chance of guessing wrong. But in that case, the other wrong door will be revealed, so swapping means you win.
Meanwhile, you have a 1/3 chance of guessing correctly, and therefore not swapping only gives you a 1/3 chance of winning.
Do you even lift?
These aren't the 'roids you're looking for.