Another Boredom Filler

[LetYouDown]

Well shuffled deck of cards. You deal the cards face up, one at a time. Every time you flip a card, you add one to the count, then repeat when you get to 13. So you count 1-13 four times. What are the odds that you will make it through the deck without ever saying a number that matches the rank of the card. Call Aces 1 and Kings 13 to make it easier to think about.

I can't believe you posted this problem. It has become a bit of an obsession of mine in that I don't know how to solve it analytically and neither does anyone else I know. I've asked some math professors, the wizard of odds (which by the way isn't too good at difficult problems despite having an otherwise nice gambling odds website) and my brother who has gotten an 800 on every SAT/GRE/LOGIC/SAT Subject Tests related to math/physics he ever took.

Anyway, you can write a Monte Carlo program to solve the problem and I am 100% positive the odds of making it through the deck without ever saying the same card that you flip over is 1:61

I have a spreadsheet of the odds of making it through X cards. So if you are interested in seeing the probability at different points in the deck I can send it to you.

[elitegimp]

I don't know if you can actually claim independence, but for any specific point in your count, there are 48 cards that don't match and 52 that do... so there's a 12/13 chance you don't match a specific time. To not match 52 times would therefore just be (12/13)^52, or 0.01557 (1.557% chance you make it through the deck). That works out to approximately 1 in 64.214, or 63.214:1.

The other thing I was gonna do was to just count the possible deck combinations, but that seems like a lot more work.

edit: what I want to know is what the expected number of cards you get through before the card = count... I've tried 5 times (sample size warning!!!) and didn't get past the 22 card any of those times.

edit 2: If my probability calculation is right, then
P(count = card i | no match in first i-1 cards) = (12/13)^(i-1) * (1/13) => P(get through the deck) = 1 - Sum (from i = 1 to 52) (12/13)^(i-1)*1/13 = 0.01557 as above

So EV = Sum (from i=1 to infinity... assuming an infinite deck so that eventually count = card) i*(12/13)^(i-1)*(1/13) = 12

So in the long run, you should average going through 12 cards per time (if I'm right, which is a big assumption)

[LetYouDown]

[ QUOTE ]
To not match 52 times would therefore just be (12/13)^52, or 0.01557 (1.557% chance you make it through the deck). That works out to approximately 1 in 64.214, or 63.214:1.

[/ QUOTE ]
This is only an approximation. I believe you'll need the inclusion/exclusion method to get an exact count...and I'm not sure that's all that's involved, or that it's even remotely as simple as that.

[ QUOTE ]
[ QUOTE ]
To not match 52 times would therefore just be (12/13)^52, or 0.01557 (1.557% chance you make it through the deck). That works out to approximately 1 in 64.214, or 63.214:1.

[/ QUOTE ]
This is only an approximation. I believe you'll need the inclusion/exclusion method to get an exact count...and I'm not sure that's all that's involved, or that it's even remotely as simple as that.

[/ QUOTE ]

Yes, that person was incorrect on nearly all of their statements including parts you didn't quote.

LetYouDown, did you just come up with that problem or did you see it somewhere? Also, what do you do for a living (if that's not too personal)? I've noticed that you seem to answer many of the people's questions.

By the way, I'm still interested in the analytical solution. If anyone could show it to me I would be impressed.

[hukilai]

inclusion/excursion is universal method and will work for this case as well, but it will be incredibly tedious.

To see it, you can try to do it for 13 cards (you also can find it books)...

[donkeyradish]

Shuffle 2 decks of cards

Then simultaneously deal from the top 1 card per deck at a time.

What is the probability that you will get through the whole deck without ever dealing the same 2 cards simultaneously?

Then for an encore what is the probability for n Decks
(1 < n < 52)

[LetYouDown]

[ QUOTE ]
LetYouDown, did you just come up with that problem or did you see it somewhere? Also, what do you do for a living (if that's not too personal)? I've noticed that you seem to answer many of the people's questions.

[/ QUOTE ]
Computer Programmer/Software Engineer. Problems like this have always interested me, although I rarely need to use combinatorics for the "real world" applications I work on.

You can monte carlo this problem to get a pretty accurate answer, but I'd really really like to see a closed form solution. Inclusion/Exclusion would be ridiculously tedious, I concur...but I'm curious if that's really the only way to solve this. Granted, you could always write out all 8.0658175170943878571660636856404e+67 possible decks, and solve manually!

[bobman0330]

Could you sketch out how the I/E method would be applied to this problem?

[LetYouDown]

Well, essentially you could turn it into an enormous tree diagram. The first card matching is obvious. On the second card you have a couple possibilities. If the first card was a 2, then you have 3/51. If it wasn't a 2, then you have 4/51. This problem is much more complex than I had originally thought. Although I'll admit, I didn't really think about it prior to posting it. It's been a while since I've messed with Mathematica, but I'd imagine it would be really useful here.

Since people seem to be somewhat interested, these are the results of making it through any number of cards without a match.

Card 1 in X
52 61.5612
51 56.9152
50 52.5458
49 48.5413
48 44.8914
47 41.5559
46 38.348
45 35.4083
44 32.6861
43 30.1386
42 27.8102
41 25.6838
40 23.7293
39 21.9168
38 20.2873
37 18.7315
36 17.3382
35 16.0514
34 14.839
33 13.7105
32 12.6682
31 11.7049
30 10.8071
29 9.9822
28 9.2113
27 8.5042
26 7.8502
25 7.2597
24 6.7077
23 6.2028
22 5.7351
21 5.3004
20 4.8953
19 4.5186
18 4.1738
17 3.8565
16 3.5594
15 3.2864
14 3.0338
13 2.7993
12 2.5886
11 2.3924
10 2.2122
9 2.0442
8 1.8893
7 1.7457
6 1.6136
5 1.4908
4 1.3765
3 1.2717
2 1.1741
1 1.0833
0 1

It gets bunched up when I post it, but you get the idea.

[LetYouDown]

The thought I've been having lately is that if you were to translate the question into counting from 1-52 and matching the exact card instead of rank only, the problem simply becomes a Fixed Point calculation based on the permutations...and should tend to 1/e for no fixed points, I believe. Although, even that isn't a closed form solution. From what I've been able to read about this, as the sample size goes up, the probability of no matches tends toward 1/e^4.

[BruceZ]

[ QUOTE ]
Shuffle 2 decks of cards

Then simultaneously deal from the top 1 card per deck at a time.

What is the probability that you will get through the whole deck without ever dealing the same 2 cards simultaneously?

[/ QUOTE ]

This is much easier than the original problem. Answer in white:

<font color="white">From inclusion-exclusion (http://archiveserver.twoplustwo.com/showthreaded.php?Cat=&amp;Board=&amp;Number=417383&amp;page=&amp;v iew=&amp;sb=5&amp;o=&amp;fpart=):

P(no matches) = 1 - P(1 or more match) =

1 - [52*51! - C(52,2)*50! + C(52,3)*49! - ... - C(52,52)*0!] / 52!

= 1 - (1 - 1/2! + 1/3! - ... - 1/52!)

= 1 - 1 + 1/2! - 1/3! + ... + 1/52!

Note that this is approximately the Tayor series for e^-1 =~36.8%.


[ QUOTE ]
Then for an encore what is the probability for n Decks
(1 &lt; n &lt; 52)

[/ QUOTE ]

Answer in white:
<font color="white">
EDIT: This solution is approximate because when there are k matches, some of these can be the same card, so there will not always be n^k ways to match k cards. The approximation should be good since the cases where the same card is matched more than once should make a small contribution.

P(no matches) = 1 - P(1 or more match) =

1 - [n*52n*(52n-1)! - n^2*C(52n,2)*(52n-2)! + n^3*C(52n,3)*(52n-3)! - ... - n^(52n)*C(52n,52n)*0!] / (52n)!

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

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

This is approximately the Tayor series for e^-n.</font>

[BruceZ]

[ QUOTE ]
Could you sketch out how the I/E method would be applied to this problem?

[/ QUOTE ]

See my solution in this thread for similar problems. It is not e^-4 for this problem since there are not always 4^n ways to match n cards, since some of the C(52,n) would choose the same rank. This is what makes inclusion-exclusion tedious for this problem, but not for the problem where we match the exact card with 1 deck. Note that on average there will be 52*1/13 = 4 matches, so we would need more than 4 terms. The other error due to the truncation of the Taylor series is insignificant.

[DougOzzzz]

I don't have a good method to solve this problem. However I am wondering the following:

Why is it that the approximate answer (12/13^52 = about 1 in 64.2) yields a probability significantly lower than the "actual" answer of about 1 in 61.5?

My first thought of approaching this problem was doing the "tree" analysis suggested by LetYouDown. It gets way too complicated, but take the first 2 cards. THere are 3 scenarios:

1. First card is an ace, a match, game over, you lose. Probability 1/13.
2. First card is a 2. Probability 1/13. Probability of a match next card is now 1/17. Probability of a 2 the first card, and no match the 2nd card is 1/13*16/17 = 16/221.
3. First card is a 3-K. Probability 11/13. probability of a match next card is now 4/51. Probability of a 3-K 1st card and no match the 2nd card is 11/13*47/51 = 517/663.

Total probability of no match the 1st 2 cards is 16/221 + 517/663 = 565/663 = 0.852187029

12/13 ^ 2 = 0.852071006.

Thus, for 2 cards at least, the probability of no matches is HIGHER with the approximate method compared to the actual answer. It's not clear to me why this changes when you continue to go through more cards.

Edit: I am stupid, and can't count.

[BruceZ]

Donkeyradish's second problem has the same issue as the original, in that when we choose C(52n,k) matches, some of these can be the same card, so there won't always be n^k ways to match the k cards. In fact, the original problem can be viewed as a special case of this problem with 4 decks of 13 cards each.

The approximation should be better in this case because for a low number of matches (low order terms), the cases where we match the same card make a small contribution. The cases where it is likely that we match the same card are represented by the high order terms, and these make a small contribution because these terms are small, the series having already converged for all practical purposes.

[DougOzzzz]

I am assuming by the title of this post that you assumed I could compare 2 numbers and determine which one was greater than the other. Since that assumption was false, your reply makes no sense to me, my post had no purpose, I am stupid, or perhaps my assumption of your assumption was incorrect. Or something.

[BruceZ]

[ QUOTE ]
I am assuming by the title of this post that you assumed I could compare 2 numbers and determine which one was greater than the other. Since that assumption was false, your reply makes no sense to me, my post had no purpose, I am stupid, or perhaps my assumption of your assumption was incorrect. Or something.

[/ QUOTE ]

I don't understand what you're saying. I responded to my own post and pointed out that my solution to the second problem that donkeyradish asked was an approximation, though it should be a good one. What 2 numbers are you talking about?

[DougOzzzz]

nevermind, I saw the reply and for some reason I thought it was to my post, which is why it confused me.

[LetYouDown]

Bruce, do you think that the only real method for getting an exact answer here would be to go through the inclusion/exclusion principle for all of the terms? I realize that as it deviates from the expected number of matches, the fluctuation will be negligible at some point. However, my thoughts at this point lean toward there not being a more elegant, exact solution as opposed to an approximation.

[pzhon]

[ QUOTE ]

What is the probability that you will get through the whole deck without ever dealing the same 2 cards simultaneously?

Then for an encore what is the probability for n Decks
(1 &lt; n &lt; 52)

[/ QUOTE ]
I'm not sure what your encore question means. Do you want the probability that on all 52 cards, every deck has a different card, or do you want the probability that not all decks coincide?

If the former, it is the number of 52xn Latin rectangles (http://mathworld.wolfram.com/LatinRectangle.html).

[BruceZ]

[ QUOTE ]
[ QUOTE ]

What is the probability that you will get through the whole deck without ever dealing the same 2 cards simultaneously?

Then for an encore what is the probability for n Decks
(1 &lt; n &lt; 52)

[/ QUOTE ]
I'm not sure what your encore question means. Do you want the probability that on all 52 cards, every deck has a different card, or do you want the probability that not all decks coincide?

If the former, it is the number of 52xn Latin rectangles (http://mathworld.wolfram.com/LatinRectangle.html).

[/ QUOTE ]

I assumed that we have 2 stacks with n decks in each stack, and that we want to go through all the cards, dealing a card from each stack, without ever dealing a pair of the same card.

[LetYouDown]

For the initial problem...here's an approach to the entire rank-derangement problem. I haven't thoroughly looked at it yet, but it seemed sound. Font is a bit ugly and hard to read, however.

http://math.dartmouth.edu/~doyle/docs/rank/rank/rank.html

Great link LetYouDown. I enjoyed reading the historical background. I guess I'm not the only one who likes this problem. Funny thing too is that I've considered pitching this game to a casino. I've come up with several ideas for it's presentation.

Anyway, Marilyn is a smart woman and I concur that the expected number of matches in 52 is 4. That was another thing I did with the program along with the earlier post I had with probability of no matches for each card. It goes like this

Matches %
0 = 1.6%
1 = 6.89%
2= 14.44%
3 = 19.8%
4 = 20.1%
5 = 16.1%
6 = 10.5%
7 = 5.8%
8 = 2.7%
9 = 1.1%
10 = 0.4%
11 = .14%
12 = .04%

[BruceZ]

[ QUOTE ]
Anyway, Marilyn is a smart woman and I concur that the expected number of matches in 52 is 4.

[/ QUOTE ]

That's obvious since the probability of a match on each card is 1/13, the average number of matches is 52*1/13 = 4.

[ QUOTE ]
I assumed that we have 2 stacks with n decks in each stack, and that we want to go through all the cards, dealing a card from each stack, without ever dealing a pair of the same card.

[/ QUOTE ]As the decks get large, doesn't this approach 1-1/e? (Assuming that "same card" means same rank and suit.)