7 ms·
A shuffled deck of cards is unique in all human history
- capex 15y agoThe 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.
- lutorm 15y agoNice. 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.
- codebaobab 15y agoActually, a deck of card is random after 7 shuffles. http://en.wikipedia.org/wiki/Shuffling#Randomization http://en.wikipedia.org/wiki/Shuffling#Randomization
- corprew 15y agoActually, 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.
- jfoutz 15y agoeven if you're preserving blocks of 3, 17! is a big number. it's not 10^44, but still, 10^14 is pretty big.
- mturmon 15y agoThat 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?view=body&id=pdf_1&handle=euclid.aoap/1177005705 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/ 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?
- dubya 15y agoSort 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.
- omaranto 15y agoYeah, 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
- bigbird 15y agoThe 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".
- baddox 15y agoIf 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.
- lutorm 15y agoWhat 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.
- eru 15y ago> Of course, once you cut the deck a few times, [...] Do you mean to do the cuts one after another?
- subwindow 15y agoThe 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.
- Avshalom 15y agoI 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.
- prodigal_erik 15y agoSee also http://en.wikipedia.org/wiki/Solitaire_(cipher) http://en.wikipedia.org/wiki/Solitaire_(cipher) which uses a deck as an innocent-looking keystream having a lot of entropy.
- eddington 15y agoIt should be noted Solitaire is not secure for long messages. http://www.ciphergoth.org/crypto/solitaire/ http://www.ciphergoth.org/crypto/solitaire/
- Cushman 15y agoWhat'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 :)
- staktrace 15y agoDoesn't the birthday paradox also come into play here, significantly increasing the chances of a duplicated shuffle?
- jfoutz 15y agoThe 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.
- sliverstorm 15y agoIn 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.
- jgershen 15y agoActually, 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.
- sliverstorm 15y agoAlright, fine, it is comparatively lower. Better? :)
- gregable 15y agoNice, 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.
- deleted 15y ago[deleted]
- deleted 15y ago[deleted]
- efsavage 15y agoMakes 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.
- jellicle 15y agoDone! http://www.schneier.com/solitaire.html http://www.schneier.com/solitaire.html
- decklin 15y agoIn 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.)
- dantheman 15y agoThis is a plot point in Neal Stephenson's Cryptonomicon.
- brudgers 15y agoI believe there is also an appendix providing details.
- deleted 15y ago[deleted]
- ColinWright 15y agoDon't think so. 52! is about 10^68, which is over 225 bits. log2(52!) ~ log2((52/e)^52.sqrt(2.pi.52)) ~ 225.58
- fberger 15y agoAlso 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.
- guns 15y agoAnyone who's studied basic probability in high school should be able to answer that question. 52! > 2^64
- Confusion 15y agoThat 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.
- ajuc 15y agoIf 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.
- smokinn 15y agoNeil Stephenson's excellent book cryptonomicon used this as a means to facilitate encrypted communication.
- gry 15y agoReminds me of a previous thread. Stacking decks in your Texas Hold'em favor: http://news.ycombinator.com/item?id=113299
- comenter 15y agoVery 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!
- TomGullen 15y ago"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?
- tedunangst 15y agohttp://news.ycombinator.com/item?id=3241304 http://news.ycombinator.com/item?id=3241304
- monjaro 15y agoHe 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).
- mdda 15y agoNo, 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.
- BenoitEssiambre 15y agoThis 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.
- deleted 15y ago[deleted]
- sycren 15y agoJust 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?
- MrJagil 15y agoWell, 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.
- sycren 15y agoI think if you bent the corner of several cards, depending on how you shuffle the cards it might affect how random they are.
- praptak 15y agoThough 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.
- danbmil99 15y agoThis just in: properly chosen random numbers with lots of bits are probably unique
- acron0 15y agoI 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.
- celticjames 15y agoReaders 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/ http://www.radiolab.org/2011/aug/23/rules-set-you-free/
- retube 15y agoThe 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.
- Duff 15y agoI'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.
- thewisedude 15y agoI 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.
- epynonymous 15y agonothing like a little combinatorics nostalgia to brighten up your day, best post today! 52!
- deleted 15y ago[deleted]
- mhartl 15y agoAn even stronger result takes into account the birthday problem (http://en.wikipedia.org/wiki/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
- MatthewWeathers 15y agoI 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.