0
$\begingroup$

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.

  • 0
    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.2011-03-13

1 Answers 1

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.