# When you randomly shuffle a deck of cards, what is the probability that it is a unique permutation never before configured?

I just came back from a class on Probability in Game Theory, and was musing over something in my head.

Assuming, for the sake of the question:

• Playing cards in their current state have been around for approximately eight centuries
• A deck of playing cards is shuffled to a random configuration one billion times per day
• Every shuffle ever is completely (theoretically) random and unaffected by biases caused by human shuffling and the games the cards are used for
• By "deck of cards", I refer to a stack of unordered $52$ unique cards, with a composition that is identical from deck to deck.

This would, approximately, be on the order of $3 \cdot 10^{14}$ random shuffles in the history of playing cards.

If I were to shuffle a new deck today, completely randomly, what are the probabilistic odds (out of $1$) that you create a new unique permutation of the playing cards that has never before been achieved in the history of $3 \cdot 10^{14}$ similarly random shuffles?

My first thought was to think that it was a simple matter of $\frac{1}{52!} \cdot 3 \cdot 10^{14}$, but then I ran into things like Birthday Paradox. While it is not analogous (I would have to be asking about the odds that any two shuffled decks in the history of shuffled decks ever matched), it has caused me to question my intuitive notions of Probability.

What is wrong in my initial approach, if it is wrong?

What is the true probability?

And, if the probability is less than $0.5$, if we how many more years (centuries?) must we wait, assuming the current rate of one billion shuffles per day, until we reach a state where the probability is $0.5$+? $0.9$+?

(Out of curiosity, it would be neat to know the analogous birthday paradox answer, as well)

-
The situation is not the same as in the birthday paradox. The birthday paradox works because the two identical birthdays may appear between any two of the persons. However, in your experiment, you demand that you are one of the two persons involved in the same card deck. A situation analogous to the birthday paradox would be given by the question "what is the chance that over the last 600 years, two persons have produced the same random shuffle". – azimut Aug 29 '13 at 17:45

Your original answer of $\dfrac{3 \times 10^{14}}{52!}$ is not far from being right. That is in fact the expected number of times any ordering of the cards has occurred.

The probability that any particular ordering of the cards has not occurred, given your initial assumptions, is $\left(1-\frac1{52!}\right)^{(3\times10^{14})}$, and the probability that it has occurred is 1 minus this value. But for small values of $n\epsilon$, $(1+\epsilon)^n$ is nearly $1+n\epsilon$. In particular, since $52!\approx 8\times 10^{67}$ and so $\dfrac{3\times10^{14}}{52!}\approx 3.75\times 10^{-54}$ is microscopically small, $1-\left(1-\frac1{52!}\right)^{(3\times10^{14})}$ is very nearly $\frac1{52!}\times (3\times10^{14})$.

-
I'm sorry, could you explain what ε represents in this case? – Justin L. Jul 25 '10 at 5:07
In most contexts(including this one) epsilon is a small value. In this case it means the wonderfully small 1/52! Just an aside, not always but in many contexts epsilon is going to be a placeholder for an infinitesimal, or a numberthat we are going to let arbitrarily small. – BBischof Jul 25 '10 at 5:35
What BBischof said is correct. – Michael Lugo Jul 25 '10 at 11:24
Just correcting a phrasing mistake: the final answer, proven to be right, is the probability that the combination is not unique. So the chances to be unique are extremely close to 100%. – Bogdan Alexandru May 20 at 11:05

There are $52!$ possible orders for a deck of $52$ cards. If a unique order of a deck of $52$ unique cards had been created every second since the big bang, the chances that any two of them were repeated is approximated by $$1-(1-1/52!)^{(10^{17})} = 1.2397999\times10^{-51}\ .$$ To show the size of this number, assume that the same shuffling has taken place every second on one planet orbiting every one of the estimated $10^{24}$ stars in the known universe since the beginning of time. The chances that all of those orders has been unique is still $$99.999999999999999999999999876\%\ .$$ Go shuffle a deck of cards six times and create something truly unique!

-

Suppose we shuffle a deck and get a permutation p. For each previous shuffling there is a 1-1/52! chance that p doesn't match it. Each previous shuffling is independent, in that regardless of what p and the other permutations are, the chance of p matching the shuffling is 1-1/52! When probabilities are independent we can simply multiple them to find the chance of all the events happening. In this case, the each event is actually a match not happening, so the chance of no matches given n previous shuffles is (1-1/52!)^n. We can then complete the calculations as Michael did.

-

You're right to question your assumptions and right that the formula you give ($n=$number of shuffles that have been made/$N=$number of possible shuffles) isn't quite right (as others have noted), but unlike the birthday paradox, here the difference works to lower the chances of a match, not raise them. Working with smaller numbers helps with the intuition a bit: suppose that there have been $n$ rolls of a $N=$20-sided die, and you want to know what your chances are of hitting a match to some previous roll. Then a reasonable first approximation for small $n$ is that the probability of a match is $n/20$: this is correct for $n=0$ and $n=1$, and it matches the 'intuition' of having $n$ previous rolls to match against. But bumping the number up to $n=20$ shows the breakdown of the approximation; after 20 rolls, your odds aren't 100% of rolling a number that's already been rolled once, and after 21 rolls they certainly aren't greater than 100%!

The flaw here, of course, is that after $n$ rolls there won't have been $n$ unique numbers rolled; instead, there are likely to already be some duplicates. But it's also clear from thinking about the probability this way that the odds of a match on your next shuffle (or roll) must be less than what the odds would be if all the previous shuffles were unique, and so must be less than the $n/N$ approximation that you use (with $n=3\times 10^{14}$ and $N=52!$).

(There's also a relatively intuitive way of looking at the birthday paradox that explains its 'paradoxical' nature; there you're not trying to match one thing against $n$, but $n$ things against each other - so the correct quantity to use isn't $n$ itself, but instead the number of possible matches, $n(n-1)/2\approx n^2/2$, with each one (heuristically) having a $1$ in $N$ chance of actually matching; this is why you can start expecting a match for a value of $n$ that's proportional to $\sqrt{N}$ rather than for a value of $n$ that's proportional to $N$.)

-

You would never ever get a deck of cards in the same order. The odds of doing so would be 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000. This is done by 52 factorial!

-
These are the odds of shuffling a deck of cards and finding them in one particular order. These are not the odds of shuffling a deck of cards and finding them in an order seen in any of the $3\times10^{14}$ shuffles that have happened before, as the question asks. – Rahul Nov 3 '12 at 15:31
Nice try though @DavidH. Welcome to MSE. – Alexander Gruber Nov 3 '12 at 17:09
"never ever" is a little exaggerated, but works. +1. – Anonymous Pi Sep 12 '13 at 12:54

Applying the birthday paradox logic when calculating the chance a 52 cards deck order has been shuffled before in the history of mankind.

x= the number of times a 52 deck of cards has been shuffled before in the entire history.

p = 1 - ((52!)! / 52!^x * (52!-x)!)

This part is highly speculative: Lets say there have lived 30 Billion humans in the last 800 years that playing cards been around. When somebody play cards 1x a month for 50 years he shuffles 600 times. Some people never play cards, other way more than once a month. Lets take 600 times in a lifetime as an average, then in the entire history there would been 18000 billion shuffles.

Now comes a practical problem it's easy to fill in 18000 Billion for x but I can't find a calculator who can handle the big numbers involved in the the calculation and I lack the math skills to solve the calculation in a different way.

-
He said that the birthday paradox variant of this problem isn't the one he has in mind: in that version of the question, you're not asking whether or not a particular shuffle has ever happened before, but rather just whether or not any two shuffles in the history of mankind were the same. Anyway, if we do use your numbers and use the birthday paradox version of the problem as you suggested, we get $p \approx 2 \times 10^{-42}$. – Nathaniel Johnston Oct 24 '14 at 18:36