# The probabilty of a new arrangement of 52 cards deck?

I just read this article, it claims that if you just shuffle a 52 card deck, you will mostly be creating an arrangement that no human have ever seen before.

But this doesn't seem right since every time we create a new arrangement, this one is now a candidate to happen again, so every time we fail, the odds increase.

How can we mathematically review this claim?

-

The number of arrangements is $52!$. Using a tool like Wolfram Alpha, or by using the Stirling approximation,, or even just a scientific calculator, we find that $52!$ is larger than $8\times 10^{67}$.

Assume, outrageously, that there have been $10$ billion people on Earth for $10000$ years, each shuffling and dealing a deck of cards every second. In $10000$ years, there are fewer than $3.2\times 10^{11}$ seconds. Multiplying by $10$ billion gets us $3.2\times 10^{21}$ shuffled decks, far short of $8\times 10^{67}$, which is a seriously large number. So a very tiny fraction of the possible hands has been dealt.

It is now probably intuitively reasonable that if all orderings are equally likely, then with probability close to $1$, all orderings have been different. But the intuition can be unreliable (witness the Birthday Problem). So we make a more detailed estimate. It turns out that the relevant fact is that the square of $3.2\times 10^{21}$, though huge, is a very tiny fraction of the number of possible deals.

Mathematical details: Suppose that there are $N$ different arrangements of cards, and that we shuffle and deal the cards out independently $n$ times, where $n$ is smaller than $N$. Then the probability that all the results are different is $$\frac{N(N-1)(N-2)\cdots(N-n+1)}{N^n}.$$ The top is bigger than $N-n$, so the probability is bigger than $$\left(1-\frac{n}{N}\right)^n.$$ Using the fact that $\left(1-\frac{x}{k}\right)^k$ is approximately $e^{-x}$, we find that the probability the results are all different is $\gt e^{-n^2/N}$.

Let $N=52!$, and let $n$ be our absurdly high number of $3.2\times 10^{21}$ shuffles. If $x$ is close to $0$, then $e^{-x}$ is approximately $1-x$. Thus the probability the shuffles are all different is greater than $1-\frac{n^2}{N}$. (A better estimate gives that it is approximately $1-\frac{n^2}{2N}$.) This is a number which is very close to $1$. The probability there has been one or more repetition, even with $n$ grossly overestimated, is less than $10^{-25}$.

The probability of at least one match grows rapidly as $n$ grows. Already at $n=10^{33}$, it is roughly $6\times 10^{-3}$, not large but certainly not negligible.

-
oh large numbers. but, what if the universe was always here, and never had a beginning? that is it has been existing for infinite years. –  Claudiu Jul 14 '12 at 1:51
@Claudiu: If the universe has gone on forever, as has card playing, then with probability $1$ there has been repetition, indeed with probability $1$ every possible shuffle has occurred infinitely many times. However, even if the universe has been around forever, there is little reason to think that our standard $52$ card deck has been. –  André Nicolas Jul 14 '12 at 2:02
@ajax333221: I have added some more detailed calculations. –  André Nicolas Jul 14 '12 at 2:05