Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 14 down vote accepted

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.

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.