What is the probability of this?

[EngWiPy]

Hi,

Suppose that there are M persons, and K balls number from 1 to K. Each person pulls k balls at the same time, and return them back. What is the probability that all persons pull the same k balls?

Thanks

 

[tiny-tim]

Hi S_David!

tell us what you think, and then we'll comment!

 

[EngWiPy]

Hi S_David!

tell us what you think, and then we'll comment!

Well, if we suppose that the probability of each ball is p, then the probability of a specific k-tuple is:

{K\choose k}p^k(1-p)^{K-k}

I guess the probability that all persons will pull the same k-tuple, will be:

\left({K\choose k}p^k(1-p)^{K-k}\right)^M

Is that true?

 

[chiro]

Are there K balls in total for everyone or K balls per person?

 

[haruspex]

Well, if we suppose that the probability of each ball is p, then the probability of a specific k-tuple is:

{K\choose k}p^k(1-p)^{K-k}

No, that's quite wrong. How many equally likely k-tuples are there? So what is the chance of picking a particular one?

 

[EngWiPy]

Are there K balls in total for everyone or K balls per person?

We have K balls in total, where each person pick up k balls, and then return them back to the box. So each person has the same set of balls to pick from them.

 

[EngWiPy]

No, that's quite wrong. How many equally likely k-tuples are there? So what is the chance of picking a particular one?

We have K choose k distinct k-tuple patterns. Right?

 

[viraltux]

We have K choose k distinct k-tuple patterns. Right?

The solution you gave is the probability that M persons choose the same number of balls regardless their label.

But you already know they choose the same number of balls, soooooo...

 

[EngWiPy]

The solution you gave is the probability that M persons choose the same number of balls regardless their label.

But you already know they choose the same number of balls, soooooo...

clue:

Imaging 3 balls

000
001
010
011
100
101
110
111

What is the probability M persons choose 010?

I am sot sure! Another tip?

 

[chiro]

We have K balls in total, where each person pick up k balls, and then return them back to the box. So each person has the same set of balls to pick from them.

In this case, this is wrong.

I think what you mean and correct me if I'm wrong, is that you have K balls and everyone takes turns in picking the balls out, not that they all pick out the balls at once.

If they all pick them out at once, then there is no way they can pick out the same balls and the question is not even valid.

So let's assume that they take turns and they pick out the balls each turn for each person and the process is random in line with the assumptions of a binomial distribution. We assume that after the person has picked the balls, they put them back in and the whole thing starts again.

Then under this situation, you will need to calculate the probability of getting the specific number of balls taking into account that the balls are in fact the same. This should be done from first principles to clarify and not just using a distribution in ad-hoc manner.

So in terms of calculating the probability of getting a particular set of balls you need to calculate the following probability:

Let your balls be a,b,c and let A be the first ball, B the second, and C the third. Let X = (A = a) XOR (B = a) XOR (C = a), Y = (A = b) XOR (B = b) XOR (C = b) and Z = (A = c) XOR (B = c) XOR (C = c). Then you need to calculate the probability P(X AND Y AND Z).

Where the XOR is the symmetric difference which is given by (A XOR B) = (A\B) OR (B\A).

You can use the fact that A,B,C are not the same since picking up a ball and not replacing it until the round has finished will change what happens to later balls in the same round.

If you expand the probabilities then you should get a simpler expression which will give you the actual probability and you will have to use the Kolmogorov axioms at some point for calculating P(A OR B) and so on.

You could also do it with the binomial in the way that you calculate getting k balls out of K and then factoring in that you only get one type of permutation of your balls out of all permutations, but still account for getting them in any order. This would probably be easier to calculate in contrast with the raw probability calculation above.

 

[viraltux]

I am sot sure! Another tip?

Well, I guess that one was not a very good tip anyway

OK, imaging you have 5 balls 1,2,3,4,5 what is the probability you pick, let's say 2 and 4? Well, then you would go the pair 2,4 divided by all the possible pairs in 1,2,3,4,5.

So that is the probability you choose one particular pair, so that is the probability anyone else chooses that one particular pair... sooo... what is your guess now?

 

[EngWiPy]

Well, I guess that one was not a very good tip anyway

OK, imaging you have 5 balls 1,2,3,4,5 what is the probability you pick, let's say 2 and 4? Well, then you would go the pair 2,4 divided by all the possible pairs in 1,2,3,4,5.

So that is the probability you choose one particular pair, so that is the probability anyone else chooses that one particular pair... sooo... what is your guess now?

If we suppose that probability of ball i is pi, then the probability of choosing 2 and 4 is:

p_2p_4(1-p_1)(1-p_3)(1-p_5)

Right?

Then why we need to divide by the number of pairs?

 

[viraltux]

If we suppose that probability of ball i is pi, then the probability of choosing 2 and 4 is:

p_2p_4(1-p_1)(1-p_3)(1-p_5)

Right?

Then why we need to divide by the number of pairs?

What? that's a new problem! in the way you stated your problem every ball is equally likely to be chosen...

Suppose that there are M persons, and K balls number from 1 to K. Each person pulls k balls at the same time, and return them back. What is the probability that all persons pull the same k balls?

OK, the solution for the this problem as it is stated is {{K}\choose{k}}^{-M}

 

[chiro]

If we suppose that probability of ball i is pi, then the probability of choosing 2 and 4 is:

p_2p_4(1-p_1)(1-p_3)(1-p_5)

Right?

Then why we need to divide by the number of pairs?

Dude, just do a binomial distribution and adjust for the different permutations so that you only select 1 permutation since all permutations are equally likely.

How many permutations can you have when you select 3 balls from 6? (Hint: Use combinatorics)

 

[EngWiPy]

What? that's a new problem! in the way you stated your problem every ball is equally likely to be chosen...



OK, the solution for the this problem as it is stated is {{K}\choose{k}}^{-M}

What if they are not equally likely? Why p does not appear in the probability?

Actually, this is not the real question. The real question is: if each person pulls different number of balls, what is the probability that the cardinality of the intersection between all users is m?

 

[chiro]

What if they are not equally likely? Why p does not appear in the probability?

Actually, this is not the real question. The real question is: if each person pulls different number of balls, what is the probability that the cardinality of the intersection between all users is m?

Maybe you should ask the real question first off :)

Use probability axioms for situations that don't fit existing models.

 

[EngWiPy]

Maybe you should ask the real question first off :)

Use probability axioms for situations that don't fit existing models.

I am sorry, but it is just so confusing to me. I am not so good in probability, and I am trying to figure this out, since I am working on an engineering model, that has the same issue.

Thanks

 

[viraltux]

What if they are not equally likely? Why p does not appear in the probability?

Actually, this is not the real question. The real question is: if each person pulls different number of balls, what is the probability that the cardinality of the intersection between all users is m?

It does not appear because every ball is supposed to have the same probability and that simplifies the problem.

In the new stated problem, again, every ball has the same probability! so you already know your new solution won't have any p either...

 

[EngWiPy]

It does not appear because every ball is supposed to have the same probability and that simplifies the problem.

In the new stated problem, again, every ball has the same probability! so you already know your new solution won't have any p either...

OK, I will try to figure it out. Thanks

 

[viraltux]

OK, I will try to figure it out. Thanks

No problem, but anyway, the answer for your new problem, assuming equally likely every cardinality, is K^{-M}.
I think you've just suffered enough

 

[haruspex]

OK, the solution for the this problem as it is stated is {{K}\choose{k}}^{-M}

Not quite. That's the prob they all pick the same prespecified k. But it could be any k, so long as they all pick the same k:
{{K}\choose{k}}^{-M+1}

 

[viraltux]

Not quite. That's the prob they all pick the same prespecified k. But it could be any k, so long as they all pick the same k:
{{K}\choose{k}}^{-M+1}

The original problem was:

Suppose that there are M persons, and K balls number from 1 to K. Each person pulls k balls at the same time, and return them back. What is the probability that all persons pull the same k balls?

That pretty much specifies the number of balls that are extracted: k

But even if you transform the problem and turn "each person pulls k" into "each person pulls the same number" being those numbers equally likely, and the question "What is probability that all persons pull the same k balls?" into "What is probability that all persons pull the same balls?" Then the answer would be:

\frac{1}{K+1}\sum_{k=0}^K {{K}\choose{k}}^{-M}

 

[haruspex]

Let's take a simple example. K=2, k=1, M=2.
Each takes one ball and replaces it. What's the probability they take the same ball?
You say
{{K}\choose{k}}^{-M} = 2^-2 = 1/4
I say {{K}\choose{k}}^{-M+1} = 2^-1 = 1/2
Think about it.

 

[viraltux]

Let's take a simple example. K=2, k=1, M=2.
Each takes one ball and replaces it. What's the probability they take the same ball?
You say
{{K}\choose{k}}^{-M} = 2^-2 = 1/4
I say {{K}\choose{k}}^{-M+1} = 2^-1 = 1/2
Think about it.

Oh, by 'prespecified' k you meant the actual set contained within the k balls, yes, then you're right.

 

[ClifDavis]

Hi,

Suppose that there are M persons, and K balls number from 1 to K. Each person pulls k balls at the same time, and return them back. What is the probability that all persons pull the same k balls?

Thanks

David, I understand that this is not the actual problem you want to solve. What is the problem you want to solve?

 

[EngWiPy]

David, I understand that this is not the actual problem you want to solve. What is the problem you want to solve?

If each person pulls different number of balls, what is the probability that the cardinality of the intersection between all users is m?

 

[ClifDavis]

If each person pulls different number of balls, what is the probability that the cardinality of the intersection between all users is m?

Okay let me restate the problem to see if I understand it correctly.

There are M people and K distinct balls. Each of those M people will pick a number k at random between one and K inclusive and then pick k balls at random. An reliable observer will record which balls they picked. Then the selected balls are put back for the next person. After all M of these people have done this the reliable observer informs us that none of the M people picked the same number k of balls to select.

Someone gives us an integer m. We want to give them the odds that the intersection of the ball picks contains exactly m balls.

Is this a correct statement of the problem?

 

[EngWiPy]

Okay let me restate the problem to see if I understand it correctly.

There are M people and K distinct balls. Each of those M people will pick a number k at random between one and K inclusive and then pick k balls at random. An reliable observer will record which balls they picked. Then the selected balls are put back for the next person. After all M of these people have done this the reliable observer informs us that none of the M people picked the same number k of balls to select.

Someone gives us an integer m. We want to give them the odds that the intersection of the ball picks contains exactly m balls.

Is this a correct statement of the problem?

Ok, let me elaborate more: We have M person and K distinct balls numbered from 1 to K. Each person will pull a number of balls, i.e.: the number of picked balls is not known a priori. Then he will return the balls to the next person (after taking the balls' numbers by a reliable observer) who will do the same thing. At the end we will find the intersection between the balls picked by all persons. I need to find the probability that the cardinality of this intersection is m, where m is an integer between 1 and K.

I hope it is more clear now.

Thanks

 

[ClifDavis]

Ok, let me elaborate more: We have M person and K distinct balls numbered from 1 to K. Each person will pull a number of balls, i.e.: the number of picked balls is not known a priori. Then he will return the balls to the next person (after taking the balls' numbers by a reliable observer) who will do the same thing. At the end we will find the intersection between the balls picked by all persons. I need to find the probability that the cardinality of this intersection is m, where m is an integer between 1 and K.

I hope it is more clear now.

Thanks

Ok, let me elaborate more: We have M person and K distinct balls numbered from 1 to K. Each person will pull a number of balls, i.e.: the number of picked balls is not known a priori. Then he will return the balls to the next person (after taking the balls' numbers by a reliable observer) who will do the same thing. At the end we will find the intersection between the balls picked by all persons. I need to find the probability that the cardinality of this intersection is m, where m is an integer between 1 and K.

I hope it is more clear now.

Thanks

In order to answer the question it is not necessary to know the number of picked balls a priori. It is however necessary to know the probability distribution of the number of balls picked.

If there are M=2 people and K=5 distinct balls and there is a very high probability of 4 or 5 balls getting picked and none at all of 1 or 2 balls, then it is a very different situation than if there is no probability of 4 or 5 balls being picked and a high probability ofr 1 or 2 balls.

If I understand your question, there is not enough information to answer it.

 

[EngWiPy]

In order to answer the question it is not necessary to know the number of picked balls a priori. It is however necessary to know the probability distribution of the number of balls picked.

If there are M=2 people and K=5 distinct balls and there is a very high probability of 4 or 5 balls getting picked and none at all of 1 or 2 balls, then it is a very different situation than if there is no probability of 4 or 5 balls being picked and a high probability ofr 1 or 2 balls.

If I understand your question, there is not enough information to answer it.

All balls are equiprobable to be picked up. Is it still not complete?

 

[haruspex]

ClifDavis is right, of course: you need to specify the probability distribution for k.
But it sounds from an earlier post that k is supposed to have a uniform distribution from 1 to K. If so, it sounds like a very nasty problem.

 

[haruspex]

All balls are equiprobable to be picked up. Is it still not complete?

No, it's still not complete. That piece of information all sets of k balls are equally likely once k is chosen. You still haven't said how k is chosen.

 

[EngWiPy]

No, it's still not complete. That piece of information all sets of k balls are equally likely once k is chosen. You still haven't said how k is chosen.

You can assume a distribution to simplify it. I just need to see the idea.

 

[haruspex]

In that case I select a binomial distribution. This means I can rephrase it as "each ball is chosen independently with probability p".
The probability that a given ball is selected by all M is then p^M.
The number of balls selected by all is binomial with parameter p^M.
However, I have violated the statement that k must be 1 to K. I've made it 0 to K. Is that alright?

 

[EngWiPy]

In that case I select a binomial distribution. This means I can rephrase it as "each ball is chosen independently with probability p".
The probability that a given ball is selected by all M is then p^M.
The number of balls selected by all is binomial with parameter p^M.
However, I have violated the statement that k must be 1 to K. I've made it 0 to K. Is that alright?

Yeah.

 

[viraltux]

In that case I select a binomial distribution. This means I can rephrase it as "each ball is chosen independently with probability p".
The probability that a given ball is selected by all M is then p^M.
The number of balls selected by all is binomial with parameter p^M.
However, I have violated the statement that k must be 1 to K. I've made it 0 to K. Is that alright?

The last time S_David explained the problem it seemed he is worried about "the cardinality of the intersection" which I think hardly relates to the "The number of balls selected by all"

Rephrasing the problem this way turns it into a different one. When a problem states thing like "Each person will pull a number of balls" the most common approach is to assume every number is equally likely. It would be like asking people to choose a number from 0 to K, if we do not consider things like psychological biases (like people choosing their favorite number) the most reasonable is to assume every number is equally likely. The moment you assign a probability p to a ball to be chosen then it implies things like "it is more likely people choose 4 balls than 5", which I see this nowhere in the problem. Not to mention that with this approach you need to estimate p which is not given by the problem.

Also, in any case, when a given ball is selected by all M is then p^M, but the probability that all M select the same ball is p^M-1... unless the problem has changed again which wouldn't be surprising at this point.

Ok, let me elaborate more: We have M person and K distinct balls numbered from 1 to K. Each person will pull a number of balls, i.e.: the number of picked balls is not known a priori. Then he will return the balls to the next person (after taking the balls' numbers by a reliable observer) who will do the same thing. At the end we will find the intersection between the balls picked by all persons. I need to find the probability that the cardinality of this intersection is m, where m is an integer between 1 and K.

I hope it is more clear now.

Thanks

I don't think there is information missing in this problem, the key difficulty lays in the "cardinality of this intersection" part. If we had the distribution for the intersection of cardinalities of M subsets within a set of cardinality K the problem is done.

I did calculate such distribution of m for any given cardinalities C₁ and C₂ considering M=2 and is already huge, and for M>2 it only gets worse

I think would I go Montecarlo on this one.

 

[ClifDavis]

Well, if we suppose that the probability of each ball is p, then the probability of a specific k-tuple is:

{K\choose k}p^k(1-p)^{K-k}

I guess the probability that all persons will pull the same k-tuple, will be:

\left({K\choose k}p^k(1-p)^{K-k}\right)^M

Is that true?

Now that we know what the actual problem is we can see where his
{K\choose k}p^k(1-p)^{K-k} came from. You have the probability of getting k picks followed by K-k non-picks, which gives you one instance of picking k balls and since any selection of k balls is equally probable you multiply by the number of ways of getting k balls. Without having given it tons of thought, that looks reasonable to me. But then he goes off the tracks a little when he looks at all of the people doing the same thing.

David, suppose that I have M people and they all flip a coin. The probability of heads is 1/2 and the probability of tails is 1/2. Is the probability they all get the same result when they flip their coin = (1/2)^M Look at it if I have 3 people or 2.

(edited because I don't really understand how the tex stuff works)

 

[ClifDavis]

Now that we know what the actual problem is we can see where his
{K\choose k}p^k(1-p)^{K-k} came from. You have the probability of getting k picks followed by K-k non-picks, which gives you one instance of picking k balls and since any selection of k balls is equally probable you multiply by the number of ways of getting k balls. Without having given it tons of thought, that looks reasonable to me. But then he goes off the tracks a little when he looks at all of the people doing the same thing.

David, suppose that I have M people and they all flip a coin. The probability of heads is 1/2 and the probability of tails is 1/2. Is the probability they all get the same result when they flip their coin = (1/2)^M Look at it if I have 3 people or 2.

(edited because I don't really understand how the tex stuff works)

David, going back and rereading what I wrote I can see where I could give the impression that simply correcting the last part of your expression to ({(K\choose k}p^k(1-p)^{K-k})^{M-1} would fix all you problems. It wouldn't. That expression would give the probability that all M people would pick the same k balls. Which isn't what you want at all.

Each of the M people could pick extra balls that all don't pick and you would still have k balls in in the intersection.

But let's go back to your original logic in coming up with the expression
{K\choose k}p^k(1-p)^{K-k}
You had the probability that the first k balls were picked times the probability that the next K-k balls were not picked by the first person to get a specific instance of k balls being picked by one person which you then multiplied to find the probability that one person would pick k balls.

Now suppose instead you had taken the probability that the first k balls were picked [By all M people] followed by the probability that the final K-k balls were [not picked by all M people] to get the probability that a particular set of k balls were picked by everyone and then multiplied by the number of ways to get k balls -- would that not do it?

 

[haruspex]

The last time S_David explained the problem it seemed he is worried about "the cardinality of the intersection" which I think hardly relates to the "The number of balls selected by all"

A ball is in the intersection if it was chosen by all. The cardinality of the intersection is the number of balls chosen by all.

 

[haruspex]

Now suppose instead you had taken the probability that the first k balls were picked [By all M people] followed by the probability that the final K-k balls were [not picked by all M people] to get the probability that a particular set of k balls were picked by everyone and then multiplied by the number of ways to get k balls -- would that not do it?

To do that calculation, you still need to know the probability distribution of k.
But it seems David_S is not that wedded to his "pick k, then pick k balls" formulation (which is what made the problem hard).
Given that he's happy with a binomial distribution for k, do you agree that allows us to rephrase it as "pick each ball independently with the same probability p"? Do you further agree that this gives a binomial distribution for the cardinality of the intersection, parameter p^M?

 

[ClifDavis]

To do that calculation, you still need to know the probability distribution of k.
But it seems David_S is not that wedded to his "pick k, then pick k balls" formulation (which is what made the problem hard).
Given that he's happy with a binomial distribution for k, do you agree that allows us to rephrase it as "pick each ball independently with the same probability p"? Do you further agree that this gives a binomial distribution for the cardinality of the intersection, parameter p^M?

I agree. In fact judging by his initial attempt at a solution it really seems to be what he had in mind from the beginning.

In fact, my question to him should be read, "given that each ball is picked by each person with a probability p, if you had taken the probability that the first k balls were picked [By all M people] followed by the probability that the final K-k balls were [not picked by all M people] to get the probability that a particular set of k balls were picked by everyone (and so constitute the intersection) and then multiplied by the number of ways to get k balls -- would that not provide the probability that exactly k balls were in the intersection?"

Edited for Clarification.

 

[ClifDavis]

The last time S_David explained the problem it seemed he is worried about "the cardinality of the intersection" which I think hardly relates to the "The number of balls selected by all"

A ball is in the intersection if it was chosen by all. The cardinality of the intersection is the number of balls chosen by all.

Yeah, I will admit to being curious about what viraltux thinks "cardinality of the intersection" does relate to.

 

[EngWiPy]

In that case I select a binomial distribution. This means I can rephrase it as "each ball is chosen independently with probability p".
The probability that a given ball is selected by all M is then p^M.
The number of balls selected by all is binomial with parameter p^M.
However, I have violated the statement that k must be 1 to K. I've made it 0 to K. Is that alright?

OK, when I thought about this in my system model, this solution makes sense. Thanks