Live data from Hacker News

The Math of Card Shuffling (2018)

fredhohman.com

31–40 of 65 posts

Re: The Math of Card Shuffling (2018)

#31

The link in this to another article about the number of different combinations of cards is mind blowing. I mean, I know I should probably have realised that really, but I didn't think it would be such a beyond-astronomical number of potential orders.

And then you consider a game like blackjack where you often have six decks in play, 312! combinations instead of 52!. Interesting question just popped into my head, if the orientation of the card matters, how do people randomize that?

312! is way too high - there are 6 indistinguishable copies of each of 52 cards, not 312 unique cards.

Re: The Math of Card Shuffling (2018)

#32
post #28

So 7 riffles can produce every permutation equiprobably, right? Is there a smaller number of riffles that can produce every permutation, not necessarily equiprobably?

> equiprobably

I thought you made up that word, but you didn't! Thanks for teaching me somethign new!

> e·qui·prob·a·ble

> (of two or more things) equally likely to occur; having equal probability.

Re: The Math of Card Shuffling (2018)

#33
post #9

There's a sort of magic trick involving doing perfect riffle shuffles where the whole deck retains it's order. If my memory is correct if you perform 8 perfect riffle shuffles (split deck 50/50, riffle one for one card correctly) then the order resets itself after 8 shuffles. It's usually only performed as a demonstration of skill by experienced card magicians than as a standalone trick.

Yup! That's correct, here's a demonstration: https://www.youtube.com/watch?v=rEoYwyHddLc Explaining why it works is an exercise in number theory. For example, card 1 stays in place; card 2 goes to position 3, then 5, then 9, then 17, ... In short, the reason why it works is that 2^8 - 1 is divisible by 52 - 1.

How can someone with that level of precision tolerate the wrinkled table cloth!

Re: The Math of Card Shuffling (2018)

#34
I've always shuffled three times due to hearing at some point in my childhood that 3 times was the max amount of shuffles needed to completely shuffle a deck. Recently I realized that doesnt check out but it's been hard to break the habit as more than 3 shuffles seems to take forever. 7 though? Wow.

Re: The Math of Card Shuffling (2018)

#35
post #28

So 7 riffles can produce every permutation equiprobably, right? Is there a smaller number of riffles that can produce every permutation, not necessarily equiprobably?

> equiprobably I thought you made up that word, but you didn't! Thanks for teaching me somethign new! > e·qui·prob·a·ble > (of two or more things) equally likely to occur; having equal probability.

Sophomore year of HS, my math teacher introduced us to the word equidistant. For at least an entire quarter, I thought he had a speech impediment and was trying to say "equally distant".

Re: The Math of Card Shuffling (2018)

#37
This is fun! One thing I notice is that rarely do I get one-to-one riffles. Often they group 2-3 cards together. I've always wondered (but not enough to do the leg work) if those 2-3 cards tend to stay together shuffle to shuffle. Can small physical attributes (size, edge alignment, inter-card friction, air pressure) contribute these cards to affect the entropy?

Re: The Math of Card Shuffling (2018)

#38
A question I've wondered about is whether or not every possible permutation of the deck can be reached by riffle shuffling.

As the article notes, a 1 card riffle can move the card at the end of the deck to any position within the deck, leaving the other cards undisturbed, so obviously you can reach any permutation by a series of 1 card riffles.

What about if you can only use "believable" riffles? By "believable" I mean that the cut is near the middle of the pack, and the alternate left and right drops are mostly small and about the same size.

The answer is yes, you can reach every permutation.

Let P be a perfect out riffle shuffle.

Let S(n) be an almost perfect out riffle shuffle, differing only in that when the cards that would end up n and n+1 from the bottom are the next two cards to drop in a perfect out riffle you drop switch the order they drop. S(n) is a believable riffle.

The result of applying S(n) is the same as if you applied P and then swapped the two cards that are n and n+1 from the bottom.

Let O(R), where R is any shuffle, be the minimum number of time you have to apply R consecutively before the deck returns to its starting order. (By "starting order" I mean the order it was in before you applied the O(R) R shuffles).

For example, O(P) = 8, because 8 perfect out riffle shuffles leaves the deck in the order you started with.

If you take a deck, do O(S(n))-1 shuffles using S(n), followed by one perfect out riffle P, the result is that the deck is back to its original order except that the cards at n and n+1 from the bottom are swapped.

Since you can produce any permutation by a serious of swaps of adjacent items (hello, Bubble Sort!), this shows you can reach any permutation by a series of believable riffles.

This is not necessarily an efficient way to achieve a given permutation, but hey, my bachelor's degree is in pure math, not applied math--efficiency is someone else's problem. :-)

Swapping n and n+1 with the above procedure takes:

   72 shuffles for n = 0 or 50
   56 shuffles for 1 or 49
   40 shuffles for 16, 17, 33, or 34
  120 shuffles for 22 or 28
   16 shuffles for everything else
Here's some Python code to play with this [1]. It takes n as an argument, and just does the O(S(n))-1 shuffles with S(n) followed by a perfect out riffle and then displays what cards ended up moved, along with how many total shuffles were done.

Probably not very efficient, as it was just a quickie for when I was playing around with this problem. (One shortcut it takes that might be confusing if you are not familiar with group theory. It does not actually do O(S(n))-1 applications of S(n). It takes advantage of the fact that the permutation you get by applying a permutation, R, O(R)-1 times is the same as applying the inverse permutation, R', once. So it actually just computes S'(n) and then applies S'(n) and P to the deck).

PS: if you apply S(n) once followed by P seven times, the result is to swap card (n+1)//2 with n/2+26 if n is even, or with (n+1)/2+25 if n is odd.

If you do S(n), 7 P, S(n+1), 7 P, S(n), 7 P you get swaps of consecutive cards. If n is even, you swap n/2 with n/2+1. If n is odd, you swap the cards that are 26 past the cards that doing this for n-1 would have swapped. That gives you a procedure for swapping any adjacent pair in 24 shuffles.

That beats the original procedure I have for 10 values of n.

[1] https://pastebin.com/bZW5ine7

Re: The Math of Card Shuffling (2018)

#39

This is fun! One thing I notice is that rarely do I get one-to-one riffles. Often they group 2-3 cards together. I've always wondered (but not enough to do the leg work) if those 2-3 cards tend to stay together shuffle to shuffle. Can small physical attributes (size, edge alignment, inter-card friction, air pressure) contribute these cards to affect the entropy?

> Can small physical attributes (size, edge alignment, inter-card friction, air pressure) contribute these cards to affect the entropy?

This is the basic premise of the Svengali deck of cards. One half of the cards is slightly smaller than the rest which gives the magician some ability to do tricks including things like "effectively" have two cards stick to each other (or jump each other).

https://www.newcasinosonline.co/svengali-deck/

Re: The Math of Card Shuffling (2018)

#40
post #11
post #8

What the article failed to mention is that a very common shuffling method - overhand shuffle - is terrible. You need about 10000 (ten thousand) of them to shuffle an ordinary deck of 52 cards. This can seriously impact you when playing board games, and collectible card games like Magic: the Gathering. In competitive CCGs it can make the game unfair. In non-competitive games it just makes it boring because the same si…

On the other hand, with sleeved cards - you can do a "direct" rifle by "cutting" one half of the deck directly into the other (looks a bit like the overhand shuffle, acts more like a riffle). Something like the second method here ("smash"? Shuffle). Note that the riffle shuffle is also pretty easy with sleeved cards, you just need to modify the technique a bit. https://youtu.be/nnVABY_a6IQ?t=2m21s

I play a lot of Magic and usually I do this. It’s hard to riffle shuffle a double sleeved 99 card library.
Post reply on HN