I'm attempting to test the claim:
"Every card deck shuffled is unique. A shuffled deck of cards will exist once and never again."
Assumption: A perfect world where a deck of cards is perfectly random all of the time. 52 cards are used in the deck.
The birthday paradox and it's easy enough to calculate for small numbers. 23 people and 365 birthdays as used in the 50% examples. But how do you approach (or approximate) the birthday paradox for values like 52!?
I understand 52! is a large (~226 bit) number but I would like to get a feel of the order of magnitude of the claim. Is it 1% or 0.00001%?
To calculate the probability of a shuffle collision would be:
(52!)!/(52!^n*(52!-n)!)
I understand the formula. But 52!! is incomputable so where do I go from here? How to approach a problem like this?
This is just for my own curiosity and not homework. If it can be done for a deck of cards I'd want to give it a try on collisions in crypto keys. (RSA, and AES256 etc.)
Best Answer
A simple estimate: given $n$ random variables, independently and identically distributed evenly over $M$ states, the probability that some two of them are equal is at most $\frac{n(n-1)}{2M}$. Why? Because that's the expected value for the number of pairs that are equal; there are $\binom{n}{2}$ pairs, each with a probability of $\frac1M$ of being equal.
So then, if $n$ is significantly less than $\sqrt{M}$, the probability of some two being equal is small.
Now, we focus on the shuffling problem. How big is $52!$, really? For that, we have Stirling's formula: $$n!\approx \frac{n^n}{e^n}\cdot\sqrt{2\pi n}$$ Take logarithms, and we get $n(\log n-\log e)+\frac12\log(2\pi n)$. Calculating that in the spreadsheet I've got open already, I get a base 10 log of about $67.9$, for about $8\cdot 10^{67}$ possible shuffled decks.
So, then, if we take $10^{30}$ shuffles, that's a probability of less than $\frac{5\cdot 10^{59}}{8\cdot 10^{67}}< 10^{-8}$ (one in a hundred million) that any two of them match exactly. That $10^{30}$ - if you had a computer for every person on earth, each generating shuffled decks a billion times per second, the planet would be swallowed up by the sun before you got there.