Slashdot Mirror
Magician Turned Professor Talks About the Math Behind Shuffling Cards
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."
to complete randomness, is to leave an open pack sitting on the floor and let loose the kittens.
I'm a very special type of magician, I'm a MATH-emagician
Brady Haran on Numberphile has a series of interviews with Persi Diaconis: https://www.youtube.com/playli...
Elen sìla lùmenn' omentielvo
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
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.
Hmm, I recall learning the seven shuffle result when I was in math grad school in the 80s (from Prof Diaconus himself.) Did he not publish it until '92?
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 cards, the more random sequence you have.
My question is..... what are the practical applications of this observation and what exactly mathematician is trying to prove.
Magician Turned Professor
...into a frog.
systemd is Roko's Basilisk.
Most people are not aware that a perfect riffle shuffle on a deck of cards returns the deck to it's original state at eight shuffles. This means an assumption of imperfection for seven shuffles.
It is highly probabilistic that a perfect riffle shuffle never occur. It takes some effort to replicate to perfect shuffle.
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.
It can be proved empirically that this is a correct theory - the longer you shuffle cards, the more random sequence you have.
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.
HA! I just wasted some of your bandwidth with a frivolous sig!
For those who are interested in math and/or card tricks, Colm Mulcahy is a professor of mathematics who often writes about math, cards and card tricks. He writes a blog called Card Colm for the Mathematical Association of America (MAA). He has written a book, Mathematical Card Magic: Fifty-Two New Effects, published by CRC Press.
A web site contains other interesting information about Mulcahy and his work, including links to past Card Colms.
Enjoy!
The Gilbert-Shannon-Reeds model 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 particular subset of the universe of possible distributions between a perfectly uniform distribution (the distribution of an infinite number of shuffles) and the distribution you actually have after a finite number of shuffles." As the Wikipedia article mentions, another alternative would be to use a measure of entropy instead of the statistical distance, but nevertheless statistical distance is a pretty good way to do it.
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 deck after a deck that is the result of an infinite number of shuffles. If the shuffle is performed the same way each time, then the order of the deck will be completely predictable. If the shuffle is not performed the same way each time, then it does not converge into any high entropy or statistically noise state to which you can compare your deck after a finite number of shuffles. Given an infinite number of shuffles there are an infinite number of times the deck is ordered perfectly, and many more infinite number of times the deck is in a low entropy state or statistically clean.
And if you're deliberately seeking to get the deck into some high entropy state by ensuring a semi-regular shuffle pattern and a target number of shuffles, then you're not getting a random deck.
If you believe in a probabilistic universe, then you can have randmoness, but you can never know if something is actually random or not.
This is fundamental shit.
You are not even wrong. 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 would recognize as being like "randomness". If you have a different definition of "random" that's fine, but you can't argue against the proof that 7 shuffles is sufficient to reduce the total variation distance to stationarity from about 1.0 to about 0.33. If you disagree, please show your work.