# Math Help - Counterintuitive???

1. ## Counterintuitive???

Okay, there is a lot of debates about the answer to this question in class. Most of the proposed solutions are plausible, but I'm not going to list them because I don't want to give ideas.

But here is the question:

If you have two randomly shuffled deck of cards of 52 cards per deck, and put both decks side by side.... then you flip the 1st cards from both decks and compare them, and you do the same for the 2nd, 3rd, and subsequent cards in the deck until you compare all the cards.... what is the probability that there is at least 1 EXACT match out of 52?

What do you think is the answer? And why? THanks

2. Two things:

1) [1 - Pr(none)] seems quite a bit easier.
2) What's the point of randomly shuffling BOTH decks?

3. Originally Posted by TKHunny
Two things:

1) [1 - Pr(none)] seems quite a bit easier.
2) What's the point of randomly shuffling BOTH decks?

It's an advanced 4XXX class. I know all those common formulas and techniques. There were disagreements during the lecture. My post is requesting the final answer, not what would be easier.

4. Hasn't the answer got something to do with $\frac 1 e$? I vaguely remember this from my own studies, and Martin Gardner mentioned this one in one of his famous columns in Scientific American.

It's the same as the shuffled letters problem - the incompetent secretary who stuffed letters at random into the envelopes. The proportion of the number of people getting their correct letters by chance tends to $\frac 1 e$ as the number of people tends to infinity.

5. Originally Posted by TitaniumX
Okay, there is a lot of debates about the answer to this question in class. Most of the proposed solutions are plausible, but I'm not going to list them because I don't want to give ideas.

But here is the question:

If you have two randomly shuffled deck of cards of 52 cards per deck, and put both decks side by side.... then you flip the 1st cards from both decks and compare them, and you do the same for the 2nd, 3rd, and subsequent cards in the deck until you compare all the cards.... what is the probability that there is at least 1 EXACT match out of 52?

What do you think is the answer? And why? THanks
Simulation suggests $0.6311 \pm 0.0015,\ (1 \sigma)$

CB

6. Originally Posted by CaptainBlack
Simulation suggests $0.6311 \pm 0.0015,\ (1 \sigma)$

CB
Thanks.

The professor said the answer was 1-(51/52)^52 = 0.6357

I told him I thought it was 0.6321 by generalizing with smaller sets, and then computing the answer making a huge mess, but I'm 99.8% it's correct.

Of course, the two answers are so CLOSE to each other. What do you think about the professor's answer? Do you think it's correct?

7. Originally Posted by TitaniumX
Thanks.

The professor said the answer was 1-(51/52)^52 = 0.6357

I told him I thought it was 0.6321 by generalizing with smaller sets, and then computing the answer making a huge mess, but I'm 99.8% it's correct.

Of course, the two answers are so CLOSE to each other. What do you think about the professor's answer? Do you think it's correct?
I have done a higher prescission run and get a Monte-Carlo (MC) estimate $\widetilde{p}=0.6317 \pm 0.00048, (1\; \text{SE})$, so assuming no major error in the simulation a value as high as $0.6357$ is implausible (its more than 8 standard errors from the MC estimate), while $0.6321$ is within $1\; \text{SE}$ of the estimate.

CB

8. Originally Posted by CaptainBlack
I have done a higher prescission run and get a Monte-Carlo (MC) estimate $\widetilde{p}=0.6317 \pm 0.00048, (1\; \text{SE})$, so assuming no major error in the simulation a value as high as $0.6357$ is implausible (its more than 8 standard errors from the MC estimate), while $0.6321$ is within $1\; \text{SE}$ of the estimate.

CB
Thank you again for input; it's much appreciated. Also, if 2SD captures approximately 95% of the population, I'm assuming 8SD captures more than 99.999999% at the very least?

BTW, what program do you use to conduct the Monte Carlo simulations?

Does anyone what's the best way to tell the professor why 1-(51/52)^52 isn't the correct answer?

9. Originally Posted by TitaniumX
Thank you again for input; it's much appreciated. Also, if 2SD captures approximately 95% of the population, I'm assuming 8SD captures more than 99.999999% at the very least?
Does anyone what's the best way to tell the professor why 1-(51/52)^52 isn't the correct answer?
One way to work this mathematically is to use derangements.
That is the number of permutations in which every term is active.
Line numbers up so that none is in its correct place.
You may have seen ‘hat check’ or ‘letter stuffing’ problems.

Those numbers are given as $D_n = n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}$.
So as Matt Westwood noted above we can approximate $D_n \approx \frac{{n!}}{e}\;,\,n \geqslant 4$.

So in this problem we use $1 - \frac{{D(52)}}{{52!}} = 0.632120558828558$.

You could simply show your professor what you have found. There are multiple methods here, but one answer.

10. Originally Posted by TitaniumX

BTW, what program do you use to conduct the Monte Carlo simulations?
Well I use Euler but any of the Matlab like systems will do, though in some you may have to provide your own random permutation generator.

(for problems like this a Monte-Carlo estimate is always useful as a reality check on other calculation methods, also it takes only a few minutes to write and only a little more time for the odd million replications).

CB

11. Originally Posted by TitaniumX
Thanks.

The professor said the answer was 1-(51/52)^52 = 0.6357

I told him I thought it was 0.6321 by generalizing with smaller sets, and then computing the answer making a huge mess, but I'm 99.8% it's correct.

Of course, the two answers are so CLOSE to each other. What do you think about the professor's answer? Do you think it's correct?
Here is the case for the professor's answer.

Let's say that $M_i$ is the event of a match on the ith pair. Then $\Pr(M_i) = 1/52$, and $\Pr(M_i^c) = 51/52$. So the probability that there are no matches in 52 pairs is $\Pr(M_1^c M_2^c \cdots M_{52}^c) = \Pr(M_1^c) \Pr(M_2^c) \cdots \Pr(M_{52}^c) = (51/52)^{52}$.

This is wrong. The fallacy is that it assumes independence of events among $M_1, M_2$ etc. To see that the events are not independent, suppose we have matches on 51 of the pairs. What is the probability of a match on the 52nd pair? 1, because it is forced.

Plato's solution is correct.

12. Originally Posted by TitaniumX
If you have two randomly shuffled deck of cards of 52 cards per deck, and put both decks side by side.... then you flip the 1st cards from both decks and compare them, and you do the same for the 2nd, 3rd, and subsequent cards in the deck until you compare all the cards.... what is the probability that there is at least 1 EXACT match out of 52?
This game was known in the 18th century as the "Jeu de rencontre" ("Meeting game"), and it was an open question as to which player is the most likely to win (if the players are betting on the presence/absence of a match), until Leonard Euler settled the question in a paper published in 1753 and obtained the celebrated match probability $\simeq1-\frac{1}{e}$.

You may find interesting to have a look at Euler's paper (translated to English).

13. Thanks for that, Laurent - it's the first time I've ever read a paper by Euler. I never realised that he was available online. I'd always heard he was an excellent writer - now I know for sure. If every textbook was written as clearly as that, the world would have more mathematicians in it.