A shuffled deck of cards is unique in all human history | Hacker News Reader

A shuffled deck of cards is unique in all human history

matthewweathers.com

272 pointspud66 comments

Makes a good hide-in-plain sight crypto key. I could see James Bond using this and destroying the key as the bad guys approach with a little 52 pickup.

Done!

http://www.schneier.com/solitaire.html

In particular,

    If the secret police starts breaking down your door, just calmly shuffle the deck. (Don't throw it up in the air; you'd be surprised how much of the deck ordering is maintained during a game of 52-Pickup.)

This is a plot point in Neal Stephenson's Cryptonomicon.

I believe there is also an appendix providing details.

See also http://en.wikipedia.org/wiki/Solitaire_(cipher) which uses a deck as an innocent-looking keystream having a lot of entropy.

It should be noted Solitaire is not secure for long messages.

http://www.ciphergoth.org/crypto/solitaire/

What's really cool about Solitaire is not so much that it uses the deck as a RNG and keystream, but that it uses the deck as a computational tool. You can easily sit down and securely encrypt a (relatively) long message without writing down anything but the cipher text.

The algorithm is also pretty straightforward. I learned to do it a couple years ago-- if you're interested in crypto and get invited to parties, it makes a neat party trick. It took a couple of hours, maybe, before I could do a couple characters a minute. I'm sure I've forgotten the specifics by now, though; it's not something that comes up a lot in day-to-day life :)

Nice. But of course, shuffling a deck of cards does not even come close to completely randomizing the sequence compared to the previous ordering (especially if you are a crappy shuffler like me). Thus the sequences are correlated, so it's much more complicated to determine how likely it is to get a repeated configuration.

Actually, a deck of card is random after 7 shuffles.

http://en.wikipedia.org/wiki/Shuffling#Randomization

Actually, I think lutorn's point is that most people (including him) do not do a full riffle shuffle when they set out to shuffle cards, thus preserving the order of segments of the cards.

even if you're preserving blocks of 3, 17! is a big number. it's not 10^44, but still, 10^14 is pretty big.

How many amateurish shuffles would it take to randomize a deck?

It's a 10 letter password in [a-z]. 8 letter in [A-Za-z]. It's 47 fair coin flips.

Or 1 deck per day for 7 billion people for 40 years.

I do use the cards metaphor for passwords: http://github.com/gaiustech/MkPasswd

That is indeed lutorm's point.

But the shuffling model used in the Diaconis and Bayer paper that the reply referred to (the "7 shuffles to randomize" result) takes that into account. In particular, the shuffling model gives reasonably high probability to "imperfect" riffle shuffles that take several cards from the left pile and then several cards from the right pile.

This model is on the first page of the paper

http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?vi...

Basically, you split the cards at random, and then you draw sequentially at random from the two piles with probability L/(L+R) versus R/(L+R) (where L is the number of cards remaining in the left pile), to assemble the new deck. This will allow shuffle sequences that take a run from the left and then a run from the right.

As people above have noted, of course the "randomization" of the deck is not perfect after 7 shuffles. But for lots of Markov processes, including this one, the distance of the shuffled deck to the uniform distribution on all decks tends to zero exponentially fast. So you get a quick change-over from "not random at all" to "very random". See table 3 of the paper.

Persi Diaconis (http://www-stat.stanford.edu/~cgates/PERSI/), to whom this result is partly due, is a legend in mathematical probability. How many math professors are bona fide magicians?

Sort of, depending on what you mean by random. The article seems to imply the uniform distribution on all 52! orders, which 7 shuffles won't get you. For example, you can't reverse a deck with 7 shuffles. There are bets you can put on a deck that's been shuffled 7 times that pay better than the same bet on a uniformly selected order.

Yeah, that phrase "truly random" in the wikipedia page is misleading. At least they do include in the references a link to Bayer and Diaconis' paper. What the paper says is that (for a certain mathematical model of the riffle shuffle, which experimentally seems to match actual results produced by human riffle shufflers) if you measure the total variation distance d between the probability distribution of the order you get after k shuffles and the uniform distribution on all 52! orders, you get d=1 for k=1,2,3,4 (i.e., maximally far in total variation distance from uniform), d=0.924 for k=5, and d drops off exponentially after that:

  k     5     6     7     8     9    10
  d 0.924 0.624 0.334 0.176 0.085 0.043

The total variation distance is an upper bound for the absolute difference in probability over all subsets of permutations.

In particular, we can consider the set:

   U = {all permuations that have never been seen by a human}

The counting arguments in the article lead us to conclude that the uniform probability of U is very close to 1, i.e. almost all permuations have never been obtained by a human shuffle. The Bayer-Diaconis result implies that for certain types of shuffles the probability of ending up in U is at least

   1 - (the total variation distance above)

So for 8 shuffles, we have a probablity of at least 82.4% of landing in U. This is considerably weaker than "every shuffle is unique".

If that's the case, which orders are more common? Do decks come in a set order? Assuming they do, I guess imperfect shuffling would result in orderings influenced by that original order. Of course, once you cut the deck a few times, I would think any statistical influence from the original ordering would be nullified.

What I meant was that after shuffling, all orders are not equally likely. The ones that are "close" to the previous one will be a lot more likely. That probably doesn't change the conclusion that it's "very unlikely" that two independent decks are shuffled into the same seqeunce, but it sure means that the chance of getting the same sequence back again after shuffling the same deck is a lot larger than 1e-89.

> Of course, once you cut the deck a few times, [...]

Do you mean to do the cuts one after another?

The first 10 or so shuffles of a new deck of cards may be relatively common, but after you put a deck of cards away you are not going to reorder it. Most aged decks are therefore going to be completely unique in their ordering.

The only people who use new decks frequently are casinos, and they have very good shuffling machines. It is likely that every deck dealt in a casino is unique.

I don't know, I end up reordering cards often enough when trying to figure out which card is missing, or because I just won a game of solitaire or what not.

I'd amend this to say "A PROPERLY shuffled deck of cards is unique in all human history".

Without proper shuffling, a card deck is like an encryption key with a poor initialization vector -- it's more predictable.

Card decks ship in order, and playing solitaire will potentially put it back in order. Many people don't shuffle properly, so I would hypothesize that the actual set of decks that most people run into are less random.

I concur. Another question to think over is...lets say you hand out a brand new pack of cards which come arranged in a certain order. Now you hand them out to one million people and ask them to rifle shuffle it 'N' times. What are the chances that two of them have it stacked in the same way after they do so? My guess is for low values of 'N', it would not be that uncommon.

Doesn't the birthday paradox also come into play here, significantly increasing the chances of a duplicated shuffle?

The chances of you sharing a birthday with one of 22 other people is pretty low. the chances of at least two people in a group of 23 is 50%. In the first case, you're fixing the day that some other person must have.

In other words, the odds that a deck you are holding is unique are high; the odds that all decks ever shuffled are unique is low.

Actually, the probability that all decks ever shuffled are unique is also very high. We can approximate the probability that any two of the n decks shuffled in human history were identical as p=1-n^2/52!

Using the same estimate as the OP for n (1.56x10^23) gives p=3.02x10^-22. Still fantastically low.

Alright, fine, it is comparatively lower. Better? :)

Nice, I came to the comments to see if someone knew how to calculate this.

Related question. If there are exactly 2N people who vote in a binary election (ie: for presidential candidates) and they have an even 50/50% chance of voting either way, how do I compute the odds that they will have a even split? This is a generous estimate for the probability my vote will matter.

That's the same as the probability that 2N flips of a fair coin result in exactly heads: (2N choose N)(.5^N)(.5^N).

Check out: http://en.wikipedia.org/wiki/Binomial_distribution

The exact answer is (2n choose n) * (1/2)^(2n). This is approximately sqrt(1/Pi n) as n grows large, with error O(n^(-3/2))

> We can approximate the probability that any two of the n decks shuffled in human history were identical as p=1-n^2/52!

I think that this is way too low. Shouldn't it be the quite large number

1 - \prod_{i = 1}^n (1 - (i - 1)/52!)

(a la the birthday paradox)?

Sorry, I was thinking of the complementary probability (that there has been a coincidence).

Mathematica overflowed when I tried to compute this by brute force. The next best thing I can think of is to use the exponential approximation

    1 - x ≈ e^{-x},

good for very small `x`, such as ours. Ignoring the cascading errors gives

    \prod_{i = 1}^n (1 - (i - 1)/52!)
    ≈ \prod_{i = 1}^n e^{-(i - 1)/52!}
    = e^{-n(n - 1)/52!}
    ≈ 1 - n(n - 1)/52!.

The error should be roughly of the size

    \frac1 2\sum_{i = 1}^n [(i - 1)/52!]^2
    ≈ n^3/(2(52!)^2),

which is relatively small. (That's stronger, here, than just saying that it is small.) That is to say: I guess I agree with jgershen after all!

A quick search turns up this link. Looks like the birthday paradox does not apply in this situation.

http://hatlogic.blogspot.com/2010/04/cards-and-birthdays.htm...

The birthday paradox applies if you are asking about the probability that any two shuffled decks throughout history have matched each other, not the probability that a shuffled deck throughout history matches the exact deck you have in your hands today.

The title of this article as posted on hacker news is "A shuffled deck of cards is unique in all human history".

Note that it does not say "If you shuffle a deck of cards, it will be unique in all of human history," which is the argument that the actual article is making.

The article title here is logically equivalent to "Any shuffled deck of cards is unique in all of human history" which is logically equivalent to "No two shuffled decks of cards in human history are equivalent". Therefore, the title of the article as it appears on hacker news needs to be changed

I don't think it's that important, really

This is also a retort to those who try to say that a universe that supports human life is too unlikely to happen without a creator.

Ignoring the sovereign debt sized hole in the creationist's argument, made obvious by the question "who/what created the creator", my shuffling of a deck of card also results in an almost infinitely unlikely configuration. Despite this, shuffling a deck of card does not make me a god and is quite possible to do without divine intervention.

Neil Stephenson's excellent book cryptonomicon used this as a means to facilitate encrypted communication.

Also makes for a great interview question why a pseudo-random generator initialized with a 64 bit seed will not produce all possible shuffles of a card deck.

Anyone who's studied basic probability in high school should be able to answer that question.

52! > 2^64

That depends on whether you use the first 52 values after the seed as the shuffle or are allowed to produce multiple shuffles from the same seed. In the latter case it also depends on the, unspecified, period of the PRNG.

If the generator memory size is equal to seed size (64 bits), then period can't be larger than 2^64, and that's probably what grand-parent meant.

But generator can have states that are not possible to be set directly by seeding (like when generator has for example 1024 bits of state, but can be seeded from 64 bit int). Then period is larger than 2^64, and grand-parent thesis don't hold.

I work in the gaming (betting) industry and came across this for the first time recently. The customer _demanded_ uniform distribution which meant getting our RNG server to churn out 8 32bit random numbers just to shuffle one deck. Fun.

"When I shuffled the cards this afternoon, and came up with the order you see in the picture, that is one of 8.0658X1067 different possible orders that cards can be in. However, in the past 700 years since playing cards were invented, cards have been shuffled less than 1.546X1023 times. So the chances that one of those times they got shuffled into the same exact order you see here are less than 1 in 100000000000000000000000000000000000000000000 (1 in 1044)." I'm too tired to do the math but isn't this wrong?

As in, is it taking the birthday paradox into account?

http://news.ycombinator.com/item?id=3241304

He is referring to the probability that this specific shuffling has come up before, not the probability that there have ever been two shuffles with the same result (which is where the birthday paradox comes into account).

No, this is one fixed example : Akin to someone in the room having exactly your own birthday.

The birthday paradox is the observation that it's much more likely than you'd think that two people in a room share a birthday - which is equivalent to two decks ever having been shuffled into the same order anywhere.

It doesn't make much sense to calculate out that probability on the figures used in the article, since the author has purposefully over-estimated the number of shuffles ever made.

An even stronger result takes into account the birthday problem (http://en.wikipedia.org/wiki/Birthday_problem).

Claim: No two properly shuffled decks have ever been the same.

Proof: For convenience, set upper bound on # of shuffles = n = 10^23 and number of possible shuffles = N = 10^68. Then the probability that all shuffles are not unique is

q = 1 X (1 - 1/N) X (1 - 2/N) X ... X (1 - (n-1)/N).

Since n << N, even (n-1)/N is small, so we can approximate q as

q = 1 X e^(-1/N) X e^(-2/N) X ... X e^(-(n-1)/N) = e^(-n^2/(2N))

using the series expansion e^x = 1 + x for x << 1.

Then the probability that any two decks have ever matched is

p = 1 - q = 1 - e^(-n^2/(2N)).

Now,

q = e^(-5 * 10^(-22)) = 1 - 5 * 10^(-22),

to good approximation, so

p = 1 - q = 5 * 10^(-22)

which is zero for all practical purposes. Thus, no two properly shuffled decks have ever been the same. QED

The real world card shuffling is very different. You move multiple cards together, a few times. I have seen the same pattern of card shuffling being followed by so many people. Sometimes you arrange the cards in your last game, and in the next game you exactly know what card is coming up next in case it didn't change position.

Just wondering but could you say that the more you use a pack of cards, the less random it is?

For example the cards will get wear and tear from constantly being shuffled (especially if you are like me and can't do it well). As the cards get more damaged, they become harder to handle and so becomes harder to shuffle. So less random.. anyone?

Well, the weak point seems to be "harder to handle = harder to shuffle". I do not see why that necessarily is the case. My grandmother used to stubbonly prefer old cards, as newer ones would glide out of her hands.

The increased grip older cards had, actually improved her ability to shuffle.

I think if you bent the corner of several cards, depending on how you shuffle the cards it might affect how random they are.

Reminds me of a previous thread. Stacking decks in your Texas Hold'em favor:

    http://news.ycombinator.com/item?id=113299

The analysis presented here assumes proper randomisation of the deck. In reality this is extremely unlikely as most people are pretty bad shufflers. Coupled with the fact that decks are manufactured with cards ordered, I bet a number of card sequences _have_ occurred more than once, and maybe many times.

Readers may also enjoy this discussion of how many moves a chess player has to make before he is playing a game unique in human history:

http://www.radiolab.org/2011/aug/23/rules-set-you-free/

This just in: properly chosen random numbers with lots of bits are probably unique

Though the number of distinct bridge deals is much smaller, the same is probably true even for bridge deals. If my math's ok then there's about 2^107 distinct bridge deals, assuming identifiable players.

I am Matthew Weathers, the author of the paged referenced here. Thanks for all the comments and insightful ideas. I've added an update to the page to include some of the ideas you all have mentioned.

Very nice approach for explaining the randomization! We can conclude one thing about the article, and the thing is that the perfect shuffle does not matter that much!

nothing like a little combinatorics nostalgia to brighten up your day, best post today! 52!

Reply on news.ycombinator.com