6 ms·
The Math of Card Shuffling
- evanb 8y agoThere's a great numberphile with Persi Diaconis all about shuffling: https://www.youtube.com/watch?v=AxJubaijQbI https://www.youtube.com/watch?v=AxJubaijQbI The extra footage is fantastic, too.
- fredhohman 8y agoAuthor here: I link to this video in the post—it was what originally sparked my interest to do the visualization! The whole channel is really great.
- edanm 8y agoGreat article! Where can I find other things you've written? I tried searching your website, but it looks like the blog is pretty inactive. On another note - I saw that you used Idyll for this site. I haven't heard of it but am very interested - what do you think about it?
- fredhohman 8y agoThanks! This was a side project for me. I'm doing my PhD right now so all my current writing is funneled into my research. But Idyll is great for these types of articles, so I'm looking forward to doing more in the future. The creator of Idyll is also a good friend of mine so I may be a bit biased :) Here's the homepage: https://idyll-lang.org/ https://idyll-lang.org/ Check out other examples too: https://idyll-lang.org/gallery https://idyll-lang.org/gallery
- drifkin 8y agoPersi Diaconis is fascinating, it's definitely worth reading through his biography [1]. A small preview: after leaving high school at 14 to travel as a magician, a little more than a decade later he managed to get into grad school at Harvard, largely due to a letter of recommendation about his magic abilities (apparently that's a thing). I also really enjoyed that he was shy revealing his background in magic to other Stanford faculty until he discovered that Paul Lévy also studied perfect shuffling [2]. [1]: http://www-history.mcs.st-andrews.ac.uk/Biographies/Diaconis.html http://www-history.mcs.st-andrews.ac.uk/Biographies/Diaconis... [2]: https://www.chronicle.com/article/The-Magical-Mind-of-Persi/129404 https://www.chronicle.com/article/The-Magical-Mind-of-Persi/...
- partycoder 8y agoThe behavior of the last cards is interesting. This can be improved by splitting the deck between riffles.
- jedimastert 8y agoI don't think I saw is in the article, but what is the definition of a properly shuffled deck?
- fredhohman 8y agoSuperficially, any arrangement of cards should be equally likely to exist, i.e., no one ordering should be favored over another. I'm a bit ill-equipped to go much further than that currently, but the Numberphile video linked in the post may help! There's also been research on this topic too that you get to from Wikipedia: https://en.wikipedia.org/wiki/Shuffling#Randomization https://en.wikipedia.org/wiki/Shuffling#Randomization
- GuB-42 8y agoJust on top of my head: a deck where the original order and shuffled order are completely uncorrelated. Or a deck where the shuffle process yields every possible order with equal probability. These two are equivalent if all cards are the same for the purpose of shuffling (no bias).
- praptak 8y agoCan 7 riffles fully reverse the order of cards?
- fredhohman 8y agoNot sure about that... but 8 perfect out shuffles will return a deck to its original order! (Thank you undergrad physics professor!) https://en.m.wikipedia.org/wiki/Out_shuffle https://en.m.wikipedia.org/wiki/Out_shuffle
- edanm 8y agoSure. Why couldn't it?
- rocqua 8y agoLike the others said, given any initial order, a 'proper shuffle procedure' gives the same probability to each other possible order of the deck. Note that this definition is about the process, not the end result. (One might say something about the end result using Kolmogorov complexity, but I know very little about that) It should also be said that the "7 normal riffle shuffles" mentioned earlier in the article is not a 'proper shuffle procedure' in the strict sense. For example, it seems to me that cards that were close together in the initial state are likely to remain closer together after 7 riffle shuffles than after a proper shuffle.
- vermontdevil 8y ago80,658,175,170,943,878,571,660,636, 856,403,766,975,289,505,440, 883,277,824,000,000,000,000 Quite a big number!
- andrepd 8y agoHow big, you ask? This big: https://czep.net/weblog/52cards.html https://czep.net/weblog/52cards.html
- sjcsjc 8y agoThis link always gets posted here when this subject comes up. If you haven't read it it's well worth a look. It's a very effective way of conceptualising the vastness of big numbers.
- eric_h 8y agoI love how he says that the result of seven riffles is “likely” to be unique, when in fact the result is very, very, very [very x 1000] likely to be the first time any human has seen that ordering of cards.
- everdev 8y ago> most of the time, a deck of cards is shuffled using a riffle. Here’s a question: how many times do you have to riffle a deck of cards before it is completely shuffled? It’s a tricky one, but math has us covered: you need seven riffles.
- trombonechamp 8y agoThere is a difference between "random in theory" and "random in practice"... see: http://blog.maxshinnpotential.com/2017/11/05/how-you-should-be-shuffling-cards.html http://blog.maxshinnpotential.com/2017/11/05/how-you-should-...
- SomewhatLikely 8y agoFor instance, the assumption that a single card riffle into a deck will put it in a random location. In reality it would probably be something more like a bell curve around the middle.
- fredhohman 8y agoAuthor here. Definitely true that you need a random number generator for this to work. See this relevant response to my tweet with a paper describing how bad humans are at picking random numbers: https://twitter.com/fredhohman/status/1007718733186396161 https://twitter.com/fredhohman/status/1007718733186396161
- trombonechamp 8y agoThere is actually a pretty simple algorithm people can use (in real time) if they want to generate random numbers: http://blog.maxshinnpotential.com/2017/07/05/can-humans-generate-random-numbers.html http://blog.maxshinnpotential.com/2017/07/05/can-humans-gene...
- sdenton4 8y agoThis article didn't have enough Fourier transforms on the symmetric group.
- cosmic_ape 8y agoand not enough coupling arguments.
- pjungwir 8y agoA high school friend told me the same thing around 1993-1995: you have to shuffle it seven times. He said he read it in Wired magazine. I've tried to find the article a few times since, but never been successful.
- wjnc 8y agoSince I lack the skills to riffle succesfully, I usually sort and shuffle based on the properties of the game at hand. I usually sort somewhat randomly to stacks, where the number of stacks is larger than the regular set in the game (but < 2 times the regular set). After that, a few quasi riffles and I feel I've made the next game sufficiently random from the sorting that the last game gave. Wonder if I could wrap my math around formalising that.
- lorenzhs 8y agoThere’s a nice but somewhat technical analysis of card shuffling things in “Proofs from THE BOOK”, a book I can highly recommend to the mathematically interested (requires some mathematical background, like what you’d get in a good CA curriculum, but nothing fancy). This link to an older edition should hopefully work: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.167.5285&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.167...
- jedberg 8y agoThat's not how you shuffle cards though. First you cut the deck, such that the bottom card is somewhere near the middle. Then you split and riffle. If you do that seven times you get a random deck. If you do it three times you get a fairly random deck, but you'll get clumps of cards together. That's why casinos usually use three cut/riffle steps, and why you can have an advantage playing with a hand shuffled deck. It's also why I will never play with a machine shuffled deck. Because those are actually shuffled seven times, and are truly random.
- Kartificial 8y agoSo why won't you play a truly random shuffled deck?
- jedberg 8y agoBecause then I have no advantage over the casino. With a hand shuffled deck, you get clumps of high cards together from the last set of hands, which gives an advantage to the player. If you can ride out waiting for the clumps, you can beat the house.
- kpskps 8y agoI'd like to understand how you came up with the equation summing up to 235
- edanm 8y agoIf you take the 52 out of the sum, it becomes: 52 * (1/1 + 1/2 + 1/3... +1/n), where n=52. This is the harmonic series. I didn't know off-hand of a formula for the sum of the harmonic series, so I searched, and apparently, there is no closed form formula for this. So you either have to actually calculate this number, or find an approximation. Personally, I just plugged it into Wolfram alpha: http://www.wolframalpha.com/input/?i=1%2F1+%2B+1%2F2+%2B+...+%2B+1%2F52 http://www.wolframalpha.com/input/?i=1%2F1+%2B+1%2F2+%2B+....... The result is, approximately, 4.538. And indeed, 4.538 * 52 = 235.976, which rounds down to 235 (not sure why the author rounded down). Thanks for asking this!
- have_faith 8y agoThere is a very interesting false card shuffle called the Faro Shuffle. A trick most card magicians/technicians can spend a lifetime perfecting. If you split the deck perfectly, riffle shuffle perfectly such that each card lands 1 for 1 with each other, and repeat 8 times, the deck will be fully restored to it's original order. No one uses it in live tricks due to the dexterity required and the fact that to a layman the effect is identical to other easier false shuffles.
- 8bitsrule 8y agoRiffle shuffle leaves many cards that were near the bottom still near the bottom. That's not exactly what I'd call 'truly random' ... which would be ANY card has an equal chance of being ANYWHERE in the deck. A better alternative would be to put the bottom-third of the deck on top, then riffle.