I'm trying to solve the question as to whether two 52 card shuffles have ever been the same but I can't calculate the final step. Additionally I can't find any answer on the internet that has approached the question in the same way. If anyone can help explain what I'm doing wrong, I'd greatly appreciate it.
Assumptions:
- Every card shuffle is independent with probability 1/52!
- There have been $n$ card shuffles in all of history
My solution thus far:
Consider the first person to ever shuffle a deck of cards. Let's call the resulting shuffle X1. What is the probability that X1 is never repeated? This is $(1-1/52!)^{n-1}$
Consider the second person to ever shuffle a deck of cards. Let's call the resulting shuffle X2. What is the probability that X2 is never subsequently (aka given X2 is not itself a repeat of X1) repeated? This is $(1-1/52!)^{n-2}$
If we carry this logic on, then the probability of $(n-1)^{th}$ shuffle (we'll call this Xn) being subsequently repeated will be $(1-1/52!)^{1}$
Therefore the probability that no shuffles has ever been repeated is
$(1-1/52!)^{n-1} \times (1-1/52!)^{n-2}... \times (1-1/52!)^{1}$ = $(1-1/52!)^{(n-1)!}$
Calculations Now I think the next step would be set this equal to $1/2$ and solve for $n$.
Notice the following:
When $n = 1$, $(1-1/52!)^{(n-1)!} \approx 1$
As $0 < 1-1/52! < 1$, therefore $\lim_{n\to\infty}(1-1/52!)^{(n-1)!} = 0$
Therefore there must be values of $n$ that we'll call $(a,b)$ (where $a = b+1$) which will give the following result:
$(1-1/52!)^{(a-1)!} > 0.5$
$(1-1/52!)^{(b-1)!} < 0.5$
So my query is:
How do I calculate $(a,b)$? The software I've tried (Excel and R) just simplify $1-1/52! = 1$ so I haven't been able to proceed with the calculation.
Are my workings sound? I can't find anyone else who has $(n-1)!$ as their power. Have I made a logical error?
Thank you.
Your approach is fine, but the usual one is to say the first shuffle is guaranteed to be unique, the second is unique so far with probability $1-\frac 1{52!}$, the third is unique so far with probability $1-\frac 2{52!}$ and the $n^{th}$ is unique so far with probability $1-\frac {n-1}{52!}$. Then you multiply these all together and compare with $\frac 12$. That doesn't give the $(n-1)!$ in the exponent, which is why you haven't seen it.
The Wikipedia page on the birthday problem shows that for large numbers $n$ of possibilities, and $52!$ is certainly large, the number of tries to get a $50\%$ chance of a match is $\sqrt {2 (\log 2) n}$. Taking $n=52!$ we get about $1.05\cdot 10^{34}$. That is huge compared to the number of person-seconds in history, so the chance of a duplicate is miniscule.