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!
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
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