|
#1
|
|||
|
|||
Another Boredom Filler
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.
|
#2
|
|||
|
|||
Re: Another Boredom Filler
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. |
#3
|
|||
|
|||
Re: Another Boredom Filler
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) |
#4
|
|||
|
|||
Re: Another Boredom Filler
[ 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. |
#5
|
|||
|
|||
Re: Another Boredom Filler
[ 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. |
#6
|
|||
|
|||
Re: Another Boredom Filler
[ 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! |
#7
|
|||
|
|||
Re: Another Boredom Filler
Could you sketch out how the I/E method would be applied to this problem?
|
#8
|
|||
|
|||
Re: Another Boredom Filler
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. |
#9
|
|||
|
|||
Re: Another Boredom Filler
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. |
#10
|
|||
|
|||
Re: Another Boredom Filler
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)... |
|
|