0
$\begingroup$

I'm trying to solve a combinatorics problem for a program I am writing but I'm having some trouble. Here's an abstracted version...

I have 5 people with weights assigned to them

A: 500
B: 300
C: 200
D: 150
E: 100

What is the probability of Person B being selected if I choose 3 at a time given these weights (without replacement)? So a result set might look like [A,D,E], [C,B,A], etc.

If I set all the weights to 100 I can calculate the probability as

(1/5) + (4/5)(1/4) + (4/5)(3/4)(1/3) = 3/5

I'm thinking about it as the probability B is chosen the first time plus the probability it wasn't chosen the first time multiplied by the probability it is chosen the second time, and so on for the third time, but I'm getting confused and stuck as soon as I try to expand with different values.

I'm looking for some sort of formula that would help me quickly calculate probabilities for hundred of different weightings.

Thanks in advance for the help!

EDIT: Seems like this is definitely know as a WRS-N-W problem or Weighted Random Sampling without Replacement, with defined Weights

$\endgroup$
  • 1
    $\begingroup$ You need to define what you want these "weights" to mean. This paper might help clear things up. I suspect that what you have in mind is Definition $3$ on p. $5$ of the PDF? $\endgroup$ – joriki Sep 14 '15 at 21:31
  • $\begingroup$ Thanks, I'm looking in to that paper. I'm not quite sure how to define these weights per say but what I mean is that the probability of A being chosen first would be 500/1250, B would be 300/1250, etc. $\endgroup$ – Kenny Bania Sep 14 '15 at 21:41
  • 1
    $\begingroup$ And then in the second step, the same procedure using only the weights of the remaining items? E.g., if A is drawn first, the probability for B to be drawn in the second step would be $300/750$? That would be Definition $3$ in the paper. $\endgroup$ – joriki Sep 14 '15 at 21:42
  • $\begingroup$ Correct. Great, so it's definitely an WRS-N-W problem. Could you help me use that definition or an algorithm to solve an example? The paper makes it look like I want to use something called the A-ES algorithm but I'm not understanding how that works right off. Thanks for the help so far! $\endgroup$ – Kenny Bania Sep 14 '15 at 21:52
  • $\begingroup$ The paper deals with sampling algorithms. From the question, I understand that you're interested in calculating probabilities. Those are quite different problems -- I doubt that the (very elegant) sampling algorithms in the paper will be of help in calculating the probabilities -- I only linked to it because it has a clear exposition of the different possible interpretations of weights in sampling without replacement. $\endgroup$ – joriki Sep 14 '15 at 21:57
1
$\begingroup$

I don't see a simple way to do this; I'm afraid you may just have to add up all the probabilities of the branches that include $B$. That's $1+4+12=17$ terms, so I'll do it for $B$ as one of two items drawn and hopefully you can take it from there.

The probability to draw $B$ in the first draw is $300/1250$. The probability to draw $B$ in the second draw is

$$ \frac{500}{1250}\cdot\frac{300}{750}+ \frac{200}{1250}\cdot\frac{300}{1050}+ \frac{150}{1250}\cdot\frac{300}{1100}+ \frac{100}{1250}\cdot\frac{300}{1150}=\frac{11481}{44275}\;, $$

and the sum is

$$ \frac{300}{1250}+\frac{11481}{44275}=\frac{22107}{44275}=\frac12-\frac{61}{88550}\approx0.4993\;. $$

$\endgroup$
  • $\begingroup$ Then to summarize, the only way to get the probability of B occurring is to sum the probabilities of every combination that includes B? This has been my basic understanding but I was hoping for some sort of more elegant solution. $\endgroup$ – Kenny Bania Sep 15 '15 at 14:00
  • 1
    $\begingroup$ @KennyBania: Yes, I think so (though you never know...). There are elegant solutions for similar problems (and the paper I linked to gives a very elegant solution to the corresponding sampling problem), but I don't see one for this one. $\endgroup$ – joriki Sep 15 '15 at 14:03
  • $\begingroup$ I'm having trouble understanding exactly how to expand your math to calculate the probability B is in the 3rd draw. Any assistance would be greatly appreciated. If I understand you right (500/1250)*(300/750) is the odds A was selected first times the odds B was selected after A. But for the probability B was selected last, would I not need to calculate 12 terms instead of 6, as there are 12 different ways that B could appear last? $\endgroup$ – Kenny Bania Sep 15 '15 at 15:58
  • $\begingroup$ @KennyBania: Sorry, you're right, I've corrected the answer in that regard. Does that clear it up? $\endgroup$ – joriki Sep 15 '15 at 16:00
  • 1
    $\begingroup$ Yes, thanks for the correction, you've been very helpful $\endgroup$ – Kenny Bania Sep 15 '15 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.