Board 8 > Probability question

(+) Yeah! (+)

If a game of Go Fish is being played with a group of 12 people with a deck of 48 cards (24 pairs), and each person holds four cards at a time...what are the odds that someone starts out with a pair?

More specifically, what are each persons odds of starting off with a pair, and what are the groups overall odds that at least one person starts with a pair.

For one person: 100%

I always carry a pair of aces up my sleeves.

---

Lol

Since you're saying there are 24 pairs I'm assuming they're all unique pairs (i.e. not a standard deck of cards with say, Aces removed, where you still have 4 Kings, Queens, Jacks, etc.)

A specific person's odds of starting with a pair: 1 - (46/47 * 44/46 * 42/45) = 89/705 or approximately 12.62%

At least one person starts with a pair... I'm not sure I'm alert enough to figure that out. Part of me wants to say you take (1 - 89/705)^12 but I'm not 100% sure that's right. If it is, that gives you an approximately 80.2% chance at least one person starts with a pair.

---

The probability a single person does not have a pair is (24C4*2^4)/48C4 = 10626*16/194580 = 87.38%.

That agrees with xp's rendition.

As for the "at least one person" version, it's slightly more complicated than the way xp put it because as you take cards from the deck without replacement, it narrows the options a bit for the others, but I would presume that his calculation is accurate enough for most purposes.

---

azuarc posted...

As for the "at least one person" version, it's slightly more complicated than the way xp put it because as you take cards from the deck without replacement, it narrows the options a bit for the others, but I would presume that his calculation is accurate enough for most purposes.

Yeah, that's what I was hanging up on but like I said I'm not currently awake/alert enough to think of a quick/easy way to account for the various permutations/possibilities to account for that... if there even is one. I presume there is but I need sleep. >_>

So I just gave up and hoped that that would be a "close enough" answer with no evidence whatsoever to support it. <_<

---

I'd think the odds would be a smidge lower for "at least one person" since if I have four cards that don't match, that means there are four cards elsewhere that are automatically not gonna match, whereas if I had two pairs it wouldn't change anybody else's odds.

---

Very interesting. So basically, over 50% that someone will start off with a pair.

Tom Bombadil posted...

I'd think the odds would be a smidge lower for "at least one person" since if I have four cards that don't match, that means there are four cards elsewhere that are automatically not gonna match, whereas if I had two pairs it wouldn't change anybody else's odds.

I actually wrote out a big response to my own post, explaining how I concluded I was wrong and it needs to be XXX and YYY and all these conditional scenarios.

But, ultimately, no.

View it from each player's perspective individually. Unless you have information that the people dealt ahead of you have or do not have pairs, it doesn't actually matter what they have. You may as well have been the first person dealt. And the first person's likelihood is 12.62%.

It's true that if you analyze it sequentially, the likelihood slides up and down based on what happened before, but there are enough eventualities in both directions that it equalizes.

For an ultra-simplistic analogy, imagine there are 5 people choosing straws. The first person has a 1/5 chance of drawing the short straw. The second person has a 1/4 chance, but that's in the 4/5 of the time that the short straw is still there, so we multiply and get 1/5. The third person has a 1/3 chance, under the 3/5 of the time the short straw is still there. Still 1/5.

Contrast that with the Monty Hall problem where your option to change selections is based on having more information than you had previously. From the players' perspective, nothing has changed the status quo from their initial deal.

Therefore, I'm going to conclude that xp's reasoning is correct.

---

Shit's exchangeable yo

---

azuarc posted...

Therefore, I'm going to conclude that xp's reasoning is correct.

xp's reasoning cannot be correct because it can be easily proven faulty in the 2-person case. Pairs AABBCCDD.
Probability of player 1 not holding a pair: 8/8 * 6/7 * 4/6 * 2/5 = 22.9%

If player 1 doesn't have a pair, then player 2 must also not have a pair. The probability is not 22.9%^2 that neither player has a pair. There are only two scenarios here, both players have at least one pair (77.1%), or both players don't have a pair (22.9%).

---

excuse me my reasoning was explicitly "i don't even know if this is correct" I just didn't want to totally punt on the question and gave the one concrete idea that came to mind with a warning that I wasn't sure about it!

=(

---

Sorry, didn't mean to come across as accusatory toward anyone. Just wanted to point out that azuarc's conclusion about your estimation doesn't necessarily hold true.

---

Well, if one person draws two cards from a deck of two pairs, the chance that they don't get a pair is 4/6. If you add a second person, the chance is still 4/6 for neither of them to get one because the first person already broke up the only two pairs.

edit: basically what tom and tyder said

---

Number of ways to draw 4 cards without getting a pair: (24*2)*(23*2)*(22*2)*(21*2)=4080384

Number of ways to draw 4 cards without any restrictions: 48*47*46*45=4669920

Therefore the odds that any particular person draws a hand without a pair is (4080384/4669920) or about 87.4%. (equivalent to xp's answer)

Note that player A obtaining a pair and player B obtaining a pair are not independent events since they're drawing uniquely from the same pool of cards, so you can't straightforwardly do (0.874)^12 to exactly get the probability of no player obtaining a pair. (tyder's reduced example is a clear demonstration of this.) Calculating this exactly would require more advanced combinatorics that I'm not capable of sorting through on the fly. If you want to use xp's method as an estimate, I don't have a great feel for how accurate it would be. My intuition says it would be a good estimate for the case of large numbers of players, but I don't know exactly how many you would need to meet that criteria, and I'm not 100% sure my intuition is correct here anyways.
---

another way to estimate this probability is to deal out a pair randomly to the 48 slots. doing that, there's a 3/47 chance they go to the same person. if you just did that 24 times in a row without considering where the previous cards went, there's a 1-(44/47)^24 = 79.46% chance someone gets a pair. but that obviously isn't going to be completely accurate either. just the second pair dealt out is already going to be less likely to be given to the same person than the first. and say you're halfway done and everyone has 2 cards. now you're even less likely to deal out a pair.

if you're combing through all possibilities, you will come across situations where the next pair to be dealt out is more likely than the initial 3/47. but that involves stacking a few players with most of the cards while the rest have very few. those situations are less common to begin with, and become even more rare with the restriction that they can't have a pair. therefore, i'd say the actual probability is signifcantly less than that 79.46% estimate. basically, every pair that pops up increases the pair of another appearing, and it's that co-dependancy that lowers the chances of "at least one" pair.

---

I ran a simulation of 100,000 trials because I'm over trying to actually figure the exact answer. This is not an easy problem.

Probability of at least 1 player getting a pair in a game of 12 players is approximately 79.0% by simulation.

---

All I can think reading this topic:

https://xkcd.com/356/

---

That's similar to another estimation method I came up with while in the shower.

Imagine dealing out both cards of a pair randomly to any of the 12 people. The # of ways to deal the pair to different people is 11*12, whereas the number of ways to deal out the pair at all is 12*12, so the odds of any particular pair being dealt to 2 different players is 11/12. Then just do this for all pairs by taking (11/12)^24, which is about a 12.4% chance of no player obtaining a pair.

As calculated, this is not an exact solution because it neglects the constraint that each player must be given 4 cards. (If you really do this randomly, sometimes you reach valid arrangements, but sometimes you get arrangements where player A has 5 cards, player B has 3 cards, etc.) However this would be close if the relative frequency of pairless arrangements and pair arrangements for the subset of evenly distributed cases is similar to the same frequency for the distribution as a whole, which I would intuitively guess to be true for numbers large enough where the probability distribution is dominated by cases close to uniform distribution of cards.

On that line of thought, I think this estimation method represents a lower bound on the true value since the odds of obtaining a pair should increase if you consider cases where cards begin to cluster in the hands of one player*, so this analysis should be introducing cases where you are more likely to obtain pairs than you would have been in just the 4-cards-to-each-player cases. However I don't quickly have a way to provide a fully rigorous proof of that statement.

*In the extreme limit of the subset where 25 or more cards go to 1 player there is a 100% chance of a player having a pair, and it's intuitively obvious that the odds are quite high in the cases where one player gets, say, 12-16 cards.
---

tyder21 posted...

I ran a simulation of 100,000 trials because I'm over trying to actually figure the exact answer. This is not an easy problem.

Probability of at least 1 player getting a pair in a game of 12 players is approximately 79.0% by simulation.

lmao yes

I tried to take a nap that I very desperately need but couldn't keep from trying to work it out in my head until I finally got frustrated enough to get back up and trying to diagram a smaller case on paper. Which... did not go well. I think I'm dulled by fatigue because my little experimental diagram's results do not look right to me at all but I also have no idea how it would scale up... if it even would at all but it definitely seems more likely my brain can't function right now and I just made a dumb mistake with it.

---

Prob a particular player does not have a pair.

48/48 * 46/47 * 44/46 * 42/45 = .8738

Each fraction represents a card in the player's hand. For the first card there are no restrictions, the player can receive all 48 cards. For the second card, there is only one card in the deck the player cannot receive. The third card there are 2 cards the player can't receive. And following that pattern, the 4th card there are 3 cards the player cannot receive.

Unfortunately this approach doesn't extend easily to multiple players. You have to keep track of what the first player has.

****

Here's the probability that a specific pair of players each do not have a pair. Let me define some symbols.

Let X1 be the event that player 1 does not have a pair. Let X2 be the event that player 2 does not have a pair. Then, we are looking for P(X1 AND X2) = P(X1) * P(X2 | X1). Luckily we already know P(X1) = .8378. Let's now calculate P(X2|X1). Let Y = X2 | X1.

In this situation there are 20 pairs left and 4 cards without a pair for a total of 44 cards left in the deck. Player 2 can get 0, 1, 2, 3, or 4 of the cards that have no pairs.

Let Z0 be the event that player 2 got 0 of those cards.
Let Z1 be the event that player 2 got 1 of those cards.
Let Z2 be the event that player 2 got 2 of those cards.
Let Z3 be the event that player 2 got 3 of those cards.
Let Z4 be the event that player 2 got 4 of those cards.

Then, P(Y) = P(Y AND Z0) + P(Y AND Z1) + P(Y and Z2) + P(Y and Z3) + P(Y and Z4)
= P(Z0) * P(Y | Z0) + P(Z1) * P(Y | Z1) + P(Z2) * P(Y | Z2) + P(Z3) * P(Y | Z3) + P(Z4) * P(Y | Z4)

P(Y) = [ (4 C 0 * 40 C 4) / (44 C 4) ] * [ (40/40) * (38/39) * (36/38) * (34/37) ]
+ [ (4 C 1 * 40 C 3) / (44 C 4) ] * [ (40/40) * (38/39) * (36/38) ]
+ [ (4 C 2 * 40 C 2) / (44 C 4) ] * [ (40/40) * (38/39) ]
+ [ (4 C 3 * 40 C 1) / (44 C 4) ] * [ (40/40) ]
+ [ (4 C 4 * 40 C 0) / (44 C 4) ] * 1
P(Y) = P (X2 | X1) = .8745

Now we can calculate P( X1 AND X2) = P(X1) * P(X2|X1) = .8738 * .8745 = .7641

You can see that repeating this process would be tedious. But doable.

How to extend this solution.

Note that I had to use P( X_1 ) to find the probability that 2 specific players do not have a pair. Similarly, I'd need to use P( X_2 | X_1 ) to find the probability that 3 specific players do not have a pair. So let me define some more terms.

Let Y_1 = X_1, and then Y_i = X_i | Y_i-1 for i > 1. Then the probability of n specific players not having a pair would be P( Y_1 ) * P( Y_2) * ... * P( Y_n )

Let d_i = # of cards in the deck for a given player i, i.e. d_1 = 48, d_2 = 44, and so on. d_i = 48 - 4*(i-1)
Let a_i = # of cards with no pairs remaining for a given player i (assuming all previous players also have no pairs), i.e. a_1 = 0, a_2 = 4, a_3 = 8, and so on. a_i = 4*(i-1)
Let b_1 = # of cards whose pair remains in the deck under the same conditions, i.e. b_i + a_i = d_i

Then,
P( Y_n ) = [ (4 C 0 * b_n C 4) / (d_n C 4) ] * [ (b_n / b_n) * (b_n - 2 / b_n - 1 ) * ( b_n - 4 / b_n - 2) * ( b_n - 6 / b_n -3 ) ]
+ [ (4 C 1 * b_n C 3) / (d_n C 4) ] * [ (b_n / b_n) * (b_n - 2 / b_n - 1 ) * ( b_n - 4 / b_n - 2) ]
+ [ (4 C 2 * b_n C 2) / (d_n C 4) ] * [ (b_n / b_n) * (b_n - 2 / b_n - 1 ) ]
+ [ (4 C 3 * b_n C 1) / (d_n C 4) ] * [ (b_n / b_n) ]
+ [ (4 C 4 * b_n C 0) / (d_n C 4) ] * 1

got some sleep finally. not enough but it will do.

I feel vindicated because that concept (specifically the consideration of the events Z0, Z1, Z2, Z3, Z4 and the extension for n cases) was the basis of my paper experiment I was just too sleepy to apply proper combinatorics to it so it kinda turned into a trainwreck. >_>

But that was the solution method I did arrive at on the theory/concept level before finally crashing to sleep.

---

So what are the final answers to my two questions

Moonroof posted...

So what are the final answers to my two questions

89/705

Generalize DrPez's solution

---

12.6% per person.
What about for at least one person?

Moonroof posted...

12.6% per person.
What about for at least one person?

do the work yourself. you didn't even thank people for their walls of text explaining it

---

I certainly didnt thank you for lazily answering 89/705 instead of 12.6%.

wait people are responding seriously to moonroof

---

Ms Lasastrikeout, I get whatever I want whenever I want.

sess made that "ms lasa" joke like 10 years ago, up your troll game

---

Seems everyone is making fun of your lameness. You truly are pathetic

Also I reported you for trolling

Moonroof posted...

So what are the final answers to my two questions

The odds of a particular player having at least one pair is 1 - .8738 or 12.62%. No one has a number for the probability that at least one player out of 12 has a pair. But I gave an algorithm that could find that number. One simply has to follow the process repeatedly to find the actual number.

DrPez posted...

How to extend this solution.

Note that I had to use P( X_1 ) to find the probability that 2 specific players do not have a pair. Similarly, I'd need to use P( X_2 | X_1 ) to find the probability that 3 specific players do not have a pair. So let me define some more terms.

Let Y_1 = X_1, and then Y_i = X_i | Y_i-1 for i > 1. Then the probability of n specific players not having a pair would be P( Y_1 ) * P( Y_2) * ... * P( Y_n )

Let d_i = # of cards in the deck for a given player i, i.e. d_1 = 48, d_2 = 44, and so on. d_i = 48 - 4*(i-1)
Let a_i = # of cards with no pairs remaining for a given player i (assuming all previous players also have no pairs), i.e. a_1 = 0, a_2 = 4, a_3 = 8, and so on. a_i = 4*(i-1)
Let b_1 = # of cards whose pair remains in the deck under the same conditions, i.e. b_i + a_i = d_i

Then for 1 < n < 12
P( Y_n ) = [ (4 C 0 * b_n C 4) / (d_n C 4) ] * [ (b_n / b_n) * (b_n - 2 / b_n - 1 ) * ( b_n - 4 / b_n - 2) * ( b_n - 6 / b_n -3 ) ]
+ [ (a_n C 1 * b_n C 3) / (d_n C 4) ] * [ (b_n / b_n) * (b_n - 2 / b_n - 1 ) * ( b_n - 4 / b_n - 2) ]
+ [ (a_n C 2 * b_n C 2) / (d_n C 4) ] * [ (b_n / b_n) * (b_n - 2 / b_n - 1 ) ]
+ [ (a_n C 3 * b_n C 1) / (d_n C 4) ] * [ (b_n / b_n) ]
+ [ (a_n C 4 * b_n C 0) / (d_n C 4) ] * 1

and P( Y_12 ) = 1 because no cards with pairs will remain in the deck after the 11th player doesn't have a pair.

In particular if one wishes to find the probability that no player has a pair, you would need to calculate
P(Y) = P( Y_1 ) * P( Y_2 ) * P( Y_3 ) * P( Y_4 ) * P( Y_5 ) * P( Y_6 ) * P( Y_7 ) * P( Y_8 ) * P( Y_9 ) * P( Y_10) * P( Y_11 ) * P( Y_12 )

Then to get the probability that at least 1 player has a pair, you would calculate 1 - P(Y)

Found a small error on a reread. Fixed it.

ye but whats the final answer

---

With 100,000 trials my simulation CI for at least one pair amongst 12 players is probably pretty tight. We're talking like 79.0% +/- 0.25% for a 95% CI.

---

So, there is a flaw in my solution. Conceptually it's on the right track. But it doesn't count the cards left in the deck with pairs and without pairs correctly. Which means that some the terms will get more complicated. Complicated in such a way that I don't particularly care to try to fix at this moment. I'll get back to you guys if I do find a good fix. But don't hold your breath.

Lol, who wouldve thought this would be such a tough problem. I remember learning probability in school and I was pretty decent at it. I dont remember any of it though but its impressive to see some of you guys remember the formulas and whatnot.

NFUN posted...

ye but whats the final answer

It is being worked on. Relax, or contribute.

If anyone cares, my hours of playing with this problem has simplified the solution to a graph theory problem that I can't solve.

Given a fully-connected graph of N distinct nodes (in our case, N = 12), how many ways are there to assign each edge a value (0, 1, 2, 3, or 4) such that the sum of edge-values attached to any given node is equal to 4?

I have solved this problem for N = 2, 3, and 4. Values are 24, 1728, and 366336. Can't really generalize the solution (also no dice on OEIS) and the computation for each successive N takes longer and longer.

The value from that sub-problem represents the numerator of the complement of probability we desire. The denominator is simply (using double-factorial notation): (4N - 1)!!

I also came up with an alternative framing of the graph theory problem that got me nowhere, but it's more fun. Given N schools (again N = 12 in our case) each with 4 students, how many ways are there to pair up penpals between schools such that every student is writing to one other student in a different school?

---

tyder21 posted...

I also came up with an alternative framing of the graph theory problem that got me nowhere, but it's more fun. Given N schools (again N = 12 in our case) each with 4 students, how many ways are there to pair up penpals between schools such that every student is writing to one other student in a different school?

I took this framing and used it to code up a solver. It agrees with your answers for 2 and 3, but for 4 gets 368064 solutions?

At any rate, for 12, it yielded 2.49409e29 solutions, for a probability of .790864. The probability for 75, which is the highest the code can run, is 8.29087e305 solutions for a probability of .779103. Anything greater, and we run out of doubles >_>
---

dowolf posted...

Anything greater, and we run out of doubles >_>

please don't give me traumatic flashbacks to college and BigInteger ;_;

---

OK I also ran a simulation 10 million times, and got 79.09935% chance of at least one pair at the table (12 players, 48 cards, 24 pairs, hand size of 4).

Code here: https://gist.github.com/Epyo/1d4d51a39b3426229973bbf832009579

---

Well, both simulations appear to be consistent with dowolf's solution of 79.0864% so that's likely the exact solution.

---

Thank you! Im glad this sparked interest

dowolf posted...

but for 4 gets 368064 solutions?

Yeah, it's totally possible I goofed up the calculation a little bit there. Thanks for running your solver, I can finally rest easy now.

---

BigIntegers are wonderful! I'm just too lazy to rewrite stuff to get it working.

Anyways, here's the code, if anyone's curious: https://pastebin.com/SKY52mxB
---

Whew that's intense code, cool though!

---