Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

quantamagazine.org

Post reply on HN
Print view View original

31–40 of 65 posts

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

#31

Post by WorldMaker »

empath75 wrote: post #27
ecolonsmak wrote: post #17

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

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.

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

#32

Post by zahlman »

vessenes wrote: post #30

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.

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

#33

Post by zahlman »

HPsquared wrote: post #29
tobr wrote: post #10

Earlier quoted context omitted.

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

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

#34

Post by PaulHoule »

vessenes wrote: post #30

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)

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.

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

#35

Post by recursivecaveat »

brookst wrote: post #19
RNanoware wrote: post #11

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.

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

#36

Post by PaulHoule »

brookst wrote: post #19
RNanoware wrote: post #11

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.

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.

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

#37

Post by possiblywrong »

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

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

#38

Post by WillAdams »

zahlman wrote: post #32
vessenes wrote: post #30

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.

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

#40

Post by pmarreck »

possiblywrong wrote: post #37

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…

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?

Post reply on HN