PDA

View Full Version : a problem

08-17-2002, 05:26 AM
One day, a friend approaches you with 2 decks of standard 52 cards. He tells you, "I want to make you a bet. I'm going to shuffle both deck of cards thoroughly. Then, I'm going to turn over the cards from the decks simultaneously, one by one. In other words, I'll turn over the first cards of each deck simultaneously. Then, I'll turn over the next cards simultaneously. I'll continue doing this, until I've finished turning over all the cards in the decks."

"Now, my offer is this. I'll give you 3:2 odds that at no time while I'm revealing the cards, will 2 of the EXACT same card fall down simultaneously. In other words, you give me \$2. If I get through the whole deck without any two cards falling identically, then I'll pay you \$3. But, if 2 cards fall at the same time, and they're identical, I win and keep your money."

Should you accept this bet?

08-17-2002, 07:21 AM
Well, if I've absorbed the lesson of the inclusion-exclusion principle, the probability of a match is:

52*51!/52! - C(52,2)*50!/52! + C(52,3)*49!/52! - C(52,4)*48!/52! +...

= 63%.

So yes you should take 3-2 odds since you are better than a 2-1 favorite. I like this principle.

08-17-2002, 07:24 AM
Except 63% isn't better than a 2-1 favorite...

08-17-2002, 07:42 AM
Ok, let's get the easy part of this problem right. You LOSE 63% of the time when there is a match, so you are more than a 3-2 dog, so you should NOT take the bet.

08-17-2002, 07:43 AM
I approached this problem two ways:

The simple way, giving each trial a 51/52 chance of failure with 52 trials giving (51/52)^52 =36.43% which means I'm under the 40% chance required to take your bet.

I then needed to confirm to myself that each trial was independent becuase it felt wrong, so i assumed the first deck came through in order As.2s.3s etc

Obviously the chances of first card matching is 1/52.

The 2s will have a 1/51 chance of SUCCESS every time it wasn't the first card which is 51/52 of the time so we get 1.51/51.52 or 1/52.

The 3s will have a 1/50 chance of SUCCESS every time it's not one of the first two cards (50/52) so again we get 1.50/50/52 or 1/52.

So these trials can be treated as independent i believe.

My maths is rusty so please check this for yourselves and flame me if approppriate.

Lori

08-17-2002, 07:44 AM

08-17-2002, 12:53 PM
I read in "Gambling Scams" that for such a wager, the odds are in favor of the two cards being in identical locations is better than 5:3, or 10:6. Since you are being paid 3:2, or 9:6, you should not accept the bet (my math is completely off base, huh?).

08-17-2002, 03:49 PM
No, you're absolutely correct. You should not accept the bet. The reason is inclusion-exclusion. What we're really doing is looking at the second deck as a permutation (shuffling) of the first, and asking if there are any fixed points. Let N(i) be the number of shufflings in which the i'th cards are identical. We want to know how many shufflings there are where this never happens for any i.

Suppose our deck has n cards, so here n = 52. Let N(i,j,k) be the number of shufflings where the i'th, j'th, and k'th cards are identical, and so on.

N(i) = (n-1)!, because there are (n-1)! ways to permute the remaining cards.

N(i,j) = (n-2)!, because there are (n-2)! ways to permute the remaining cards.

And so on.

Also, when we apply inclusion-exclusion, there are C(n,1) terms of type N(i), C(n,2) terms of type N(i,j), etc. In general, there are C(n,k) terms corresponding to shufflings which have k identical cards.

Thus, the number of ways that none of the cards can fall identically is

n! - (n-1)!*C(n,1) + (n-2)!*C(n,2) - (n-3)!*C(n,3) + ... + (-1)^n,

the final term corresponding to k = n.

Now, if we divide this by n!, we get that

1 - 1/(1!) + 1/(2!) - 1/(3!) + 1/(4!) - ... + (-1)^n/(n!)

is the probability that none of the cards will fall identically.

This is the series expansion of e^x, where x = -1. So, the above expansion is just a partial sum approximation for 1/e. This means the probability that at least one of the cards WILL fall identically is (e-1)/e, and so the odds for the bet should be set at (e-1):1, which is about 1.718:1. This is why both 3:2 and 5:3 are losing bets.

08-17-2002, 05:23 PM
If I start with \$2 then I should finish with \$5 if I win my bet and \$0 if I lose.

08-17-2002, 09:21 PM
[(n-1)/n]^n also equals 1/e for large n, so in this problem the cards are independent, and we can just do (51/52)^52 = 36.4% without the inclusion-exclusion principle.

If you do something n times where the probability of success each time is 1/n, and the tries are independent, then the probability of at least one success is approximately 1-1/e = 63%, the approximation becoming better as n becomes sufficiently large.

08-17-2002, 10:15 PM
"If I start with \$2 then I should finish with \$5 if I win my bet and \$0 if I lose. "

You do. The original message said you would get paid \$3. Therefore, you are paid \$3 for your \$2 and walk away with \$5.

08-18-2002, 03:36 PM
Maybe I'm misunderstanding the odds notation...I've never encountered it before until reading about poker. (I'm only used to percentages.) In this case, it should be 1:2 (or .5:1) instead of 3:2, and 2:3 (or (2/3):1) instead of 5:3. Sorry for the confusion.

08-18-2002, 04:25 PM
Except the trials AREN'T independent, in this case. Say you have a full deck, in order, As Ks Qs Js... to start with. You don't want any identical cards. The probability the first isn't is 51/52, true. But the probability the next one is identical is dependent on the first.

Let A = event the first card is not identical, and B = event the second card is not identical. The definition of "independent" means that

P(A intersect B) = P(A)*P(B),

(e.g. choosing suit vs. rank in a deck are independent because P(Qs) = P(Q)*P(s)).

Here, P(A) = P(B) = 51/52.

But what is P(A intersect B)? Well, how many permutations are there where the first two aren't identical? There are a number of cases. The first two cards could be completely different from the As and Ks. There are P(50,2) ways to get these cards, then. After that, there are 50 cards left, and they can be permutated in any way, so that's 50!, altogether, in this case, there are 50*49*50! ways. What if exactly one of those two cards falls among the first two? It's place is completely determined, because it can't fall on its own place, so here there are 2*50*50! ways (the 2 comes from the choice of 2 cards As and Ks, the 50 from choosing the other of the first 2 cards, and then 50! for the rest). And finally, they both could appear, but in reverse order. Here, there's 50! ways this could happen. Altogether, there are (50*49 + 2*50 + 1)*50! = 2551*50! ways. Dividing by 52!, we get the probability to be 2551/(52*51), about .9619155

The probability you get from multiplying P(A) by P(B), however, is (51/52)^2, which is 2601/(52*52), about .9619082, not the same.

Another way to see why simply assuming they're independent is wrong, is to imagine a deck with, say, 3 cards. If you assume independence, you get the probability of no identical card falling to be (2/3)^3 = 8/27. Using inclusion-exclusion (which IS known to give the correct answer), you get 1 - 1 + 1/2 - 1/6 = 1/3, which is not the same as 8/27. Or, better yet, use a deck with TWO cards...inclusion-exclusion gives you the (obviously correct, even without inclusion-exclusion) answer 1 - 1 + 1/2 = 1/2, whereas assuming independence gives you (1/2)^2 = 1/4.

This is an example of getting the right answer, but for the wrong reasons. It's true, that in the LIMIT, as n goes to infinity, the probability of a derangement on n elements (a permutation without fixed points) approaches the probability of taking n independent selections, with replacement, from a jar with n objects, and never selecting a specific fixed object. That doesn't mean the probabilities for FINITE n are identical.

08-18-2002, 06:05 PM
I agree that the trials aren't independent in the strict sense. That's obvious when you consider that if all the cards up to the last one match, then a match on the last one is guaranteed.

The bigger question, IMO, is whether the trials can be treated as independent for the purpose of calculation. We have shown that the probability of no match is equal to the product of the individual probabilities of no match per card (51/52)^52 to within our desired accuracy of calculation. Therefore, for all practical purposes, the trials may be regarded as indpendent. This will be the case for a reasonbly large number of trials, in this case 52. You have shown yourself that even with as few as 3 trials, the approximation is quite close (8/27 vs 1/3). The inclusion-exclusion principle will generally also give an approximation since we will not generally bother to calculate all the terms for large n, and a calculation based on an assumption of independence may actually be just as accurate as well as much simpler to compute. So I disagree that it is "getting the right answer for the wrong reasons". It is getting the right answer for the right reason, namely the correct realization that the trials may be treated as independent.

In the other problem where we wanted the probability of a player holding a pair of jacks or better, the assumption of independence still held to a high degree of accuracy, though I would not necessarily have assumed that. Yet now that I know this result, I will continue to use it to simplify calculations where appropriate.

08-18-2002, 06:10 PM
You had it right, you just have to make it clear that when I win you give me back my original \$2 in addition to the \$3 that I win. That is giving me 3:2 odds. I'm betting \$2 in order to have a net win of \$3.

08-18-2002, 06:48 PM
Well, okay...you didn't say you were TREATING them as independent, you said they WERE independent. There's a big difference. When you say "the limit is 1/e, therefore the trials are independent", that's just false. If you mean to say, "for large n, the trials can be considered as independent", and then give a heuristic or intuitive justification for that, is one thing. But I interpreted what you said to mean that independent trials could be used to find the EXACT number of derangements, and that's not true. I'm sorry, if it seems like I'm incredibly pedantic and take things literally, but that's just my training. Anything mathematical, I interpret literally, unless I'm told otherwise.

08-18-2002, 11:17 PM
I think i showed that the trials were okay to be considered at 1/52 each time in a very simple way

08-19-2002, 08:50 AM
I said they were independent "in this problem" meaning that for the purpose of deciding whether or not to accept 3:2 odds, they could be regarded as behaving independently. Since the series solution represents 1/e in the limit, and since the first few terms of this series are sufficient to compute our probability, then surely [(n-1)/n)]^n which also approaches 1/e very rapidly will also yield the same probability to our required degree of accuracy, hence the trials behave as though they are independent for our purpose. That is all I was noting.

If P(AB)-P(A)P(B) = 0, A and B are independent. If P(AB)-P(A)P(B) = .0000001, to a mathematician they are not independent. However, to a physicist or engineer, they are still highly independent depending on what one is attempting to measure. Having been trained in all three disciplines, I use whatever interpretation gives me the results I'm after.