Magician Turned Professor Talks About the Math Behind Shuffling Cards 63
An anonymous reader writes with this story about magician and professor of mathematics and statistics at Stanford University Persi Diaconis. "Now a professor of mathematics and statistics at Stanford University, Diaconis has employed his intuition about cards, which he calls 'the poetry of magic,' in a wide range of settings. Once, for example, he helped decode messages passed between inmates at a California state prison by using small random 'shuffles' to gradually improve a decryption key. He has also analyzed Bose-Einstein condensation — in which a collection of ultra-cold atoms coalesces into a single 'superatom' — by envisioning the atoms as rows of cards moving around. This makes them 'friendly,' said Diaconis, whose speech still carries the inflections of his native New York City. 'We all have our own basic images that we translate things into, and for me cards were where I started.' In 1992, Diaconis famously proved — along with the mathematician Dave Bayer of Columbia University — that it takes about seven ordinary riffle shuffles to randomize a deck. Over the years, Diaconis and his students and colleagues have successfully analyzed the effectiveness of almost every type of shuffle people use in ordinary life."
Tip: The best method to shuffle (Score:5, Funny)
to complete randomness, is to leave an open pack sitting on the floor and let loose the kittens.
Re: Tip: The best method to shuffle (Score:4, Informative)
What would motivate a rabbit, horse or dog to eat its own shit?
At least in the case of rabbits, it is normal behavior. All rabbits do it. They eat high-cellulose diets, and require bacteria to break down the fiber. Cows manage that by having multiple stomachs and a long digestive tract. But rabbits are too small for that, so they use two passes. After the first pass, the poop comes out soft and green, and is re-eaten as it emerges from the anus. After the second pass, the poop is hard black pebbles, and is not eaten.
Many animals will eat the feces of their young to get rid of the odor that may attract predators.
Most dogs stop eating poop as they mature. Puppies often do it, but adult dogs usually don't, unless they are nursing a mother, which often eat the puppy poop. Folklore has it that you can stop a dog from eating poop by mixing mashed pumpkin into their food.
Re: (Score:1)
What would motivate a rabbit, horse or dog to eat its own shit?
For a lot of animals their digestive system can't extract all the nutrients in one pass. By giving the food a second pass through the digestive tract they get more nutrients.
Re:Tip: The best method to shuffle (Score:4, Informative)
Cats aren't taking pleasure in tormenting prey, or playing with the mouse, they are tiring out an animal that has teeth and claws and could potentially hurt the cat. In the wild, even if a predator manages to kill the prey, if that prey manages to wound the predator so that the next time it goes on the hunt, it is not so strong or sharp, the predator is in trouble.
Have you ever gone fishing? The best way to catch many kinds of fish is to fight it for a while and tire it out. That's the hunting methodology that cats have evolved to use.
Re: (Score:2)
Just because there is a good reason for cats to torment their prey doesn't mean they aren't enjoying it. Hunting is part of their nature, and it does seem that more intelligent animals get joy out of doing what they were born to do.
I mean a household cat doesn't need to hunt to eat, but when left outside it will hunt with gusto. Its joy is inflicting agony and death.
Re: (Score:2)
Cats can be interesting when it comes to prey.
Re: (Score:2)
The kittens want you to believe that the outcome would be random.
Comment removed (Score:5, Funny)
Re: (Score:2)
Simpsons reference AND a Chappelle's reference? I think we just became best friends
Re: (Score:3)
Phantom Tollbooth did it first!
Re: (Score:3)
And it varies with each individual shuffler, deck of cards, etc.
To call such a thing a "proof" is an insult to actual mathematical proofs. To use such a definition of "random" is outright blasphemy.
Re: (Score:2)
The Gilbert-Shannon-Reeds model [wikipedia.org] of shuffling is a textbook example precisely because it is both mathematically tractable and a pretty good model of how a riffle shuffle actually distributes cards. It is so good a model, that I would argue that if your shuffling technique isn't well-approximated by the model, then you aren't doing a riffle shuffle.
And his definition of "random" is not "outright blasphemy." To the contrary, the definition is basically "the greatest difference in probability of any particul
Re: (Score:2)
That's a terrible definition of random. Entropy and statistics have nothing to do with randomness.
Something is random if it is not due to any deterministic cause. Yes, that definition means there is no such thing as a random event, a random number, etc in a deterministic universe. And yes, that is the correct definition.
In a deterministic universe there is no such thing as a "random" ordering for a deck of cards as there is no such thing as "random".
Beyond that, their definition is based on patterning a
Re: (Score:2)
You are not even wrong [wikipedia.org]. Measure-theoretic probability has proven itself as an exceptionally accurate model of highly complex, yet fully deterministic, phenomena that cannot be predicted well using other means. Such as the shuffling of a deck of cards, slightly different each time, but similar enough to be able to build a model of its behavior.
You called it "random," not me. I would call it "\underset {A\subset S_n} {sup} |Q^{*k}(A) - U(A)|" and then label it as "random" because that is what most laypeople
Numberphile interviews (Score:5, Interesting)
Re: (Score:2)
Dang it, I had my link all ready and you beat me to it. Damn good series, very interesting in that he describes in simpler terms why and how it is worked out.
Re: (Score:2)
Perfect shuffle (Score:1, Interesting)
If you do 13 perfect shuffles (deck cut in exactly half, one card from each half going on top of the other), you will end up with the same deck. So it's not surprising that 7 "shuffles" would maximize entropy, by how they are measuring it (where does the top card end up, are there adjacent cards still "stuck"). You do end up with interesting pattern on a perfect shuffle using a sorted deck.
--sf
Re: (Score:3)
http://en.wikipedia.org/wiki/F... [wikipedia.org]
First request for Slashdot video...EVAR (Score:4)
This topic might have warranted a video, considering it's a demo. It would sure beat all the "some dude talks about something for flipping forever" videos Slashdice keeps trying to dump on us instead.
Re: (Score:1)
I'm still waiting for an option to find sex partners with /. video.
Re: (Score:1)
Re: (Score:1)
Even greasy Yoda dolls get a taste for some strange from time to time.
Re: (Score:1)
This topic might have warranted a video, considering it's a demo. It would sure beat all the "some dude talks about something for flipping forever" videos Slashdice keeps trying to dump on us instead.
As I already pointed out in a different post, there are some video interviews on Numberphile:
:-)
https://www.youtube.com/playli... [youtube.com]
Ok, it's not a Slashdot video but hey
I heard his seven shuffle result long before 92. (Score:1)
What is the objective of the research? (Score:2)
First of all, my respect to devoted professor and mathematician who is able to concentrate into observation and to think it through various aspects.
I have read article carefully and what it says is that certain type of shuffling produces desired random sequence of cards.
Also, consequently, we have mathematician who is trying to prove statistical correlation between how much time is spent mixing (smooching) and the randomness.
It can be proved empirically that this is a correct theory - the longer you shuffle
Re: (Score:2)
It can be proved empirically that this is a correct theory - the longer you shuffle cards, the more random sequence you have.
Not for a riffle-shuffle, which is what most people do. For a riffle, the more you do IMPERFECT shuffles, the more random, but for every perfect riffle shuffle the output will be completely predictable.
A wash is a much more random shuffle, which is why casinos that don't have machines to shuffle and use a single deck will do a wash. I have no idea how the shuffle machines operate, they're literally a black box.
Re: (Score:1)
It can be proved empirically that this is a correct theory - the longer you shuffle cards, the more random sequence you have.
that's not true at all. After some point more shuffling will make the set less random the more times you shuffle. How do you find that point?
It's really not all that simple, but in many fields it could be important.
objective of the research: The perfect shuffle. (Score:3)
Not true. There is a limit to entropy of a collection of objects, and once you reach this limit, any change to the system can only to be a reduction in the degree of entropy in the system. Also, it is entirely possible, (if unlikely) that you can shuffle a randomized deck of cards into sequential order.
Re:objective of the research: The perfect shuffle. (Score:4, Informative)
Also, it is entirely possible, (if unlikely) that you can shuffle a randomized deck of cards into sequential order.
Random does not mean completely out of order, it means unpredictable. I can roll five dice and come up with a large straight (12345). The random comes from not being able to predict from the previous state (22222 Yahtzee!) what the next state (12356 chance) will be.
A perfect riffle shuffle is not a random process since you can observe the initial state (123456 e.g) and predict the result (142536). That's true for whatever the starting state is.
Re: (Score:2)
what are the practical applications of this observation
Mathematicians don't need practical applications. When they speak about "applications" they mean "applications to other fields of mathematics". And that is good so.
That being said, I know Diaconis primarily for his earlier work on ranking methods, which have many practical applications in CS -- like page ranking algorithms, for instance.
Magician Turned Professor... (Score:2)
Magician Turned Professor
...into a frog.
Re: (Score:2)
Magician Turned Professor
...into a frog.
If kissed he's a prince too...
Perfect riffle shuffle (Score:1)
It is highly probabilistic that a perfect riffle shuffle never occur. It takes some effort to replicate to perfect shuffle.
Re: Perfect riffle shuffle (Score:1)
It is actually pretty easy to do once you get the knack for it. Cut the deck in half, square the ends, place the ends against each other with about a three eights inch offset, push the halves together firmly, and slightly twist the opposite ends toward you. If it is a new deck, the cards will basically interlace themselves. perfectly.
Yes, I did have a misspent childhood.
Colm Mulcahy -- Math and Cards (Score:1)
For those who are interested in math and/or card tricks, Colm Mulcahy [spelman.edu] is a professor of mathematics who often writes about math, cards and card tricks. He writes a blog called Card Colm [blogspot.com] for the Mathematical Association of America (MAA) [maa.org]. He has written a book, Mathematical Card Magic: Fifty-Two New Effects [crcpress.com], published by CRC Press.
A web site [cardcolm.org] contains other interesting information about Mulcahy and his work, including links to past Card Colms. [cardcolm.org]
Enjoy!