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.
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.
What amazing control in that video.
From the very start, spreading the cards so evenly that every single card can be shown to be in order, then even more the precision needed to riffle the cards together perfectly eight times.
It you want to see more amazing, Ricky Jay could do this while keeping up a stream of amusing patter and making his hand motions seem almost casual. E.g. https://www.youtube.com/watch?v=eonlrksCsw8
Yes it's 8 perfect riffles. What the article doesn't seem to stress is that there are two different riffles—an in shuffle (top card moves to second) and an out shuffle (top card stays on top). It's only 8 with an out shuffle I think, but 52 with an in shuffle. So presumably their figure of 7 is referring to the in shuffle (as being 1 shuffle away from the original order doesn't sound too shuffled to me).
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)
Your statement about in shuffles for general n is false. Consider that an in shuffle on n cards is identical to an out shuffle on the middle n of n+2 cards.
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.
This really makes my head hurt, haha. I've always heard the 7 shuffles to be randomized. Great. But if I shuffle one more time it's back to where I started? How does that makes sense?!
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 :)
Two different meanings of perfect are being used. For eight "perfect" riffles to return to the starting order, you've got to split the deck perfectly in half, and then drop one card from one half, then one from the other, and so on alternating. For perfect randomness, choose at random which half to drop a card from each time.
Most smarter magicians think that it is a waste to show off things like this as demonstrations. There is a number of extremely clever card tricks that use the principle mentioned by you as one of their components, but you won't notice. It can be hidden in clever ways.
It's usually done with a so-called "faro shuffle". The mechanics behind it are really interesting and once you get good at it you can almost always guarantee perfect shuffles.
The explanation of the 1-card riffle looks fine on a purely mathematical (computer) simulation, but what about an actual human trying to do it manually? I'd presume one would be much more likely to insert the top card somewhere near the middle of the deck, and almost never at or near the top, nor at the bottom of it. Would the calculation still stand, or should one need more riffles to reach a truly random state?
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 situations tend to occur.
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.
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.
> You need about 10000 (ten thousand) of them to shuffle an ordinary deck of 52 cards.
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.
Assuming 4 shuffles per second, 3000 shuffles would take about 12.5 minutes, while 10000 shuffles would take more than 40 minutes. One of those sounds feasible during a break on a casual game night.
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.
I went down the rabbit hole of looking at Idyll [0] the tool that he uses to create the shuffling simulation. Some pretty interesting examples in the gallery. Trying to decide whether the capabilities are worth the learning curve.
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).
I once attended a talk by Roger Antonsen where he displayed lots of computer generated art he had made. The pictures of card shuffling he has made are simple but very elegant. https://rantonse.no/en/art/2018-07-25
This is a really nice visualization. One recommendation I'd have for the author is to use a four-colour deck (usually blue and green for diamonds and clubs). This would make it much easier to see where each card lands after inserting it randomly into the deck.
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".
I don't think the arrangements are equiprobable. Well-distributed, likely.
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.
An interesting bit if history. Electronic card shuffles were invented by a former truck driver. Casinos rented the devices from his company I don't think any were sold (their value was approximately $20,000 each).
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.
You can buy card shufflers on Amazon for under twenty dollars. I've only used one once and geez was it loud - hopefully they do not all have that issue.
The casino type shuffler have cameras to read the cards and remember the order of the cards after shuffling them. It also has a pseudorandom number generator it uses as a guide to shuffling randomly. You need to set the card type before loading too. Casinos order their own cards so you need to make sure the shuffler can read them.
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.
Also interesting here is that the number of single-riffles taken is expressed as a harmonic series, which in the limit can be simplified for 52 * (log(52) + .57) (where .57 is the Euler gamma constant). So this approach of shuffling is O(n log n), which is also the expected complexity of putting the deck back in order with pairwise sorting.
I'm designing a card game at the moment and have been pondering this because I'm doing play testing online, so the shuffling is done by a computer and is therefore perfectly random.
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.
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!
Most naive algorithms for card shuffling that you find people using that aren't Fischer-Yates or Knuth shuffle (as mentioned above) are sometimes "more lazy" than normal people and will give you worse results than the average human shuffling especially when you factor in how bad the average computer PRNG is. (Computers don't have "perfect random", so your assumption above is probably more amusing to me than you intended it to be. Even a bad/lazy human is still likely more "perfectly" random than the average computer.)
(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.)
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.
With practice you can get a riffle under 2-3 seconds without weaving. But if 7 still seems too much, do less but do a running cut or overhand shuffle between two of the riffles, like riffle -> riffle -> running cut -> riffle -> offer to cut -> deal. I heard this is what casinos did in older times, and they do have a direct interest in not making the shuffling too long (less hands played) or too weak (can be abused).
They talk about this in the associated Numberphile video. The starting bottom-most card can be thought of as creating a partition of the deck into two parts: the ones "above" it are not uniformly shuffled but the ones "below" it must be, and so right at the moment when it is placed into the deck, the deck must become perfectly uniformly shuffled and any further shuffles cannot take it out of that state.
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 would love to see someone pick up a $100,000 "Magic: The Gathering" vintage deck and giving it seven riffle shuffles saying, "The maths doesn't lie!" :P
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.
