Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a set of N elements. I want to select few elements from the set. Now each element i of the set has a probability P(i) of getting selected. Then how can I figure out the probability of selecting atleast K elements from the set?

K elements are required to be different. Some of the probabilities may be zero, but we are assured that there are atleast K elements whose probability is non zero.

share|improve this question
    
You don't give us enough to formulate a definite answer. Do you mean $K$ different elements? Are the probabilities all non-zero? Imagine there is only two elements but the probability to select one of them is zero, then you can not select more than one element. For how long can you go on selecting elements? If the answer is indefinitely and provided the probability to select any element is non-zero, then the answer to your question is $1$. –  Raskolnikov Mar 12 '11 at 19:31
    
K elements are required to be different. Some of the probabilities may be zero, but we are assured that there are atleast K elements whose probability is non zero. –  Suman Mar 13 '11 at 15:34

1 Answer 1

There's no easy solution, but if you want a slick expression you can try the generating function approach. Write $Q_i = 1-P_i + P_it$ and extract the coefficient of $t^{K-1}$ in $$\frac{\prod_{i=1}^n Q_i}{1-t}.$$ This is the probability that less than $K$ elements were selected.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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