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!
4 shuffles should be enough for everyone.
...deck shuffles you.
It helps reveal the math underlying Markov Chain Monte Carlo simulations, telling applied mathematicians when they can stop their simulations.
Please! Stop your simulations already! Think of the Children!
Quick, somebody report a bug to Microsoft. Free Cell and Hearts need a patch!
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.
If you take a great hand made of five cards together, then distribute them one at a time to several people, there's no need to worry that the full house that won last hand will just get handed back to the same person (or another) again. It would take one hell of a shuffling to hand back those same five cards to someone again the next round!
I've seen this assertion, and never quite understood it. I mean, if you're doing a perfect interleave shuffle, dividing the cards into two piles A and B and then weaving them together ABABABAB and so on, in what sense is that random? No matter how many times you iterate, it's still a purely deterministic process and you can easily predict the order of cards in the deck post-shuffle. So how do you get a random non-predictable card order out of this?
I can understand that in real life, you're not going to shuffle perfectly, there'll be a few more cards in one pile than the other, your interleave will occasionally do something like ABBBAABA instead of being perfect, and so forth, but in that case I don't see how you can say "Oh, it'll be random after 7 shuffles," because it'll depend on the amount of imperfection. And even then, this still doesn't strike me as actual random behavior; it's still deterministic, it just doesn't matter because a human observer isn't capable of observing the information he'd need to predict card order. But that information's still *there*, and a theoretical perfect observer will still be able to know what the card order is. With a truly random sequence, there is *no* way to determine the order, even given a perfect observer.
welcome our new less-thoroughly-shuffled overlords. (I am truly sorry for that, but I couldn't resist)
What we really need is a ten day waiting period and a background check before you can buy a congressman.
First! (this shuffling really works!)
Extreme Programming - Redundant Array of Inexpensive Developers
facepalm!
entropy does not decrease
never
IranAir Flight 655 never forget!
Shuffle tracking and sequencing techniques are well developed, and (very) skilled players regularly do these techniques to get an edge against the house.
The house doesn't shuffle thoroughly to ensure randomness, it does so to thwart advantage players.
I used to play complicated variants of Solitaire. I needed pretty much every one of those shuffles and then usually one more to make up for the terrible shuffle that was done really horribly.
In these variants, one small blockage of 3 cards stuck together from last game due to an incorrect shuffle can lose you the next round.
I file this under Texas SharpShooter.
http://en.wikipedia.org/wiki/Texas_sharpshooter_fallacy
"Let's discard games from the set of all games until they qualify under four shuffles!"
My first Journal Entry ever, in 8 years! http://slashdot.org/journal/365947/aphelion-scifi-fantasy-horror-poetry-webzine
If you'd like to play with solving simple substitution ciphers using both dictionary attacks and hill-climbing methods (similar to the method described in the paper), try Decrypto. It's open source, too.
http://www.blisstonia.com/software/Decrypto
facepalm!
entropy does not decrease
never
Every time I shuffle my deck of one cards it always produces the same order.
Oh, say does that Star-Spangled Banner entwine / The myrtle of Venus with Bacchus's vine?
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.
and can you predict when it will decrease? decreases are random fluctuations, you can see when they have happend but you cant see when they are going to happen.
If i have random inputs there is no 'blind' (probably the wrong word, but what i mean is without being able to see the cards) algorithm that can predictably make the data less random, without
IranAir Flight 655 never forget!
Incorrect sir!
You are simply defining the lower entropy instances (entropy after n shuffles, after n+1, etc) as indications of HIGHER entropy in the series.
Taken as a single element, which is what matters when playing cards, a shuffled deck can easily have lower entropy than it had prior to being shuffled.
In fact, good sir, I propose that for any statistically non-uniform (this is the goal, NOT randomness) deck n, deck n+1 (obtained by shuffling deck n exactly once) has exactly a 49.9999% chance of being higher entropy, and a 49.9999% chance of being lower entropy, and a .0002% chance of being the same entropy (assuming .0002% represents the deck being shuffled into the exact same order, or an order producing equivalent entropy).
Further, I propose the following for ANY deck of cards, statistically non-uniform or not.
You cannot define the entropy of a deck of cards without first defining the game, method of dealing, the number of players and their decisions (even when assuming "perfect" players), etc.
The simplest "game" would be to simply deal all the cards face up, in a row. Determining the entropy of that single game would be the closest analog to determining the entropy of the deck. Entropy of getting this many pairs, this many straights, this "21" pattern across n players, etc. Remember, determining the entropy involves finding the number of possible equivalent outcomes and the total possible outcomes (52! for a single, standard deck of cards).
Thus, for a deck n, the entropy is low if the outcome for a game is unlikely (fewer equivalent outcomes), and the entropy is high if the outcome for a game is likely. Your measure of entropy for any given game can be simple (dealer vs "perfect" player blackjack, who wins?) or complex (4 player poker, with certain decisions, entropy decided by considering the initial and final hands of all players).
For an undefined game, the entropy is therefor undefined. The entropy of the deck cannot be calculated, and is therefor always the same regardless of the number of shuffles.
For specific games (in terms of your entropy measure for that particular game), the entropy of deck n+1 (compared to deck n) will be the same A/52! of the time, higher B/52! of the time, and lower C/52! of the time, where:
A is the number of orderings that produce a game state with equivalent entropy.
B is the number of orderings that produce a game state with higher entropy.
C is the number of orderings that produce a game state with lower entropy.
For a generic game, (this is the amalgam of all possible playable games with a given deck, and thus the best measure of entropy of a "deck of cards"), you fall into the Y/52!, X/52!, X/52! split (see above). There are infinitely many games (when considering players and decisions), and while they balance higher and lower entropy for any given subsequent shuffling, because of the infinite rule sets, Y trends to but is not necessarily 1. Y can range from 1 to X.
So there you have it:
Entropy cannot change for a specific hand of an undefined game played with a deck of cards.
Entropy can decrease for a specific hand of a specific game played with a deck of cards.
Entropy can decrease for a specific hand of a general game played with a deck of cards.
Entropy can decrease for a specific ordering of a deck of cards.
Entropy can decrease.
But maybe the "blockage" occurred purely by chance, even though you did shuffle well. ;-)
That's the problem with randomness... you can never be sure: http://www.random.org/analysis/dilbert.jpg
"They were pure niggers." – Noam Chomsky
Dood - it doesn't get any more random after a while...
There are other problems with your idea as well, but I can't be bothered...
I play bridge. All 52 cards matter. 7 shuffles? Hell no!
On an average evening, 24 people shuffle a deck each. On average, the distributions of the cards is far from what you'd expect from a good (say by a computer) shuffle....
Shuffle standards vary depending on the region. As an American, I'm used to riffle shuffle as the standard method. If you try to use another method, even in a casual game, you will likely get complaints from other players that you haven't really shuffled the cards. But in Australia, I found that most people used overhead shuffling. More than once my use of the riffle shuffle was commented on as being usual. However, I did note that the professional poker dealers at the casino in Melbourne did use a riffle shuffle for their tables.
If your random number generator is truly random, a single pass will scatter your dataset. The problem Monte Carlo simulations can run into is not the number of passes through the randomizer but relying on a crappy non-random generator.
Get you back where you started.
Try it sometime.
You are being MICROattacked, from various angles, in a SOFT manner.
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).
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...
Use my userscript to add story images to Slashdot. There's no going back.
ok 4 shuffles? But how many rounds of 52 card pickup. Just one methinks.
I Need someone to rebuild a Digitech Digital Delay pedal for me....for me...for me...for me.