0
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ I have no idea what you are asking. What does shuffling a deck of cards have to do with the birthday paradox? $\endgroup$ – 5xum Mar 6 at 11:23
  • $\begingroup$ @5xum The probability of a collision. $\endgroup$ – JWRM22 Mar 6 at 11:24
  • 1
    $\begingroup$ By the way, $52!! \neq (52!)!$. $\endgroup$ – Deepak Mar 6 at 11:42
  • $\begingroup$ @Deepak, I learn something new every day. :) $\endgroup$ – JWRM22 Mar 6 at 11:51
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ And yet these sneaky magicians seem to always get the deck shuffled as they intended to! $\endgroup$ – Christoph Mar 6 at 11:57
  • $\begingroup$ Thank you! There is a chance but too tiny to care even when talking about the 10^30 shuffles. Good to know! My curiosity is satisfied. $\endgroup$ – JWRM22 Mar 6 at 12:02
1
$\begingroup$

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\%$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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