Results 1 to 13 of 13

Math Help - Counterintuitive???

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    53

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,111
    Thanks
    2
    Two things:

    1) [1 - Pr(none)] seems quite a bit easier.
    2) What's the point of randomly shuffling BOTH decks?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    53
    Quote Originally Posted by TKHunny View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by TitaniumX View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Sep 2008
    Posts
    53
    Quote Originally Posted by CaptainBlack View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by TitaniumX View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Sep 2008
    Posts
    53
    Quote Originally Posted by CaptainBlack View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,708
    Thanks
    1638
    Awards
    1
    Quote Originally Posted by TitaniumX View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by TitaniumX View Post

    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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by TitaniumX View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by TitaniumX View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    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.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum