The Math of Card Shuffling | Hacker News Reader

The Math of Card Shuffling

fredhohman.com

157 pointsdanso33 comments

There's a great numberphile with Persi Diaconis all about shuffling: https://www.youtube.com/watch?v=AxJubaijQbI The extra footage is fantastic, too.

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

Great 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?

Thanks!

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/

Check out other examples too: https://idyll-lang.org/gallery

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

[2]: https://www.chronicle.com/article/The-Magical-Mind-of-Persi/...

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

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

There is a difference between "random in theory" and "random in practice"... see: http://blog.maxshinnpotential.com/2017/11/05/how-you-should-...

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

Author 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

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

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

So why won't you play a truly random shuffled deck?

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

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

The behavior of the last cards is interesting.

This can be improved by splitting the deck between riffles.

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

I'd like to understand how you came up with the equation summing up to 235

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

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!

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

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

I don't think I saw is in the article, but what is the definition of a properly shuffled deck?

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

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

Can 7 riffles fully reverse the order of cards?

Sure. Why couldn't it?

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

80,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!

How big, you ask? This big: https://czep.net/weblog/52cards.html

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

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

This article didn't have enough Fourier transforms on the symmetric group.

and not enough coupling arguments.

Reply on news.ycombinator.com