Seven Perfect Shuffles Randomize a Deck of Cards. But How Many Sloppy Ones? | Hacker News Reader

Seven Perfect Shuffles Randomize a Deck of Cards. But How Many Sloppy Ones?

quantamagazine.org

102 pointslayer859 comments

The article deserves several clarifications:

> The deck has to be cut more or less in half before shuffling.

"More or less" is doing some heavy lifting here. The original GSR shuffling model cuts the deck at a point that is binomially distributed, so that for example about one-fifth of the time the cut may be at least as asymmetric as a 21-31 card split, which I think most would agree is nowhere near "the precision of a professional magician."

Also note that the theorem in the paper really focuses only on relaxing the cutting model; the model of subsequent interleaving of the resulting piles is the same, dropping a card from a pile with probability proportional to the size of the pile. (Equivalently but perhaps less intuitively, for the original GSR model with the binomial cut, imagine flipping a fair coin for each card in the deck, then "de-interleaving" by sliding the "heads" cards out, preserving their relative order, and placing that pile on top of the remaining "tails" cards.)

> But with that seventh shuffle, the deck suddenly tips into a highly unstructured state.

More accurately, the total variation distance from a uniform distribution first drops below 0.5 at seven shuffles[0]. The actual cutoff phenomenon's asymptotic result would suggest 3/2 lg n shuffles for a deck with n cards, which for n=52 would be closer to nine shuffles.

[0] https://possiblywrong.wordpress.com/2018/09/02/arbitrary-pre...

If, instead of doing a binomially-distributed cut, we do a 2-step cut which consists of first a random cut (then take the bottom portion and place it on the top, which in essence shifts all the cards by a random amount), and THEN do a perfect half-and-half split to perform the actual shuffle with?

Would that get us closer to "random enough", quicker?

Why does it matter that only the cut is imperfect? Isn’t an imperfect interleaving also expressible as a modification to the unevenness of that left/right pile split? It seems the “0110” system doesn’t track relative order of cards but only the landing of each card, which allows each left/right landing to be treated as an independent event. If there’s no dependency on card order, modifying the cut split is a simple way to express both an uneven cut and imperfect interleaving with one variable.

But that assumes the model is only tracking cards’ arrivals in the left and right piles, not their ordering relative to one another. I only got that from the article.

Am I missing something? Is it that the left/right split is actually only informative about the amount of mixing that has occurred under the assumption that the interleaving was perfect, and therefore if imperfect interleaving is possible then one must weaken that guarantee - which then requires a more complex tracking system?

Ironically seven perfectly interleaved riffle shuffles will return a deck to its original order, so the title is spectacularly wrong for one famous result.

Also the new result is cool! (14 semi bad riffle shuffles are sufficient to mix)

It requires eight perfect riffle shuffles, not seven. (I just checked at the Python REPL.) And actually it depends on whether the riffles are done "in" or "out" (i.e. which half of the deck the new top card comes from).

I had understood that seven "typical" riffle shuffles produce good randomness.

Yeah, my father could do that consistently, and used it to teach me "Always cut cards" having also memorized the card order for each shuffle --- I guess being on a troop ship for weeks on end had to have some sort of up-side.

Nick Scarne is an interesting name to look up, and his writings are almost on a level with his facility to manipulate cards.

I love the fact that he intended to become a card shark but his mom steered him towards magic instead, and then he got hired by the US Army to teach enlistees about the various scams they might encounter overseas, in addition to serving as the "hands" for Paul Newman in the movie The Sting, which was about conning a mob boss? Damn, "interesting" is apt!

https://en.wikipedia.org/wiki/John_Scarne

Whenever someone acquires a morally-neutral skill (like "card manipulation" or "martial arts") that can be used for "good" or "evil" and chooses the former, that's almost always a good story... especially if they flirted with the latter...

Thanks for correcting the name and the link --- not sure where I got "Nick" from...

Well I'd imagine a "perfect" shuffling procedure would have an equal probability of all 52! possible outputs which includes the original input and one would expect the sequence that gets you there would be highly symmetric.

Anecdotally, I find that certain card games are more enjoyable with the imperfections of human shuffling: when clumps naturally arise after playing, packing, and unpacking the game several times. An element of organic personality arises when you see a sequence of cards from a previous game. That human element is lost when a computer perfectly shuffles a deck into a never-before-seen orientation.

Games that sort the cards are the worst / most interesting for this. Gin rummy, etc, where the end result of a game is sorted groups of same-numbers and runs. You can really tell when then shuffling has just transposed a few cards.

Magic the gathering has this problem. You have 2 types of cards, and drawing an imbalanced mixture is pretty detrimental. During play you tend to sort them into 2 piles though. Consequently it's a not uncommon sight to see people manually interweaving their cards after a match, then shuffling. Logically, this is either pointless or cheating depending on the quality of that shuffle, but people do it anyways haha.

There's quite the history of straight out cheating in high level MtG, and yes, insufficient randomization is one of the most typical ways around it. If all you do is cut their deck, and do zero shuffles, you will find a perfect interweaving of lands and spells either way.

Also see Magic players being fond of pile shuffles, which, of course, do very little randomization, and guarantee a good mana weave. Without a few shuffles of your own, most Magic decks ever presented are not sufficiently randomized, and it's even worse in Commander, where we are talking 100 card decks.

The interesting thing is, the cheating in mtg has always been so, ridiculously bad.

If anyone actually cared, and really learned the moves, it would be imperceptible, even on camera, but instead regularly players get caught doing the dumbest of obvious things, even while on camera.

I am in a tarot group where we have a lot of decks that people share. Many tarot users believe that a deck develops a personality specific to the user and because of that I got my own deck which I take to the group.

There's the general belief that all magical tools develop significance for the user over time, something that my wife who is a "secular green witch" who doesn't believe in psi at all would tell you all about.

Scientifically though, if somebody isn't a good shuffler their deck is not going to be well shuffled and they'll get readings that deviate from what you'd get from a well shuffled deck. It's harder to shuffle a tarot deck well because it has more cards and these are frequently larger. (Personally my riffle shuffle is awful and probably not much better than an overhand)

A new deck usually has the major arcana together and in order and other cards might be sorted by suit and then number. We do a 5 card spread and if your have a new and poorly shuffled deck of course you are going to have more spreads where you get both the Emperor and the Empress or the 4 of Swords and the 7 of Swords.

One of the things is, I do magic, and used to do tarot.

I found the tarot readings were infinitely better to the person getting the reading when I just forced the results. So I did.

I still did all the things you're indicating about talking about specific personality, etc, as the patter to the concept.

Yeah, I see a lot of people doing tarot readings for money but I don't see myself doing that.

I got into the tarot group because it's not so easy to find a therianthrope's guild!

From a scientific perspective there is a lot to say for randomness. Like the theory that the I Ching was a version of game theory from bronze age China. I recently created A System of Blessings with 13 selected characters from the I Ching because I wanted to give people something nice but didn't want to give everybody the same thing.

I never did it for money. I did it for free. My joy was in their joy.

My job was to heighten their experience, and to essentially act as a mini therapist enabling them to feel confident in their own decisions.

But I feel you. I did things entirely differently to everyone else. Which is why I thought it was an interesting story.

Myself I charm people with fox magic to melt them into puddles before I photograph them

https://mastodon.social/@UP8/116731777979379420

I find significance in the shuffling and enjoy it. Always overhand. And very thorough; I have a perhaps overmechanistic view but I suspect effective divination requires true randomness in the information theory sense.

There's even a form of bridge related to this IIRC, if a hand is passed out (nobody has opening to start the bidding), you stack the hands on top of each other and don't shuffle - because players organize their cards by suits, it always results in fun.

Yes - it's called goulashing. The cards are stacked and dealt out in groups of three and four to produce wild distributions.

The most interesting feature of it for me is that the carefully-developed bridge bidding systems don't work properly as they're implicitly based on a normal random distribution of cards. With a goulash it's likely that both sides have hands with 7+ cards in one suit, and the game is to pre-emptively bid high in "your" suit before they can do so in theirs. So you would ideally like different signaling arrangements that indicate suit length rather than quality.

Upper limit of 14. I’m curious then - when playing cards with friends we start with a semi -random, but definitely clumped, deck. It gets shuffled a couple times.

How random is that deck? How many “cold spots” does it have? Just how not random of decks are people playing with, and ultimately does that even matter if players lack the knowledge or skill to change their play because of that knowledge?

There's this numberphile video where Persi Diaconis tells a story about bridge and how the players got used to not totally random shuffled decks: https://youtu.be/RIGJH12vVCY?si=cMSx6YEr8MMFgYg6 (Starts at around 3:30).

Numberphile has a video with Persi Diaconis about the seven perfect shuffles. It gives a lot of insight and anectdotes in addition to the central theorem: https://youtu.be/AxJubaijQbI?si=ED7ufY4oPZnNxCbd

Shouldn't a perfect shuffle just reorder the cards without adding entropy?

You would need sloppy ones to introduce randomness.

I don’t know on perfect shuffles but for the sloppy shuffles, the deck is cut at a random location between each shuffle.

See the paragraph beginning "Yet terms and conditions also apply."

It's modelled with randomness, each card is taken from left or right with a probability, it's not a deterministic model.

You misunderstood because the title is ambiguous.

This talks about seven consecutive riffle shuffles ("cut the deck and interleave the piles"): Those are not a "perfect shuffle" (i.e. same probability for every permutation) by themselves, only after doing them several times consecutively (which is kinda suprising by itself).

A "perfect shuffle" according to the article:

>The riffle shuffle has to follow a realistic but strict model where cards are randomly interleaved from the left or right pile one by one. (Each card gets dropped from either the left or the right pile with a probability that’s proportional to the number of cards remaining in that pile. This means that the cards don’t simply alternate between left and right, which would result in a predictable structure; instead, the order might go “left, right, right, left, right, left, left.”)

Yeah, a "perfect" shuffle is known as a faro shuffle and it's the basis of a lot of magic tricks, but it's a weird looking shuffle and it sort of ruins the tricks once you can recognize it.

not a lot of magic tricks. quite few actually. and it's interesting that it ruins the trick for you, because it's still a quite hard maneuver.

as a magician, I'm always still impressed when I see perfect faros.

Yeah, I worked on getting a Faro for a while when I was a teenager but gave up on it after a few months. I even got some coaching and tips from the Professor and Earl Nelson, so the issue was definitely not a lack of knowing the best ways it's ever been done :-). I just couldn't get it quite reliable enough to 100% trust in performance. Plus most of the Faro effects that were hot at the time were poker stacks and I was never really into those plots.

Now, all these decades later, I don't regret giving up on the Faro and a burnable 2nd. I got along just fine without either one as there's so many ways to reach the same destinations. It's weird how some moves just 'speak to you' right away and others never seem to sit right. Best advice I ever got was to not force it. If progress stalls out, just move on.

You going to Magic Live this year?

Yeah, I also cannot get a perfect faro consistently enough. I can consistently get 51 cards correct every time. It’s actually amazing how I am off by one every single one.

That’s a thing where when you know how hard the trick is, it makes it better.

Very cool your training.

And same on poker plots. I can do them infinite other cooler ways, so what’s the point?

The burnable 2nd I have. But it’s not the traditional 2nd. I have practiced and still practice the Richard Turner style 2nd, but I never do it in a performance. I use another path to get to the same result.

Wasn’t planning on Magic Live, but I should see where it is and when.

> I can consistently get 51 cards correct every time.

That's not a bug, it's a feature! Just do a "new deck order restore" with the selected card out of seq. :-)

> when you know how hard the trick is, it makes it better.

Totally! A few years ago I shared my view on "The Progression of Close-up Magic" (pardon the paste):

1. When you're 12, you're happy if a trick fools anyone.

2. Once you get older and have practiced a lot, you start to feel cocky that almost all your tricks fool almost everyone.

3. Then you keep practicing obsessively, start sessioning with good magicians and get humbled all over again. But in their work you start to realize there are levels of depth beyond just fooling people. You can finally see the path and your journey begins.

4. If you keep no-lifing it, eventually those magicians you respect, start respecting a few of your moves back. And that feels better than the loudest applause from any audience.

5. If you're a public performer, you're now probably working regularly. You fool all non-magicians all the time, and even other magicians some of the time. All your years of practice and study have finally paid off. Then you realize, most nights the valets make more than you do. :-)

6. But you keep doing it because you love it, except now the only audience you're working to impress is yourself. Non-magicians love it just as much whether you do easy tricks the easy way or hard tricks the hard way. In competent hands, they all look identical.

But you keep looking for even harder stuff, and then spend hours reworking the methods, exploring how to create the same effect in new ways. You sweat the meta stuff - structure, timing, flow. You pick up new subtleties by studying ancient VHS videos of the old masters. How Slydini's body language made his lapping transcendent. You contemplate how Goshman put that goddamn coin under a clear water glass, in the middle of an empty table, under a spotlight, with 80 year-old arthritic hands. And no one saw him do it. No trick, no move, just pure Jedi misdirection. And no audience will ever know the hours you waste obsessing on this. To everyone else, the tricks look exactly the same, but you do it your own weird, much harder way simply because you think it's neat, elegant, clever or sometimes just because it feels a little more right.

7. At that point, whether you keep working as a pro or even still perform magic at all becomes irrelevant. It's just a day job like any other. You do magic for yourself and maybe handful of others who 'get it'. The tech equivalent is kind of like the time I realized I'd spent more time (and had more fun) reading Doom's source code than I ever had playing the game.

> I can do them infinite other cooler ways, so what’s the point?

One cold deck is worth a thousand perfect Faros :-).

> Very cool your training.

I'd been obsessed with magic since I was 7 and was lucky enough to live in Los Angeles. When I was 16 I heard about the Magic Castle Junior program, then just in it's third year. When I auditioned, Vernon himself (then in his late 80s) was one of the three judges. No pressure, kid - it's just the guy that book you've had since you were 12 titled World's Greatest Magic says is "the greatest magician of the 20th century." The Castle Juniors was the hardest audition in magic because they lose money on (and have to mentor) every kid they let in. Three tricks, 10 minutes. I was so nervous, I blew two of my three tricks. Complete fail. I was so naive and stupid, all three tricks I picked were originals with insanely high difficulty. I had zero chance of nailing them under the pressure and lights of the Castle close-up gallery. :-)

I was shocked when I found out I'd gotten in on my first audition (the avg was 3). Vernon was at my first meeting, took me aside and made it very clear he'd voted against me because I "sucked." He blamed the other two other judges for being 'softies' who gave partial credit to my failed tricks because they were "mildly interesting" twists. Vernon stayed tough on me for all my years in the Juniors, but I did learn a lot from the cranky old bastard. Once when I was classic palming a coin, he slapped my hand and snorted "you palm like a girl!" Offended, I replied "At least the coin didn't fall out when you hit my hand." He rolled his eyes, and sighed "Kid, if you're doing it right, it should fall out!" Vernon passed away a few years after I turned 21 and became a regular member. It wasn't until I was invited to be a judge for regular member auditions that I learned Magic Castle auditions require that all three judges vote "Yes" to accept anyone. Vernon had lied to me! That was the moment I began to suspect maybe he didn't believe I was completely hopeless! I think he just saw how arrogant and cocky I was and knew I needed to be humbled before I could learn anything he had to teach. At best, Vernon seemed to find all the Juniors annoying, and at worst, insufferable. We used to wonder why he bothered showing up to every meeting since we were so hopeless. Only in later years did I appreciate the gift he was giving us and the legacy he was creating. That first decade of graduates from the Juniors created a shocking number of the top magical performers, creators and teachers in the world (although I don't count myself in that lofty company).

I 'dropped out' as a performer after 4 years working full-time as a pro to become a serial tech startup entrepreneur. A few years ago, Stan asked me to give the opening keynote at Magic Live to reflect on how, in my case, so much early magic potential and world-class mentoring "had gone so horribly wrong." :-) My conclusion was that learning the centuries-old craft, rigor and discipline of inventing all-new ways to make the impossible seem possible, and then the showmanship to present it well - was the best training possible for a successful career in tech.

> The burnable 2nd I have.

I'm envious. Mine's just ugly. I kept playing with it on and off over the years but when I saw Lennart Green do his (face up!) I officially gave up on it forever. :-) Of course, Vernon was one of the few humans ever to master a perfect burnable middle. But that's a god move beyond us mere mortals. (Excellent book on Vernon's years long journey to get that 'perfect middle': https://www.amazon.com/dp/0805074066).

> Wasn’t planning on Magic Live, but I should see where it is and when.

First week of August in Vegas (usually the same week as Blackhat). I go every year just to hang out with friends from the old days. Ping me if you go.

Very interesting story. I come from a different direction.

I work in tech, and was onsite somewhere for over a month with nothing to do. Remote area. I had always loved magic, and had asked magic teachers to teach me when I was a kid, and they all said no, they don't teach anyone.

I read books, but didn't really get it.

So I was in tech, in a place completely foreign to me with no rental car on weekends. I asked the bartender if he had anything I could do. He handed me a deck of cards.

From there, I just started to learn and practice things cause I was bored. Ultimately went to train with Jeff McBride and Eugene Burger. Jeff wasn't focused on the kinds of magic I liked, and Eugene Burger hated my style. I fooled both of them for the "final", intentionally leading Eugene down a garden path.

He hated not treated the cards with reverence. So I threw cards behind me, knowing it would completely shut off his brain while I did the secret move.

I did the same with Jeff. In the routine, I took his teaching on what not to do, and intentionally did it to shut off his brain.

They were both completely, ridiculously fooled. I likely may have fooled them without it, but I am too clever for my own good, and wanted to trick them in my own way.

From there, I ended up training with the guy who actually fit my style, Dani Daortiz. I flew to Spain and learned from him and Yann Frisch. I also helped Yann develop a new move. I taught them some of my original moves which they loved. I just come at things from a very different angle, so I have some interesting things.

Dani asked me to perform at the end, but I was too nervous. He is the guy I most adore. I regret that.

I even left them at one point after a full day of working with them, and just went and did magic in Spain for the night. I just do whatever, and that was what my soul needed after listening to 12 hours of magic discussion.

So I'm a software engineer, who has it as a hobby, but whenever I do it, I do it at a level that is stupid good. I don't even remember tricks, or have a set list, I just sort of vibe with whatever I remember, and rely on all the random skills I have to get there. I will do Lennart's snap deal for fun, invent a new trick on the spot because I'm bored. I do have a few original tricks that are completely mine.

One of them has a mind reading plot with cards. I have done the trick so many times in life, that I can legitimately forget the card, and it's fine, I can actually do the activity of figuring out their card without knowing it a good percentage of time.

You just get so used to understanding how people react to things, that you can figure it out in the process.

The trick just keeps evolving. Now, quite often, I have other spectators figure out the card. They also can get it with my... direction to what to look for.

So then they get to be the star. Lot of fun. It has so many variations because the whole thing is jazzed. So every time something new works, it's another thing I might remember to do.

I also am maybe the only magician then will intentionally bomb tricks. I learned early on that I do this for fun, and unfun people are not worth my time.

So even though I know the trick, and their card, I will intentionally pretend I don't and bomb the trick. I like that space. Living in that space has taught me more than any book about how to jazz around failure.

Intentionally failing is a master class in the space of failure in magic.

So I'm just a software engineer, who has had a ridiculously deep hobby for a long enough time that I can do a full show at a moment's notice. I have the tools, the understanding, and I can do prepared stuff, jazz whatever, or remember a trick i haven't done in 10 years, and decide to do that.

I do it for my fun. It's enabled me to drink for free where ever I go if I want, and have an enjoyable time.

I don't usually do the Magic Live stuff. I did that stuff for awhile, but I never felt like it really added much value to my experience.

I feel like I could surely if I cared to, book a show here locally, and do it. It would teach me a lot, but I just don't really want it. I like just being a random dude who can do ridiculously good magic when I feel like it.

This is a weird title, because what is a perfect shuffle? The word shuffle does not necessary imply a rifle shuffle, and does perfect mean "it mixes the cards well" or is it meaning "cards go down left-right-left-right". It the later, then "perfect" shuffles don't randomize at all, as evidenced by the fact that 8 faros return the deck to order consistently.

I can do this when in shape, but like most mortal sleight-of-hand practitioners, only with in-hand faros. Actual table faros, what most people are thinking of with a rifle, are the domain of very very few, and even fewer can get that to a point of consistency. In hand faros are not impossible given fresh cards and enough practice.

I thought about this for a very long time. For any given deck of cards, there is a coefficient of the average magnitude of displacement from their current order after a shuffle. This can be positive or negative, but we take the absolute value. Then, divide the total number of cards in a deck by this number to get the number of times you need to shuffle. A total of 7 shuffles implies an average displacement of about 7 cards. I think it's reasonable if you alternate the cuts in between shuffles.

Sloppy shuffles have a much lower average displacement and thus need more shuffles to get to a random state.

Unrelated but the animated photo of the magician performing a shuffle really shows how advanced, efficient, and deliberate our limbs are.

I randomly came across a 1979 bbc documentary on "Word Processors" on YouTube yesterday. Even though I wrangle terabytes of data using AI agents everyday now, it still felt like magic to imagine myself seeing the documentary for the first time in 1979.

"...unique tracking label for every card in the deck"

I'd like more details on how this was accomplished on a practical level. Got me thinking about how to embed trackers thin enough to go into a playing card that would operate like a mesh network then the deck could self report once it's properly randomized making a green light go off indicating play may begin.

They didn’t do this practically, the “tracking label” is just an analogy to convey what they did mathematically. The word “barcode” is also only used because it might be more accessible to the layperson than “bit sequence”.

There are actually "marked" decks you can buy that come with an iphone app that tell you exactly where every card on the deck is by looking at the side.

Marked decks are an ancient tradition for both cheaters and magicians. There are also ways to mark a deck that aren't obvious to most people with a casual inspection and that don't need an app to read from the edge.

Yeah, but there aren't ones that will give you the _entire stack_ in less than a second from a glance at the side of the deck.

You might be surprised at how close they sometimes get, at a glance. For close up magic it has to be readable at a quick glance (without an app). For some of the cheating it has to "not even be a glance" because you can't get caught looking at the side of a deck.

To be fair, sure most of those marking strategies are approximations designed for a specific trick or a specific gambling game and so don't always need to be 100% of the state information (suit and rank of every individual card). But there are certainly close up magic reasons to have a deck you can find exact cards by marks. Though also to be fair, many (but not all) of those do move the marks to the back of the card with the assumption that you can at least spread the backs of the cards.

This is just the authors explanation to explain how to encode where a card ends up. The cards don't actually have barcodes, they have a binary-encoded number where a 0 indicates the left pile and 1 indicates the right pile during a specific round of the shuffle. The number encodes the journey that card makes during the shuffle. It's not an actual barcode.

The paper: https://arxiv.org/abs/2510.22783

Does this new proof have any practical consequences for determining if a PRNG algorithm is any good?

And 8 perfect shuffles resets it back to starting order (perfect being cards interlaced 1 by 1)

So just do -1 shuffles and save yourself a lot of effort?

Quite the assumption here: "cards are randomly interleaved from the left or right pile one by one. (Each card gets dropped from either the left or the right pile with a probability that’s proportional to the number of cards remaining in that pile."

... Why would it be proportional to the number of cards in each pile? (Edit: I suppose the person doing the shuffling might adjust the rate of cards coming from each hand ... But not perfectly and continuously)

> But not perfectly and continuously

Isn’t that where the randomness comes in?

The randomness comes from sampling the probabilities. The strange assumption is that the probabilities are exactly proportional to number of cards currently in each stack.

It's the simplest model that gives the right result for simple cases (e.g. once one pile is empty, the remaining cards must come from the other pile; and when they're evenly split, it should be a coin flip). It also entails, for example, that when there are N cards in one pile and one in the other, the single card gets placed in each possible spot with equal probability. (This recalls the old trick for getting a random line from a text file without pre-counting anything.)

If there is one card in this pile and no cards in the other, the probability of dropping the card from this pile is one. If instead there are some cards still in the other, a) the probability is less than one, and b) we move one step closer to the first state. So by construction it must be proportional - perhaps a poorly behaved proportionality, but that is still enough for the math to work.

TL;DR "roughly 14"

AI written? Em dashes, it's not X it's Y

Username checks out

Reply on news.ycombinator.com