4 ms·
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
by lutorm 15y ago
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.
- 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.