What is the probability of taking two shuffled decks and by dealing cards from both at the same time, to get a match somewhere along the deal?

The probability of not getting any matches is:
(51/52)to the 52nd power. So the probability of getting at least one match would be 1 minus that amount. The probability of only one match of course is less than that but I'll leave that for others to calculate.

Larry, what is the average number of cards you’d need to deal from both piles before finding a matching pair?

Larry, I'm not sure that's a correct analysis. I think it's more complicated than that. Here's why:

Imagine a two card deck, just an Ace and King of Spades. Now someone else has the same two card deck. By your analysis, the chance that neither card matches is 1/2 x 1/2 =1/4. But a little observation will show that this is not true, because after all the cards can only be dealt two ways--Ace, King or King, Ace. That is, the chance of not ever matching in this case is 1/2, not 1/4. In the same way, with 52 cards the chances of not ever matching is not simply 51/52 to the 52nd power. The problem is , you see, that once you deal out one non-matching card, the pool of remaining cards diminishes.

As for Jon's question, that is even more difficult, and probably would best be solved with a computer simulation program.

I admit though I'm not smart enough to figure this out. Tomas, where are you?!

Jack Shalom

I think that shows probability problems are not so easy to solve just like that.
I believe the real answer approaches 65% more or less.

What's interesting is that Larry's suggestion actually converges to the correct solution as the number of items increase. He wrote that there's no matches with a probability of (1-1/n)^n which, as n->infinity, becomes 1/e. This does not converge as quickly as the correct formula though, which is:

k=n
sum (-1)^k / k!
k=0

Already at four items a good approximation for that sum is 1/e and it converges very quickly. At ten items it already looks like 1/e to around eight decimal places, so for all purposes we can simply say that the probability of at least one match when dealing with more than four items is 1-1/e which is about 0.6321.

A good solution to this problem can be found at:

http://www.math.uwaterloo.ca/navigation/......Sol.html

I'd very much like to see any other ways of attacking this problem.

/Tomas

To increase the chances of a match I usually deal the cards alternately from the two decks, so that even if cards are off by one in position you get a match. I simulated the probability for at least one match to 0.864.

Note that this probability is still true regardless if one deck is stacked. That's not much of a leap, but consider what can be done. Here are a few ideas:

1. Have three cased decks on the table. They are secretly in the same order. Let the spectator take one and decide which one you should get. Let him shuffle his deck while you false shuffle yours. Deal cards alternately face up to the table, starting with a card from his deck, counting loud for each card dealt from your _own_ deck. Maybe you'll get a match on the count of 15. Remember that the match can occur when you deal your card, or when the spectator deals a card after you dealt yours. Play this up as spectators usually think that the chance of even one such coincidence is minimal. Have them remove the third cased deck and count down to card number 15 (in this case) where the coincidence happened. They will find a perfect match on that card! Should you get no matches during the deal just shuffle (yours falsely) the decks again and redeal. If they think it was just luck you can repeat the trick.

2. You can do a packet version of the above trick by using three packets of Ace through King in identical orders. You'll note that the sum oscillates as items increase so that for an odd number of items the chance of a match is _always_ greater than for an even number of items. So 13 card packets is a good thing.

3. Prepare two red decks in the same order. Write the numbers 1 through 52 on the cards in one deck and place a blue backed joker on top of it. Bring out the two decks and false shuffle the "blue" deck as the spectator shuffles the red. Deal cards alternately to the table with the decks face up and count every time you deal a card from the "blue" deck. Show the incredible match and secretly switch the position of the two cards when you place them back on the decks. Put the "blue" deck away. Spread the rest of the red cards to show ordinary backs. Let them check the back on the card where the coincidence happened. They will find the position of the match written on its back.


Other ideas?

/Tomas

Here's another trick where two decks are shuffled fairly by the spectators:

Take one deck and write names of cards on their backs, but make sure that no card gets its own name on its back. The other deck you mark the opposite way, so if you in the first deck have a 7 of Spades with "Three of Clubs" written on its back, you should have a 3 of Clubs with "Seven of Spades" on the back in the second deck.

Show the boldly marked decks, which might get a laugh. People will assume that the faces and what's written on the backs correspond. Have one spectator hold his deck face up and deal cards face up as the other spectator holds his deck face down and deals the cards face down. Stop them when you get a match in writing and face up card. A real magical coincidence of that happening! Turn the face up card over to show that it surprisingly has a different card written on its back. Turn the other face down card over to show that it matches what's written on the other card!


Now, if one deck is false shuffled...can this trick be combined with the idea in my previous post? Sure, you can make a really strange trick with the following effect for example: Two marked decks are shuffled. A third deck is still in its case. Cards are dealt face up and face down until a face matches the writing on a back. This might happen on count 23. When the cards are turned over they show a totally different face (maybe 3 of Clubs) and a totally different writing (maybe "Seven of Spades"). The third deck is uncased and the 23:d card is found to be the 3 of Clubs with "Seven of Spades" written on its back. Sounds infinitely improbable.

/Tomas

Jack and Tomas,
Thanks for the correction. It shows that combination and probability problems can be very sneaky and easy to go astray. I shot from the hip and wound up shooting myself in the foot. No more probability problems late at night for me. The two card deck example that Jack gave shows that the probability for mismatch of the first pair is 1/2 but that then fixes the probability for the second pair mismatch at 1. As Tomas pointed out my solution would work with infinite decks.

Tomas, IMHO, that's one of the best card tricks I've ever read. I think it's on a par with Out of This World. I'm so glad that no one but us math geeks reads this forum. I think you should publish it.

Jack Shalom

Tomas, I also loved it,
especially the second variation!

Great thinking, Tomas. Seems like something Stewart James might have come up with.

Ben Blau

Here's something a few of you might enjoy. This exact same question came up several years ago on MagicTalk. As phrased, the person making the post only asked for the answer, not a method for finding an answer. Bob Farmer posted the correct odds (5:3 For) and I posted a rather lengthy reply that affirmed Bob's answer and offered up some interesting (to me) problems that are virtually identical to this card matching problem. They are the Hat (or coat) Check problem, and the Secret Santa problem.

Well, I got attacked by some guy named James, whose response to me was pretty adamant that I got the wrong answer and didn't know what the heck I was talking about. He was also quick to provide an incorrect answer and he even completely misunderstood the problem from the beginning, thinking it wanted a SPECIFIC match at a predetermined location in the deck. The odds of that are 2703:1 against.

I told him he was wrong in my initial post and placed the correct answer in there as well. Being put in his place apparently didn't sit too well with this guy.

While I unfortunately lost my original post and James's rather poorly written attack on me, I did save my response to his attack, where I put him in his place. I also took him to task on his poorly written reply in a few places. My response to him is below. It's full of quotation marks and >>> signs as I tried to mark off his text for others to be able to pick out. Suffice to say if the passage has all its words spelled correctly and seems to be halfway well written it's probably me. Otherwise it is him.

Here you go, enjoy.

"Sorry James...not even close. "
I stand by this sentence.

>>It should be easy to prove that I made a mistake somewhere in the process... Your call...

First of all, prove has only one "o". Your mistake was answering a problem that hadn't been given.

"What you produced was the probability of a pre-determined card and location being found in both decks. For instance: "the Ace of hearts at 17th in both decks" would indeed have a probability of 1/2704. "

>>Well, okay, that is exactly what I stated at several occasions all along during the demonstration...and that was exactly what was asked, wasn't it ?

A resounding "No!"

>>.... That is exactly what the guy wanted to know: the probability to have one card at a position in one deck and the same card at the same position in another deck... So I don't get your point dude...

What you don't get are the fundamentals of the problem. Yes, that is exactly what the guy asked, which makes you look even worse...you correctly understood what was wanted, provided an incorrect answer, and then jumped all over me for informing you of this. (Your apology next post is duly noted.)

>>"See my response to Bob Farmer for more details on the correct answer. "
Well that is what makes me doubt...There is no proof anywhere of what you are saying...You might be right...you might...BUT you first don't prove that I am wrong and then don't prove any of your statements.

I was too busy providing the CORRECT answer to worry about the details of the proof or the basic formula. This post will try to remedy that. By the way, my addition to Bob's post was in keeping with the original question, which only wanted the answer, not a general formula for finding the answer.

>>As for the "details", I would not call it so...

Again, I only provided a detailed answer, not a detailed proof or general formula...in keeping with the original poster's request.

Please note that any single thing that I assumed was accurately defined (to make sure that any of my statements cold be related to something) and any of my statement was argumented. It does not seem to be the same in your so-called detailed proof. You first start by mentioning a book, which is not a proof in itself...

You know my favorite part of this exchange? The way you keep pointing out that my post to Bob didn't contain a mathematical proof. Did I miss something? Did someone ask for a proof? Or was it just the answer that he wanted? I'll say it for you if it makes you feel better: "I didn't provide a proof for my CORRECT answer to the problem posed."

>>You say: "The answer is .63 (remember, odds is a ratio of winning outcomes to losing outcomes or vice versa, probability is usually expressed as a decimal number from 0 to 1)."
If you define "odds" as a ratio of the winning outcomes to the loosing outcomes, fair enough: if that is your definition that you start with, that's fine. However, the Probability of a winning outcome is NOT the same thing at all, since it is defined as the ratio of the winning outcomes to the TOTAL of possible outcomes (that is, the sum of winning and loosing outcomes).

You're right, the probability of an event is expressed (usually) as the ratio of winning outcomes to total outcomes. And when converted to a decimal, you get a number from 0 to 1. Which is exactly what I said in parenthesis above. (I did leave out what the two numbers that comprise that ratio are, but I assure you I am aware of them.)

>>So, since at this point I don't know where this 0.63 comes from (you don't prove it), I am tempted to think that we are not talking about the same thing. You talk about "Odds" and I talk about mathematical "Probability".

No, I was affirming Bob's statement that the odds were 5:3 in favor by providing the probability of a match somewhere in the two decks.

"Interestingly enough, the probability is the same with any number of cards in a deck after about 10 assuming each card has a mate). ".

>>I am sorry but as soon as Maths are involved, I cannot accept a proof that says "about 10"... TO me it has to be proved and accurate, not "about"...

Well then tell me, what is pi expressed as a decimal? I don't want "about" or "approximately", I want proved (sic) and accurate. Sometimes in "maths" as you put it, approximations are a convenient way of getting information across.

As you will find when you address the proper problem, if the number of cards in the deck is 5, the probability of a match is already .633333. A six card deck? The probability is .63194. Even beyond 10 cards the odds level out to .63212 and then never get any better or worse no matter how many cards your deck contains. (Assuming you don't have duplicates, you would have to of course invent new suits to carry this beyond 52 cards.)

The general formula for finding this is as follows:
1/1 - 1/2! + 1/3! - 1/4! + 1/5! - 1/6! + 1/7! - 1/8! + 1/9! - 1/10!....(-1)n-1/n

"In other words, if you had two groups of cards that each contained the spades from Ace to King, and you tried this little matching experiment, you would find that the probability of a match was still only .63. (.63212 to be precise...an interesting number, this is approximately 1 - 1/2.71828. 2.71828 will be recognized by the math geeks on the board as e, the base of natural logs. "

>>Again, there is an obvious lack of proof here... I am sorry, I must confess that I started to laugh when I read "to be precise...[...]...this is approximately"... I really don't do maths this way dude )....

.63212 is precise to 5 digits. And 1 -1/e is approximately .63212. And I must confess, I started to laugh at the number of misspelled words in your indignant response.

"Someone on this board gave an answer of 1:1. While not correct, 1 is the AVERAGE number of matches that would occur if you did this for a large number of trials. "

Again, this statement is correct when the proper problem is being addressed.

>>Well, this starts to be pure fantasy ).

You should reconsider what is pure fantasy.

>>"large number" : how large please !!...
More importantly, you compare here carrots and potatoes: Explanation: "odds of 1:1" means that you have one winning outcome to one loosing outcome. Whereas in the following statement, you say that you have in average 1 winning outcome if you perform a large number of trial, which means that you have 1 winning outcome, and " a large number (you called it this way...) minus 1 " loosing outcome...

I really don't see the logic that makes you go from the "1:1 odd" to the "1 winning after a large number of trial"...I really need explanations here...Okay, there is the same digit in both statements, "1", but they have complete different meanings...

It helps to be on the same sheet of music as the rest of us. If you did the original problem a thousand times, you would expect on average, a thousand matches. Therefore, the average number of matches per attempt would be one. I know you don't like to be referred to books, but I recommend you check out p. 68 and 69 of 50 CHALLENGING PROBLEMS IN PROBABILITY by Frederick Mosteller. The paragraph in question is entitled: Solution for average number of matches.

>>"To do this more than once, it is necessary to shuffle only ONE of the decks. Even having the non-shuffled deck in new deck order doesn't change the outcome. "

Okay fair enough, although it is erroneously phrased. IN mathematics and logics, you have what is "necessary" and what is "sufficient". Logically said it should be "it is sufficient to shuffle only ONE of the decks"...It is a necessary condition to shuffle at least one deck, and it a sufficient condition to shuffle only one". Or "it is necessary and sufficient to shuffle at least one deck"

Thanks for clarifying that...I was terribly confused on the issue.

"By the way, this problem is identical to the "hat check" problem that can be found in many recreational math books: If a hat check girl takes in 20 hats, and then mixes the hat check slips and gives the hats back at random, what is the probability that at least one gentleman will get his own hat back? Again, the answer is 63%. "

>>Again, you don't prove any thing, and that is a shame, because you might be right, who knows...

At least one of us knows.

>>Please note that you are talking here about "the probability that AT LEAST one gentleman gets his own hat"... Now you really need to define what you are talking about and what problem you want to solve.

I'm the one who needs to get his problems right?

>> So far we were talking about the "probability of having ONE winning outcome", meaning "exactly ONE".

No we weren't. I'm sorry if the "at least" part of the original post confused you, but it clearly means that we will accept any number of matches other than 0.

>> The "probability of having AT LEAST ONE winning outcome" is completely different (reminder: THAT is equal to the probability of having exactly one + Probability of having 2 winning outcomes + the probability of having 3 winning outcomes +....+ the probability of having 20 winning outcomes". Again, although the conditions are indeed similar, the problem is different, it is NOT what the question was, you mix everything...please read again....

Please read again? I don't have to...I got it the first time through.


>>As for the 63%, you may be right, I don't know,

That much is certain.

>>I haven't try to solve the problem, but the bottom line is that you did not prove your statement.

You got me there. My defense? No one asked me to provide a proof until you came along.

"Another identical problem: Ever take part in a "Secret Santa" ring at the office? Put everyone's name in a hat and then have everyone take turns drawing a name out. You buy a gift for the person whose name you draw. What is the likelihood that someone will draw their own name? You guessed it: approximately 63%. (Assuming there are more than 10 people involved.)

>>again and again and again...no demonstration... and still these same numbers "more than 10 people" (any number greater than 10 ??? Well prove it...)...."approximately 63%"...proof ?

The problems are identical, so I was just giving other examples of how people may have been exposed to the same concepts before. You might have picked up on this had you been with us from the start.

>>Furthermore you use a new term, just to confuse us all even more,

In your case, I don't think this is possible.

by saying "likelihood"... Okay, it is very close to "Probability" but in "standardized Math's terminology", the correct term is "Probability", not "likelihood"

Sorry, I misplaced my copy of that age-old text, "Standardized Math's terminology".

>>So, my guess is that you read all these somewhere

You say this like it's a bad thing. I did read all this somewhere! These are standard probability problems that have appeared over the years in books by Martin Gardner, John Allen Paulos, Marilyn vos Savant, the aforementioned "50 Challenging Problems..." book, and countless others. I never claimed to be able to generate proofs of these concepts at will. However, you will notice I did do one thing: I got the problem correct, and provided the correct answer.

>>No hard feeling buddy, but I am really not convinced by your lecture....

No hard feelings at all. And I'm sure you weren't.

Jason

Well, there you have it. If anyone out there is interested in those books or more problems like this one, I'll be happy to help out in any way I can. Also, if anyone here has by some chance those original MagicTalk posts, I'd love to have copies for my files.

Jason

Actually, I just found my original post that affirmed Bob Farmer's response. You can read it without interruption from James or anyone else.

Jason

Bob is correct, the odds are 5:3 in favor. This answer can be found in Darwin Ortiz's GAMBLING SCAMS along with several other prop bets involving playing cards. What Darwin doesn't reveal is the probability of this occurring. The answer is .63 (remember, odds is a ratio of winning outcomes to losing outcomes or vice versa, probability is usually expressed as a decimal number from 0 to 1).

Interestingly enough, the probability is the same with any number of cards in a deck after about 10. In other words, if you had two groups of cards that each contained the spades from Ace to King, and you tried this little matching experiment, you would find that the probability of a match was still only .63. (.63212 to be precise...an interesting number, this is approximately 1 - 1/ 2.7128. 2.7128 will be recognized by the math geeks on the board as e, the base of natural logs.

Someone on this board gave an answer of 1:1. While not correct, 1 is the AVERAGE number of matches that would occur if you did this for a large number of trials. To do this more than once, it is necessary to shuffle only ONE of the decks. Even having the non-shuffled deck in new deck order doesn't change the outcome.

By the way, this problem is identical to the "hat check" problem that can be found in many recreational math books: If a hat check girl takes in 20 hats, and then mixes the hat check slips and gives the hats back at random, what is the probability that at least one gentleman will get his own hat back? Again, the answer is 63%.

Ever take part in a "Secret Santa" ring at the office? Put everyone's name in a hat and then have everyone take turns drawing a name out. You buy a gift for the person whose name you draw. What is the likelihood that someone will draw their own name? You guessed it: approximately 63%. (Assuming there are more than 10 people involved.)

Jason

Another version of this problem is the envelope and letter problem. You have ten letters and ten addressed envelopes. You put the letters into the ten envelopes at random. What is the probability that a least one letter makes it into the correct envelope? And of course once again the answer is the same.

Jack Shalom



Actually, maybe this question isn't that hard. I'm going to jump and make the assumption that the match can occur at any position with equal likelihood. So then the average place that would occur is at the 26th-27th place. Or does the fact that more than one match can occur mess this up?

Jack

Jack, the probability for the _first_ match found to be near the end of the deck is pretty slim, I think. I'll do as usual and make a simulation of it and then try to find a proof of it.

/Tomas

For the original problem, where cards are dealt simultaneously, the first match comes at card 22 on an average. (Only counting the cases where there was at least one match.)

/Tomas

Thanks Tomas!

Jack

Jack, I now realize that there are several ways to interpret when the first match occurs. Do we want the average only among the cases where there is at least one match in the deck? If not, do we count the cases where there are no matches as a match at 0, a match at 53, or a match at infinity?

/Tomas

Maybe the way to handle "no match" is to say that we start the deck again until there is a match. Thus if there is no match and you start the deck again and a match then occurs at position 20, then that should be recorded as one deal with a match at position 72.

Does this make sense to you? I think it keeps to the spirit of what we're trying to figure out.

Jack Shalom

Thanks for asking for clarification.

What I had in mind was simultaneous turnovers from both decks until a match. Looking for a rough gauge to how many turnovers are needed to hit the first match.

For some reason this situation strikes me as suspensful from an audience perspective.

Yes, that makes sense since "a performance" is "until you get a match". The rather strange result I got from this was that the match occurrs at card 52.4 on an average. The match is at 30.5 for the alternate dealing procedure.

Reservations for that my simulations might be totally wrong.

/Tomas

The odds of not getting ANY matches works out to .3643135196, or about 36.43%. The odds of getting a match, then are 1 minus this number, or .6356864804 (roughly 63.56%).

Interestingly, the odds of no matches approximates the reciprocal of e (1/2.7182818285 = .3678794412), and naturally, the odds of getting any match approximate 1-(1/e) . . . (.6321205588).

/*math geek mode off

Some have suggested that the (51/52) to the 52nd power method is the wrong way to calculate it, because the deck "diminishes" each time a card is dealt.

This method is actually correct. I'll explain why.

I think we can all agree that the odds of the first card matching are 1/52, and the odds of not matching is 51/52.

But wouldn't be the odds of the second card matching thus be 1/51 (and the odds of not matching be 50/51), because we've already dealt one card? No.

All we're looking for is a match. When you turn up a card from Deck A, this is the card whose duplicate you're looking for at the moment. There are only two possibilities for the top card of Deck B - either it is a match, or it's not. If it doesn't match, it doesn't matter where else in the deck the match for Deck A is.

Sure, if you turned up, say, a 3H on Deck A, and you've already seen a 3H dealt from Deck B, you can say with certainty that this particular time will not be a match, but that doesn't affect the odds for being at least one match at SOME position in the deck.

If you were to just turn up one card from Deck A, and then go through Deck B one card at a time, the odds for the first pair matching would be 1/52. The odds of the next card matching the single card from Deck A would be 1/51. Obviously (assuming both cards are full decks), you would eventually get to the duplicate in Deck B, even if it was the last card. So, the odds of eventually getting a match for the top card of Deck A would be 100%, and the odds of no match would be 0%. Think about the math of no matches in this situation: (51/52)*(50/51)* . . . (2/3)*(1/2)*(0/1). Since the last factor is 0 in that problem, that makes the whole chance of no matches is 0.

In short, the cards that have already been dealt don't affect the probability in any way. Therefore, the method of calculating the probability by using (51/52) to the 52nd power is correct.

If this, for some reason, still doesn't sound right, try writing a program to simulate the problem. The more times you simulate the problem, the more you'll see the odds of a match approximate 63.56864804% (roughly 5 out of every 8 times).

Here's a page with effectively the same problem:

26. Players A and B each have a well-shuffled pack of cards. The players deal their cards one at a time, from the top of the deck, checking for an exact match. Player A wins if, once the packs are fully dealt, no matches are found. Player B wins if at least one match occurs. What is the probability that player A wins?

Asked this way, it's no different than asking what is the probability of no matches.

Here's the answer: Solution 26

As stated before, the probability of no matches with 10 cards or more quickly converges to 1/e, making the probability of a match 1-(1/e). Interestingly, this page demonstrates that the true odds of n amount of cards not matching are always within 1/n! (one divided by n factorial) of 1/e.

It's been well established that the approximate 63% answer is correct, so why is the method of calculation wrong, yet still gives the correct answer?

Scott,

I'm no math expert and I will certainly defer to those with more math knowledge than myself, but I don't understand how your argument refutes my counter argument of a two card deck posted above. If (51/52) ^52nd power was correct, then, by that argument, for a two card deck the answer should be (1/2) ^ 2nd, and clearly it isn't.

You ended your last post saying: "It's been well established that the approximate 63% answer is correct, so why is the method of calculation wrong, yet still gives the correct answer?"

We both agree that 63% is the correct answer; but just because (51/52) ^ 52nd comes close to that answer it doesn't necessarily mean that that is the correct way of thinking about the problem. It's logically possible to have two algorithms that come up with similar answers in one situation, but different answers in other situations. So I don't really find that particular argument very convincing. (2+2 =4, 2*2 = 4, does not necessarily imply that addition and multiplication are the same process).

But I'm quite willing to admit I'm wrong. Maybe I'm just not smart enough to follow your argument. Could you explain it a little further? Or if this is too boring for others and not magical enough, maybe you could PM me.

Thanks,
Jack Shalom