A shuffled deck of cards is unique in all human history

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.

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

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.

I'd amend this to say "A PROPERLY shuffled deck of cards is unique in all human history".<p>Without proper shuffling, a card deck is like an encryption key with a poor initialization vector -- it's more predictable.<p>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.

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

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

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?<p>As in, is it taking the birthday paradox into account?

An even stronger result takes into account the birthday problem (<a href="http://en.wikipedia.org/wiki/Birthday_problem" rel="nofollow">http://en.wikipedia.org/wiki/Birthday_problem</a>).<p>Claim: <i>No two properly shuffled decks have ever been the same.</i><p>Proof: For convenience, set <i>upper bound on # of shuffles</i> = <i>n</i> = 10^23 and <i>number of possible shuffles</i> = <i>N</i> = 10^68. Then the probability that all shuffles are <i>not</i> unique is<p><i>q</i> = 1 X (1 - 1/<i>N</i>) X (1 - 2/<i>N</i>) X ... X (1 - (<i>n</i>-1)/<i>N</i>).<p>Since <i>n</i> &#60;&#60; <i>N</i>, even (<i>n</i>-1)/<i>N</i> is small, so we can approximate <i>q</i> as<p><i>q</i> = 1 X <i>e</i>^(-1/<i>N</i>) X <i>e</i>^(-2/<i>N</i>) X ... X <i>e</i>^(-(<i>n</i>-1)/<i>N</i>) = <i>e</i>^(-<i>n</i>^2/(2<i>N</i>))<p>using the series expansion <i>e</i>^<i>x</i> = 1 + <i>x</i> for <i>x</i> &#60;&#60; 1.<p>Then the probability that any two decks have ever matched is<p><i>p</i> = 1 - <i>q</i> = 1 - e^(-n^2/(2N)).<p>Now,<p><i>q</i> = <i>e</i>^(-5 * 10^(-22)) = 1 - 5 * 10^(-22),<p>to good approximation, so<p><i>p</i> = 1 - <i>q</i> = 5 * 10^(-22)<p>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?<p>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?

Reminds me of a previous thread. Stacking decks in your Texas Hold'em favor:<p><pre><code> http://news.ycombinator.com/item?id=113299</code></pre>

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:<p><a href="http://www.radiolab.org/2011/aug/23/rules-set-you-free/" rel="nofollow">http://www.radiolab.org/2011/aug/23/rules-set-you-free/</a>

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!