The Math of Card Shuffling (2018)
fredhohman.com
fredhohman.com
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.
The in shuffle is n shuffles in general to get back to the start but the out shuffle isn't such a simple pattern.
If you want to make a shuffle that will take _even longer_ to get back to it's starting point, the best you can do is the Landau function which as you can see can get very big: https://oeis.org/A000793/list (I have a calculation of g(52) but not on me right now)
http://statweb.stanford.edu/~cgates/PERSI/papers/83_05_shuff...
I saw one of the authors, Persi Diaconis, give a talk on this paper, and then perform a perfect shuffle. I was floored.
Also, the statement in the article is for a random riffle, not a perfect one. Any deck which has only been perfectly riffled is entirely determined.
Of course, this is dependent on perfect shuffles, which I'm sure I never achieve. Maybe the 'seven shuffles to randomize' calculation takes into account the 'human' nature of shuffling during a game? It is almost a sure thing the deck will never be split perfectly in half, and a perfect faro shuffle achieved.
Someone else mentioned that it depends on if it's an 'in' or an 'out' riffle as well, so I read the wiki page. The basically tells me you should always try to do an 'in' shuffle, I will have to start looking out for this :)
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.
Interesting question just popped into my head, if the orientation of the card matters, how do people randomize that?
Smushing is a great way to shuffle cards (used on poker tournaments) but it doesn't work if they're sleeved.
For this reason I really appreciate board games which use bags and tokens as card substitutes. It's really the best shuffling method, except that token-sized cards don't have room for text on them. Now that I mention it I'm surprised there are no playing cards in the form of bag and tokens. Probably because ordinary playing cards are so cheap.
My source[0] says the lower bound for full overhand shuffle is number of cards squared, so less than 3000 shuffles for 52 cards. Upper bound around 5000.
Your source?
Of course, those numbers apply only if the shuffle is done literally—I personally try to mix individual cards by letting one hand’s batch cut in-between the other’s (and I think I’m not the only one)—but I’m still curious where did those 10000 come from.
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.
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).
Is there a smaller number of riffles that can produce every permutation, not necessarily 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.
Heuristically, there are a finite number of outputs of a riffle shuffle (probably fairly large; basically the number of different ways that you can clump cards together, 52^20 or thereabouts). But any finite number of outputs raised to the 7th power is not going to divide 52 factorial, in terms of the number of output possibilities.
I haven't worked at a casino for four years but at that time I beleive the market opened up. It sounds like a patent expired or maybe the fisr card shuffle company was sold.
https://www.amazon.com/card-shuffler-automatic-card-shuffler...
At casinos there's so many proprietary devices for example a small plastic block like a prism the size of a quarter. It sits on the table in the area where the dealer sets his cards. Blackjack dealers use it to view their cards when face down only they can see the image. Just that little stupid plastic block is patented and costs something like $10 per device per day for every casino that leases them.
I'm wondering how having non-perfect shuffling will affect the game play when it's a real world game and card combinations end up being left together.
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://www.rosettacode.org/wiki/Knuth_shuffle
What I mean though is that in real life people won’t shuffle the same way as the computer does so my online playtesting might be inaccurate.
They’ll just do crap shuffling and cards will still be together in sets from the previous game - what I need is a bad / human shuffling algorithm that shuffles like lazy normal people do!
(ETA: One perfect naive algorithm example is directly in the article here: the riffle one card at a time algorithm. Select any n riffles less than the mean 236 and it is a guaranteed lazy/bad shuffle. Even selecting above the mean doesn't guarantee a perfect shuffle, again because of the properties of a computer PRNG.)
They also cover that overhand shuffles in practice require something like 10,000 shuffles to properly randomize. The problem is familiar to cryptographers: this scheme has "confusion" but not "diffusion". You can see this yourself: sort a deck of cards[1], then do two overhand shuffles in a row and splay out the cards and look at how random the result looks. They kind of "undid" each other, they "commuted" with each other or so.
If you want something a little more interesting, try to overhand shuffle with large cuts and then overhand shuffle with smaller cuts, and this gives somewhat more diffusion. Or just overhand-large, overhand-small, and then riffle -- the riffle will give you tremendous diffusion of the cut entropy created by the overhands. Anecdotally it seems somewhat unlikely that one gets to the full 220-something bits of randomness from only 7 riffles as that would require each riffle to have 30+ bits of entropy which seems... unlikely.
[1] you can do this fastest probably with a sort of omniscient quicksort: sort black/red, then sort black into spades/clubs, then sort spades into high/low, then sort the 6 low spades by eye, then sort the 7 high spades by eye, then sort clubs into high/low...
I thought I had found my next idle clicker.
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
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.