Birthday paradox for large numbers

Question

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

Answer 1

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.

Answer 2

I thought about the exact same thing and solved it using a different method.

My exact problem was: How many shuffles do you need to have a $50\%$ chance that at least one shuffle happened twice?

I used a slightly different formula , found here. $n$ is the number of shuffles and $p(same)$ equals $0.5$ in our case.

$$n\approx \sqrt{ 2 \times 365 ln(\frac{1}{1 - p(same)})}$$

Then I applied the formula for numbers other than $365$. Here $\frac{1}{1-p(same)} = 2$, so the formula becomes:

$$n\approx \sqrt{ 2ln(2) \times M}$$

$M$ the number of possibilities. For a birthday it's $365$, for a card deck it's $52!$.

That gives $1.057 × 10^{34}$, which is not that far from "one in a hundredth million for $10^{30}$ shuffles"!

---

Actually I didn't use the second formula, I used the first one and went with a much more empirical approach. I used the code given in the article, changing $M$ to increasingly big numbers and plotting the results in Excel ($n$ as a function of $M$) until I had a satisfying trend curve. That gave a square root curve ($y \approx 1.1773\sqrt{x}$). I applied logarithms to $n$ and $M$, so that $ln(n)$ as a function of $ln(M)$ is linear. Then I used the trend line of that new function ($0.5x + 0.1632$) to get $ln(n)$ for $y = ln(52!)$, I also found $1.057 × 10^{34}$.

I now realize that I did not choose the easiest method...

Answer 3

If you shuffle two decks, the probability of them being in the same order is $$ \frac{1}{52!} \approx 1.24\times 10^{-66} \%. $$

If you shuffle $n$ decks, the probability of a collision is $$ 1 - \left( 1- \frac{1}{52!}\right)\left(1-\frac{2}{52!}\right)\cdots\left(1-\frac{(n-1)}{52!}\right). $$ Are you looking for the smallest $n$ such that this number is at least $50\%$?