# Fewer Shuffles Suffice

#### kdawson posted more than 5 years ago | from the off-to-buffalo dept.

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."*

## fp (-1, Offtopic)

## Anonymous Coward | more than 5 years ago | (#25760301)

Anyone eles think Barack Obama is like jesus, but real?

## Racist mods (-1)

## Anonymous Coward | more than 5 years ago | (#25761617)

You got modded down because the mods are racist

## Re:Racist mods (-1, Troll)

## Anonymous Coward | more than 5 years ago | (#25767195)

This is true. It is racist, and therefore the worst thing ever in the history of history, not to consider negroes as magical super-human beings who are our superiors in every way.

It should be a federal offense if you don't allow a negro superman to have his way with your wife, daughter, your own asshole (for the "downlows"), etc., whenever he wants. And it should be a capital offense not to worship Barack Obama for the African god that he is.

Then, and only then, can our dream world (as depicted in Planet of the Apes) come true.

## Help! (5, Funny)

## azior (1302509) | more than 5 years ago | (#25760341)

My reply was shuffled 4 times and it's now at a completely random position!## Fourth post! (-1, Offtopic)

## Anonymous Coward | more than 5 years ago | (#25760461)

Ah bugger.

## 4 shuffles... (2, Funny)

## Shikaku (1129753) | more than 5 years ago | (#25760361)

4 shuffles should be enough for everyone.

## Re:4 shuffles... (2, Insightful)

## Sun.Jedi (1280674) | more than 5 years ago | (#25760413)

3, if the dealer is clumsy or awkward.

Unlike blackjack, many of the poker variants pay better the more hands you can 'play'. Slow shufflers ruin my hand/hour numbers, and subsequently my $/hour.

## Re:4 shuffles... (1)

## RiotingPacifist (1228016) | more than 5 years ago | (#25760957)

in poker the suit matters so, the new limit doesn't apply.

## Re:4 shuffles... (1)

## Sun.Jedi (1280674) | more than 5 years ago | (#25762333)

in poker the suit matters so, the new limit doesn't apply.

The suit is an additional data point effected by the randomization of shuffling. The number of shuffles still applies according to the maths in TFA.

## Re:4 shuffles... (2, Informative)

## e2d2 (115622) | more than 5 years ago | (#25761363)

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.

## Re:4 shuffles... (1)

## BrokenHalo (565198) | more than 5 years ago | (#25761823)

I guess that would be easily got around by running the cards through the machine a second time.

## Re:4 shuffles... (2)

## johnsonav (1098915) | more than 5 years ago | (#25763121)

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.

Having been a frequent visitor to casinos in the recent past, I can say that the use of auto-shufflers varies widely depending on the casino, or even different tables in the same casino. Some players, especially blackjack players, have a superstition that the auto-shuffler is somehow "rigging" the game to give the house a bigger advantage. I have seen casinos with auto-shufflers at every table hand shuffling cards because the reaction from players had been so negative.

I have to say that this discovery applies to blackjack much more than poker, or any other card game. Multi-deck blackjack, as is played at most tables in most casinos in the USA, is played with all players' cards face up. After each hand, the dealer collects the cards from each player in exactly the same way and places them in the discard pile. So, if the dealer is collecting the cards in the casino-regulated fashion, after the shoe has been dealt down to the cut-card the exact composition of the discard pile is known, with the exception of the undealt cards behind the cut-card.

Compare this to poker where the majority of the cards are never dealt, and of those that are, more than half are discarded before being turned face up for all to see. The composition of the unshuffled cards are more accurately known in blackjack, even when played with 6 decks.

Add to this that hand-shuffled, multi-deck blackjack cards are not shuffled very well at all. The large stack of cards is broken down into smaller piles which are then shuffled together in a predefined, casino-standard way, which does not add nearly as much randomness as a standard shuffle (which is infeasible with that many cards).

The bottom line is that with a computer, a few matrices, and a good dealer(who follows all of the casino shuffling and card collecting rules), the cards coming out of the shoe can be predicted with a suprisingly large amount of accuracy.

## Re:4 shuffles... (2, Informative)

## e2d2 (115622) | more than 5 years ago | (#25764585)

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, 1951But 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.

## Re:4 shuffles... (2, Insightful)

## Sun.Jedi (1280674) | more than 5 years ago | (#25770311)

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.

Since you discuss the online vs brick/mortar differences. Your final comment is even more profound, imho.

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.

I think its far more likely for an online deck in poker or multi-deck blackjack to be more (dare I say truly?) randomized than a manual shuffle based on super fast CPU crunched RNG's.

At the end of the day, the number of hands are finite, but it's a really big number for a single 52 card deck.

I found that in Hold'em, there are 1326 possible starting hands and in Stud, 2,598,960 possible.

Source1 [top15poker.com] .

Source2 [wikipedia.org] .

## I prefer the Nano.... (0)

## Anonymous Coward | more than 5 years ago | (#25760381)

With 4 shuffles I still can't pick the song I want.

## TGIF (0)

## Anonymous Coward | more than 5 years ago | (#25760419)

## Re:TGIF (3, Interesting)

## fuzzyfuzzyfungus (1223518) | more than 5 years ago | (#25760471)

Theology.)## In Soviet Russia... (2, Funny)

## Cornwallis (1188489) | more than 5 years ago | (#25760423)

## how in the fuck is this funny (-1, Flamebait)

## Anonymous Coward | more than 5 years ago | (#25761083)

seriously, go snuggle a dick

## Re:In Soviet Russia... (1)

## Eudial (590661) | more than 5 years ago | (#25762739)

When you count how many cards you have in quantum poker, you no longer know which cards you hold. Conversely, if you check what cards you are holding, you no longer know how many they are.

## Think of the Children! (1)

## erbbysam (964606) | more than 5 years ago | (#25760429)

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!

## oh no (2, Funny)

## redalertbulb (1321747) | more than 5 years ago | (#25760453)

Quick, somebody report a bug to Microsoft. Free Cell and Hearts need a patch!

## Re:oh no (1)

## hansamurai (907719) | more than 5 years ago | (#25763591)

Well, they added the ribbon toolbar to Paint and Wordpad, maybe they'll spend a few minutes on these too!

## Good one... (3, Funny)

## consequentemente (898944) | more than 5 years ago | (#25760473)

"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.

## Re:Good one... (1, Funny)

## Anonymous Coward | more than 5 years ago | (#25760903)

And we all know what "the math" is a euphemism for...

## Re:Good one... (1, Funny)

## Anonymous Coward | more than 5 years ago | (#25761257)

Arithmetic?

## Re:Good one... (0, Troll)

## TubeSteak (669689) | more than 5 years ago | (#25762641)

I RTFPDF and here's the decrypted prison code

http://i36.tinypic.com/35na4hd.png [tinypic.com]

## Re:Good one... (0)

## Anonymous Coward | more than 5 years ago | (#25769247)

on a more serious note, I must be a tard because I read the manuscript (or tried to) and I can't actually work out what this straightforward calculation is for the general problem of an n-card deck composed of m-types of cards (ie the true general deck).

anyone?

## xkcd (3, Funny)

## Andr T. (1006215) | more than 5 years ago | (#25760479)

## Could have told you that decades ago. (1)

## Drakkenmensch (1255800) | more than 5 years ago | (#25760489)

## Re:Could have told you that decades ago. (2, Informative)

## larry bagina (561269) | more than 5 years ago | (#25760607)

never ascribe to a heck of a shuffling that which can be adequately explained by stacking the deck and bottom dealing.

## Re:Could have told you that decades ago. (1)

## SeePage87 (923251) | more than 5 years ago | (#25762767)

guaranteeingthat that full house won't go back to the same person. It's equally important to ensure that it might go back to them as it is to ensure that it won't. Randomness is about randomness, not about getting different hands.## Re:Could have told you that decades ago. (0)

## Anonymous Coward | more than 5 years ago | (#25764415)

The issue is a bit more complex than someone getting the same hand again...

## Re:Could have told you that decades ago. (1)

## crossmr (957846) | more than 5 years ago | (#25767683)

I would say the chances would be the same as any other random cards end up being dealt to one person. We always talk about how "rare" it is for a specific hand to be dealt out of a deck, but in reality its just as likely as getting any other 5 cards dealt to you. Its just the ridiculous high number of combinations available for a deck make it seem like they're rare. You have just as much chance of being dealt a royal flush as you do any other specific 5 cards. Its just that there are more combinations of 5 random cards than a royal flush.

## How is this random? (2, Interesting)

## Phanatic1a (413374) | more than 5 years ago | (#25760725)

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.

## Re:How is this random? (2, Insightful)

## tomhudson (43916) | more than 5 years ago | (#25760773)

## Re:How is this random? (2, Informative)

## iangoldby (552781) | more than 5 years ago | (#25760817)

I think you needed to glance at the article:

We're not taking about perfect shuffling here.

## Re:How is this random? (1)

## RiotingPacifist (1228016) | more than 5 years ago | (#25760983)

but they're saying "a few" its hardly quantitative either, how can you do maths on "a few"?

## Re:How is this random? (0)

## Anonymous Coward | more than 5 years ago | (#25761309)

but they're saying "a few" its hardly quantitative either, how can you do maths on "a few"?

Fuzzily?

## Re:How is this random? (1)

## sexconker (1179573) | more than 5 years ago | (#25761483)

You can't - it's all bullshit.

When these retards talk about "random" they really mean "statistically non-uniform".

The more effort you put into making things "random" the less random they actually are. The goal of card simulations, shuffling, etc. is to make each hand statistically like every other hand. This is done to ensure the money flows in as expected.

If you were dealing with an actual random deck, you would be able to assume only the accepted probabilities of a statistically non-uniform deck. Once that deck is being dealt out, you can form some more accurate predictions based on what cards come out when. Using a statistically non-uniform deck, you can NOT make these same refinements to your predictions, because you must assume that getting a straight dealt across the 4 players and the dealer was a fluke. (You can of course refine probabilities that are based on the remaining cards in the deck once you've seen some cards dealt out.)

Great pains are taken whenever we want something to be random. When one of your methods involves checking and rejecting the output, you have failed. It's fine to check for statistical randomness of a given method when developing the method, to make sure you don't fuck up, but it's NOT okay to enforce that randomness later.

Specifying the number of times a deck of cards must be shuffled is just barely violating the rule. It's done to ensure predictable results and revenue.

Really, you should shuffle the deck a random number of times. Determine that random number by covering your (exposed) genitals with delicious honey and counting the number of insects that are stuck in the honey 1 hour later.

## Re:How is this random? (1)

## Aranykai (1053846) | more than 5 years ago | (#25762393)

Really, you should shuffle the deck a random number of times. Determine that random number by covering your (exposed) genitals with delicious honey and counting the number of insects that are stuck in the honey 1 hour later.

But that could easily be influenced by variables outside your control(time of day, place of exposure, temperature, relative humidity, season, alignment of the planets?), and thus, totally not random. It boggles the mind!

## Re:How is this random? (1)

## sexconker (1179573) | more than 5 years ago | (#25763317)

No, it's more random.

If you seek to control it, you're interested in statistical non-uniformity.

## a random number of times (1)

## Vryl (31994) | more than 5 years ago | (#25762915)

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

## Re:a random number of times (1)

## sexconker (1179573) | more than 5 years ago | (#25763343)

Define "random".

Something is either random, or not.

(Hint: NOTHING is random)

(HINT: No, not even that. We just don't understand quantum physics yet.)

## Re:a random number of times (1)

## Raffaello (230287) | more than 5 years ago | (#25767603)

(HINT: No, not even that. We just don't understand quantum physics yet.)Hmm, lets see...

quantum physics: better part of a century of experimental confirmation in thousands of independent tests with accuracy exceeding any other scientific theory.

your assertion: just your say so.

Yeah, gotta go with quantum physics here.

Executive summary: The physical world really is inherently random. Deal.

## Re:a random number of times (1)

## sexconker (1179573) | more than 5 years ago | (#25768901)

Accuracy and precision in our observations.

Almost no understanding of the causes of what we're observing.

## Re:How is this random? (1)

## Robyrt (1305217) | more than 5 years ago | (#25760829)

## Re:How is this random? (1)

## SQLGuru (980662) | more than 5 years ago | (#25760879)

Computers don't normally shuffle with the "divide into two stacks and interleave" algorithm. They tend to do more of a "remove a random item from A and place in stack B, repeat until A is empty" algorithm.

And as for deterministic, you forgot the variable of where the deck is split (size of A relative to B) which is another source of imperfection.

Layne

## Re:How is this random? (0)

## Anonymous Coward | more than 5 years ago | (#25764081)

I would initialize it to a known setup then loop over it x times, swapping 2 random enries each time.

## Re:How is this random? (1)

## SQLGuru (980662) | more than 5 years ago | (#25764449)

My algorithm makes a random deck in a single pass (assuming cards, 52 iterations - 51 with a "take the last item" optimization). Yours would require additional passes to ensure that it was random.....I haven't run the numbers, but I would guess somewhere in the neighborhood of 4x52 iterations (formerly 7x52).... :D

Layne

## Re:How is this random? (3, Insightful)

## Anonymous Coward | more than 5 years ago | (#25761011)

## Re:How is this random? (2, Interesting)

## RingDev (879105) | more than 5 years ago | (#25761699)

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.

No joke, you ever try to explain the Monte Hall logic of changing doors? I've had people fight to the bitter end on that one. I've drawn pictures. I even wrote a little .Net app with three doors and a picture of a goat just to help people comprehend...

-Rick

## Re:How is this random? (0)

## Anonymous Coward | more than 5 years ago | (#25761975)

Would you be willing to share the app somewhere?

## Re:How is this random? (1)

## s73v3r (963317) | more than 5 years ago | (#25762351)

## Re:How is this random? (3, Insightful)

## larry bagina (561269) | more than 5 years ago | (#25764299)

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.

## Re:How is this random? (1)

## Jeremy Erwin (2054) | more than 5 years ago | (#25765973)

That's a pretty good explanation. I would have modded you insightful, but my mouse slipped.

## Re:How is this random? (1)

## Geek Prophet (976927) | more than 5 years ago | (#25762385)

No joke, you ever try to explain the Monte Hall logic of changing doors? I've had people fight to the bitter end on that one. I've drawn pictures. I even wrote a little .Net app with three doors and a picture of a goat just to help people comprehend...

-Rick

You're doing it wrong. What I've found works is to extrapolate to ten, one hundred, ten thousand, or a million doors, and describe it as Monty Hall going down the row of doors, looking behind them, then opening them, except one. I've never had anybody argue the point with the million doors.

## Re:How is this random? (1)

## Tetsujin (103070) | more than 5 years ago | (#25763411)

No joke, you ever try to explain the Monte Hall logic of changing doors? I've had people fight to the bitter end on that one. I've drawn pictures.

What I've found works is to extrapolate to ten, one hundred, ten thousand, or a million doors, and describe it as Monty Hall going down the row of doors, looking behind them, then opening them, except one. I've never had anybody argue the point with the million doors.

I don't get how changing the number of doors makes the principle any clearer...

I was one of those "fight it to the bitter end" types (there was a pint of Ben & Jerry's on the line) - the bit that finally helped me understand was the realization that the choice of which door gets opened is constrained by your first-choice door - then I just ran the possible combinations (1 in 3 chance that my initial door choice was the right door, in which case switching results in failure, 2 in 3 chance that my initial door choice was wrong, in which case switching results in success)

## Re:How is this random? (1)

## Kagura (843695) | more than 5 years ago | (#25764065)

## Re:How is this random? (0)

## Anonymous Coward | more than 5 years ago | (#25767391)

No joke, you ever try to explain the Monte Hall logic of changing doors? I've had people fight to the bitter end on that one. I've drawn pictures. I even wrote a little .Net app with three doors and a picture of a goat just to help people comprehend...

-Rick

A way to (somewhat) explain it: If there is 100 doors and you choose one - then Monte opens 98 others... Do you keep your one or choose the one he didn't open?

## Re:How is this random? (1)

## C18H27NO3 (1282172) | more than 5 years ago | (#25767865)

## Re:How is this random? (3, Insightful)

## Anonymous Coward | more than 5 years ago | (#25761049)

## Re:How is this random? (1)

## RealGrouchy (943109) | more than 5 years ago | (#25767645)

I don't need to read it. It's clear just looking at the summary that it is plagiarized.

How many shuffles necessary to get randomness? Four. [xkcd.com]

QED.

- RG>

## Re:How is this random? (4, Informative)

## retchdog (1319261) | more than 5 years ago | (#25761077)

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: 7 vs 4 Shuffles (1)

## TaoPhoenix (980487) | more than 5 years ago | (#25761403)

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 [wikipedia.org]

"Let's discard games from the set of all games until they qualify under four shuffles!"

## Re: 7 vs 4 Shuffles (1)

## retchdog (1319261) | more than 5 years ago | (#25762577)

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 [random.org]

## Re:How is this random? (1)

## Phanatic1a (413374) | more than 5 years ago | (#25761475)

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

[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.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.

## Re:How is this random? (1)

## mr_gorkajuice (1347383) | more than 5 years ago | (#25761627)

there are no such observers for radioactive decay

I'll dare make the claim that it's just a matter of human technology not being advanced enough to create such observers. If the abscence of a sufficiently accurate observer defines true randomness, then shuffling a deck of card 4/7/whatever times creates true randomness if no cam is recording the shuffling. Otherwise, true randomness simply don't exist.

## Re:How is this random? (2)

## Geek Prophet (976927) | more than 5 years ago | (#25762647)

I'll dare make the claim that it's just a matter of human technology not being advanced enough to create such observers.

Nope. Observed phenomena in quantum mechanics exist that could not exist if the weirder claims of quantum mechanics were not true, including the inherent perfect unpredictability (i.e. randomness ) of certain phenomena. In other words, if atomic decay could be even theoretically predicted, certain experiments that have been done would have had different results.

## Re:How is this random? (1)

## ceoyoyo (59147) | more than 5 years ago | (#25761685)

Nobody lets you shuffle, do they?

While you may be technically right that a deck shuffle may not be truly random in a technical sense, the randomness they're talking about is certainly good enough for any practical situation.

Note that your playing back the video of either the die or the card shuffle is cheating. I can "predict" radioactive decay too if I'm allowed to film the particles flying out of the nuclei and play them back later. The trick is to predict the process

beforeit happens, not after you've observed it in progress. Go ahead and predict the order of the cards after being shuffled seven times,before the shuffling occurs.I strongly suspect that, like predicting the fall of die based only on conditions before it's shaken, or predicting the weather, falls into that collection of things that Newton might have thought predictable but are actually hidden by chaos.

## Re:How is this random? (1)

## retchdog (1319261) | more than 5 years ago | (#25762515)

You need to make a distinction between outcomes of a process, and the process itself. Even if you can fully understand the shuffle by reviewing several gigabytes of video after-the-fact, doesn't mean that it was

implementeddeterministically. (On a similar note, a perfect deterministic understanding of that shuffle won't help you with the next shuffle... why is that?)Similarly, suppose that we can perfectly observe radioactive decay in a recording. That's fine, but the atoms still decayed randomly...

A full deterministic solution to the "shuffling problem" would involve a state-space including perfect knowledge of the room-temperature; card material and age; the edge-profile of each individual card; shuffler's heart-rate and blood flow; &c., and I

stilldon't think you could predict very well without going into even more absurd depths (e.g. a full particle model of the shuffler's hand). Now, if you did implement such a model, wouldn't it be reasonable to call the inevitable deviations from this model, as random deviations?Sorry but, philosophy aside, it's just a

whole lot more effectiveto think of it as a random process.## Re:How is this random? (1)

## dcollins (135727) | more than 5 years ago | (#25762569)

"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."

This is a completely philosophical claim and non-scientific. There are two primary camps for probability interpretations. (1) The "frequentist" camp, where probability is an objective statement about the ratio of successes over many trials (i.e., no statement can be made about one single trial). (2) The "Bayesian" camp, where probability is a subjective statement about the observer's belief about the next trial.

It sounds like you're in the "frequentist" (objective) camp, and thus can't make any probability statement about individual trials in the first place. Others will differ. The distinction is not subject to scientific testing.

See http://en.wikipedia.org/wiki/Probability_interpretation [wikipedia.org]

## Re:How is this random? (1)

## retchdog (1319261) | more than 5 years ago | (#25763565)

Bayesianism != subjective.

That section is awful. It opens up by

definingBayesians as "subjectivists" and spews on about that a while, before finally (in the last paragraph!) saying that "the use of Bayesian probability involves specifying a prior probability...",which is the actual definition of Bayesianism!At least they mention de Finetti, but for an antidote look at e.g. http://en.wikipedia.org/wiki/Empirical_Bayes [wikipedia.org] , which is unfortunately at a much higher technical level than the bullshit section in Probability Interpretation. Oh well.

## Re:How is this random? (1)

## louiswins (1017272) | more than 5 years ago | (#25765501)

fix it! Imagine that!## Re:How is this random? (1)

## retchdog (1319261) | more than 5 years ago | (#25766867)

Yeah, and after I put one or two (precious!) hours into correcting it, it'll likely be reverted by some pompous jackoff (some people are really religious about the Bayes=subjective thing) at which point I'll have the option of ditching my time, or getting into a protracted edit war. I'd rather spend the time writing a paper or running a simulation.

You know, some people don't have time to waste on amateur drama about scholarly topics. Imagine

that!## Re:How is this random? (3, Informative)

## Geek Prophet (976927) | more than 5 years ago | (#25763763)

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:How is this random? (1)

## TeknoHog (164938) | more than 5 years ago | (#25762121)

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.

I think that's an essential point about randomness. Or at least thermodynamical entropy, with which I'm more familiar. Entropy is really a measure of how little you know about a system, and the better you define a system, the smaller its entropy.

Entropy can be calculated as k*log(W), where W is the number of microstates corresponding to your idea of the system. For example, there are more ways of arranging molecules into 1 liter of liquid water, than into 1 liter of frozen water. Thus we say that liquid water has a higher entropy.

You can define a specific arrangement of water that has zero entropy, but it's not going to last very long in that state. So in practice, you'll end up with a generic jumble of molecules. Your knowledge of that water is eventually reduced to its thermodynamical quantities (temperature, pressure, volume...), and there are many ways of having that kind of water, so it will again have the usual entropy.

## Re:How is this random? (1)

## AdamTrace (255409) | more than 5 years ago | (#25761667)

In fact, if you do a perfect ABABAB shuffle enough times, the deck will return to its original position.

It's called the Faro Shuffle:

http://en.wikipedia.org/wiki/Perfect_shuffle [wikipedia.org]

But you're right... a perfect shuffle is uniform. A very sloppy shuffle will leave big chunks of cards in the same order. So there is some indeterminate middle ground, I guess.

## Re:How is this random? (5, Informative)

## Sheafification (1205046) | more than 5 years ago | (#25761833)

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

knowthat 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

stillcan'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 cards are divided in two pieces, chosen by a binomial distribution. For example, cutting into sizes 2 and 50 has probability (52 choose 2) / 52! (this is small), whereas dividing into sizes 26 and 26 has probability (52 choose 26) / 52! (this is bigger). So it's more likely that things will be divided roughly evenly.

After the cards are divided in two packets of size A and B, the probability that we choose the next card in our re-ordering from the first packet is A/(A+B). So the probability of choosing from the second packet is B/(A+B). Repeat in this way until you've used up all the cards. Notice that in this model, you're more likely to drop several cards from a large packet in a row than you are to drop several cards from a small packet in a row. This should be a somewhat familiar fact to you if you've shuffled a bit.

## Re:How is this random? (1)

## Omkar (618823) | more than 5 years ago | (#25762923)

## I for one.... (2, Funny)

## bgackle (597616) | more than 5 years ago | (#25760739)

## What is random though? (0)

## Anonymous Coward | more than 5 years ago | (#25760871)

Technically the very act of shuffling the deck is not random. For instance I know several people who can shuffle a deck "perfectly". That is, split the desk exactly in half and then interleave every other card perfectly. They do it so fast that you can't tell that it wasn't a random shuffle.

## First post (3, Funny)

## Yetihehe (971185) | more than 5 years ago | (#25760951)

## Flip-side (0)

## Anonymous Coward | more than 5 years ago | (#25760997)

I think I'd rather know how many shuffles past 4 or 7 does a deck

loseits randomness, if it does at all. And if it does, how many shuffles of a fresh deck would it take to go from ordered to random to ordered again?## Re:Flip-side (1)

## RiotingPacifist (1228016) | more than 5 years ago | (#25761161)

facepalm!

entropy does not decrease

never

## Re:Flip-side (0)

## Anonymous Coward | more than 5 years ago | (#25761369)

Entropy does not decrease

on average.It

can(and does, with a measureable, but small, probability) increase locally for short periods of time.## Re:Flip-side (1)

## RiotingPacifist (1228016) | more than 5 years ago | (#25761973)

and can you predict when it will decrease? decreases are

randomfluctuations, 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

## Re:Flip-side (0)

## Anonymous Coward | more than 5 years ago | (#25762363)

and can you predict when it will decrease?

No, of course not. If it was predictable, why would you need the tools of probability and statistics?

Entropy can decrease locally with a measureable (but small) probability.

It's "entropy of a closed system" that can never decrease

on average. (In the absence of external forces, and with certain other technical caveats such as the process being ergodic and the small-multiplier problem doesn't exist and the dimensionality being finite and assuming the axiom of choice and blah blah blah...)## Re:Flip-side (1)

## HTH NE1 (675604) | more than 5 years ago | (#25761507)

facepalm!

entropy does not decrease

never

Every time I shuffle my deck of one cards it always produces the same order.

## Re:Flip-side (1)

## sexconker (1179573) | more than 5 years ago | (#25762445)

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.

## Re:Flip-side (0)

## Anonymous Coward | more than 5 years ago | (#25774801)

Assuming a perfect split (2 piles of 26) and a perfect ABABABABABA.... shuffle

repeating the sequence:

Start Deck:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

1 Shuffle:

1 27 2 28 3 29 4 30 5 31 6 32 7 33 8 34 9 35 10 36 11 37 12 38 13 39 14 40 15 41 16 42 17 43 18 44 19 45 20 46 21 47 22 48 23 49 24 50 25 51 26 52

2 Shuffles:

1 14 27 40 2 15 28 41 3 16 29 42 4 17 30 43 5 18 31 44 6 19 32 45 7 20 33 46 8 21 34 47 9 22 35 48 10 23 36 49 11 24 37 50 12 25 38 51 13 26 39 52

3 Shuffles:

1 33 14 46 27 8 40 21 2 34 15 47 28 9 41 22 3 35 16 48 29 10 42 23 4 36 17 49 30 11 43 24 5 37 18 50 31 12 44 25 6 38 19 51 32 13 45 26 7 39 20 52

4 Shuffles:

1 17 33 49 14 30 46 11 27 43 8 24 40 5 21 37 2 18 34 50 15 31 47 12 28 44 9 25 41 6 22 38 3 19 35 51 16 32 48 13 29 45 10 26 42 7 23 39 4 20 36 52

5 Shuffles:

1 9 17 25 33 41 49 6 14 22 30 38 46 3 11 19 27 35 43 51 8 16 24 32 40 48 5 13 21 29 37 45 2 10 18 26 34 42 50 7 15 23 31 39 47 4 12 20 28 36 44 52

6 Shuffles:

1 5 9 13 17 21 25 29 33 37 41 45 49 2 6 10 14 18 22 26 30 34 38 42 46 50 3 7 11 15 19 23 27 31 35 39 43 47 51 4 8 12 16 20 24 28 32 36 40 44 48 52

7 Shuffles: (Notice something? odds in the first 1/2, evens in the second?)

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52

8 Shuffles:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

So, 8 shuffles should have you back with your initial deck. Meaning if you want to save shuffle time and have a perfect 7 shuffled deck, just put first card in pile A, second in B, third in A, etc, then stick pile A beneath pile B.

## Completely untrue (1)

## HEbGb (6544) | more than 5 years ago | (#25761395)

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.

## Simple substitution cipher program (1)

## edwinolson (116413) | more than 5 years ago | (#25761407)

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 [blisstonia.com]

## There is another variable (i.e. I call BS, YMMV) (3, Informative)

## Khopesh (112447) | more than 5 years ago | (#25761813)

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:There is another variable (i.e. I call BS, YMMV (1)

## Chris Pimlott (16212) | more than 5 years ago | (#25763495)

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.

## Re:There is another variable (i.e. I call BS, YMMV (2, Informative)

## Khopesh (112447) | more than 5 years ago | (#25764169)

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

## Bridge. (1)

## rew (6140) | more than 5 years ago | (#25763261)

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

## Monte Carlo? (1)

## jmichaelg (148257) | more than 5 years ago | (#25763971)

If your random number generator is truly random [fourmilab.ch] , 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.

## Single deck, 7 perfect shuffles (1)

## SpaceLifeForm (228190) | more than 5 years ago | (#25764111)

Get you back where you started.

Try it sometime.

## How many? (1)

## TornCityVenz (1123185) | more than 5 years ago | (#25768645)