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.

So I wanted to figure out a meaningful probability for the card deck order problem. I chose arbitrary values in an attempt to show the magnitude of permutations:

If you and everyone on the Earth right now shuffled a million randomized decks every millisecond that universe has existed, the probability that any two decks at one moment were the same would be:

What is the probability?

share|improve this question
add comment

2 Answers

Here is what I came up with and my assumptions. Please point out any errors.

First, I attempted to find the probability of 2 people having the same deck order of N people shuffling decks in one trial. I could not figure out how to model it in a more standard way, so my leap of faith was that for N people, there were (N+N-1+N-2+...)=Nt. For 6.7e9 people on Earth, that's 2.2445*^19 pairs of people. The probability that one pair had the same deck order was (1/52!) = 1/8e67 = p1. Since the events are not independent, I need to multiply by (52!)!/(52!-N).

Next, I wanted the probability that any of them had a match. So that would be 1 minus the probability that none of them had any matches:
(1 - (52!)!/(52!-N)*(p1)^0*(1 - p1)^(Nt)) = (1 - (52!)!/(52!-N)*(1 - p1)^(Nt)) = p2.

Now, I wanted to do a million randomized trials every millisecond that the universe existed. So that's 1.4e10 years * 365 days/year * 24 hours/day * 3600e3 ms / hour * 1e9 trials/ms = T = 4.5e29. Again, I wanted at least one match, that would bring it to:
(1 - (1 - p2)^(T)) = (1 - (1 - (1 - (52!)!/(52!-N)*(1 - p1)^(Nt)))^(T)) =
(1-(1-(1-(52!)!/(52!-6.7e9)*(1-1/8e67)^(2.2445*^19)))^(4.5e29)) = 6.31 × 10^-20

share|improve this answer
    
$p_1$ is $1/52!$, which should not be squared. The calculation of $p_2$ is incorrect because the probability that Alice and Bob have the same order is not independent of the probability that Alice and Carol have the same order - see the en.wikipedia.org/wiki/Birthday_Problem . –  aschepler Oct 3 '10 at 8:04
    
I figured that assumption was wrong somewhere and had forgotten about the birthday paradox. So I just need to multiply p2 by 52!/(52!-Np)? –  Eruditass Oct 3 '10 at 17:53
    
Yes, part of the calculation is similar to that of the birthday problem. It's the line with the product sign in my answer. –  Derek Jennings Oct 3 '10 at 17:56
    
Actually, wouldn't it be (52!)!/(52!-N)! –  Eruditass Oct 3 '10 at 18:03
    
When m people shuffle in the first step, person 1's card can be in any order, person 2's cards cannot be in the same order as the 1st person's, and this probability is (1 - 1/n), the 3rd peron's card must be different from the first two, and that probability is (1-2/n), and so on up to the last person (n=52!). We thus multiply all these probabilities together to obtain the probability that no two are identical. –  Derek Jennings Oct 3 '10 at 18:45
add comment

Let's make some assumptions for the purposes of calculation. Suppose 6.7 billion people have been alive for 13.5 billion years each shuffling one deck a thousand times a second.

The total number of rounds of shuffles $N=1000 \times 3600 \times 24 \times 365 \times1.35 \times 10^{10}.$ So $N = 4.25736 \times 10^{20}.$ Let $n=52! \approx 8.0658 \times 10^{67}$ and let $m=6.7 \times 10^9.$

When everyone shuffles the cards once in the first millisecond the probability that they are all different is $$ \prod_{i=1}^{m-1} \left( 1- \frac{i}{n} \right) \approx 1 - \frac{m(m-1)}{2n},$$ ignoring the cross products since $n$ is much bigger than $m$.

Each shuffle is independent, so after $N$ steps the probabilty that we have had no match is $$\left( 1 - \frac{m(m-1)}{2n} \right)^N \approx 1 - \frac{m(m-1)N}{2n}, \qquad (1)$$ since $m(m-1)/2n$ is very small.

Hence the probability that there has been a match is 1 minus RHS of (1), that is $$\frac{m(m-1)N}{2n}.$$

I make this about $1.18 \times 10^{-28}$ with the figures I've used.

REMARK: Note that if you drop the "at one moment" requirement. That is, if you now ask if two shuffles have ever been the same, the problem is slightly quicker. The total number of shuffles that have ever taken place is $mN$ and so the probability that they were all different (as in the birthday problem) is $\prod_{i=0}^{mN-1} \left( 1- \frac{i}{n} \right),$ where as before $n=52!,$ So the probability that we've had a repeat is $1- \prod_{i=0}^{mN-1} \left( 1- \frac{i}{n} \right),$ which, similar to before, is approximately $mN(mN-1)/2n,$ or $5 \times 10^{-8}.$

Note that as the index $i$ in the product gets larger, better approximations are obtained by passing to logarithms (as on the wikipedia page).

share|improve this answer
    
What is the equation you are using to calculate it called? And which product sign are you referring to? m(m-1)/2 is the total # of pairs, but I don't see the dependent events factor of (correct me if its wrong) (52!)!/(52!-m)! –  Eruditass Oct 3 '10 at 18:05
    
The product sign I'm referring to is the one taken from i=1 to m-1 and the m(m-1)/2 factor comes from summing 1+2+...+(m-1). Each shuffle is independent from the previous shuffle, so if the probability that no match occurs is a shuffle is p, then after 2 shuffles it p^2, that we've still had no match, p^3 after three, and so on. –  Derek Jennings Oct 3 '10 at 18:22
    
You can see the product formula used in the birthday problem on the wikipedia page given by aschepler in his comment on your question. I've just noticed a typo in my previous comment, it should be "in a shuffle," of course. –  Derek Jennings Oct 3 '10 at 18:30
add comment

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.