Re:A shuffled deck of cards is unique in all human history
by omaranto on Tuesday November 15, 2011 @11:38PM
(#3241794)
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:
[ Parent
| on HN ]
Re:A shuffled deck of cards is unique in all human history
by bigbird on Wednesday November 16, 2011 @09:53AM
(#3243277)
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".