There are $N$ items, numbered $1 \ldots N$. The probability of selecting item $i$ in one draw is $p_i$. Items are drawn without replacement, so after each draw we need to do a re-normalization. Now, could you please tell me how to write down the probability of drawing $i$ in $k$ ($k \le N$) attempts? Even an approximate solution is good. Thanks!
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ random sampling? drawing at least once? exactly once? something else? .. Is this an exercise for a class? $\endgroup$– Glen_bCommented Jun 19, 2016 at 17:28
-
1$\begingroup$ I think the sampling without replacement implies you can only draw $i$ once. $\endgroup$– Kitter CatterCommented Jun 19, 2016 at 18:01
-
$\begingroup$ @Glen_b Yes. Only draw i once. Not an exercise for a class. Basically, one can write a program to enumerate all combinations. But it is very slow. Are there any closed form solution or approximated solution? Thanks! $\endgroup$– ZillGateCommented Jun 19, 2016 at 18:04
-
1$\begingroup$ Sounds like you are looking for the multivariate Wallenius' noncentral hypergeometric distribution. ie weighted balls, multiple colors, multiple draws. wikipedia link $\endgroup$– Kitter CatterCommented Jun 19, 2016 at 18:10
-
$\begingroup$ @KitterCatter Thanks! This is what I am looking for. Please post an answer and I will accept it. Thanks! $\endgroup$– ZillGateCommented Jun 20, 2016 at 1:08
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Sounds like you are looking for the multivariate Wallenius' noncentral hypergeometric distribution. ie weighted balls, multiple colors, multiple draws.wikipedia link
I did try to find something analytic, but even in simple cases this problem becomes increasingly complicated. I would advise looking at some of the packages in the link.
$\begingroup$
$\endgroup$
1
A long comment which I have have had to post as an answer. I have no objection if some kindly Moderator converts it into a series of comments on the main question.
Your question is essentially unanswerable in one sense.
You have told us that the probability of drawing the $i$-th object on the first draw is $p_i$. In the general scheme of drawing with replacement, the probability of drawing the $i$-th object remains the same on all further draws.
However, in the general scheme of drawing without replacement (which you want to consider), there is no immediate answer to the question: what is the probability of drawing the $i$-th object on the second draw? the third draw? etc. There is also the question whether we want the unconditional probability of drawing the $i$-th object on the second draw, or the conditional probability of drawing the $i$-th object on the second draw given that the first draw resulted in the $j$-th object being drawn?
One possibility to consider is that the (conditional) probabilities are obtained by re-normalizing the probabilities of the remaining balls at each step. That is, we write \begin{align} P(i_i) &= p_{i_1},\\ P(i_1, i_2) &= p_{i_1}\cdot \frac{p_{i_2}}{1-p_{i_1}}\\ P(i_1, i_2,i_3) &= p_{i_1}\cdot \frac{p_{i_2}}{1-p_{i_1}} \cdot \frac{p_{i_3}}{1-p_{i_1}-p_{i_2}}\\ P(i_1, i_2,i_3,i_4) &= p_{i_1}\cdot \frac{p_{i_2}}{1-p_{i_1}} \cdot \frac{p_{i_3}}{1-p_{i_1}-p_{i_2}} \cdot \frac{p_{i_4}}{1-p_{i_1}-p_{i_2}-p_{i_3}} \end{align} and so on. But there could be other kinds of assumptions that might be made about what happens on successive draws, and so unless you specify what the probabilities are on successive draws, w=your question is unanswerable.
answered Jun 20, 2016 at 2:41
-
$\begingroup$ Thank you very much for your detailed comments. I agree that the original problem description is unclear. I have added renormalization to the description now. $\endgroup$– ZillGateCommented Jun 20, 2016 at 19:20
$\begingroup$
$\endgroup$
2
Since you asked for an approximation, I will propose one. It's not perfect: it requires additional reasonable assumptions; I won't prove it's accurate; I'm not sure it's a valid pmf.
If $N$ is large, $K << N$, and the $p_j's$ are small, then drawing once gives a probability of $p_j$. The next draw will be only slightly better than $p_j$, etc. The draws are not independent, but are not too dependent. So I would approximate drawing the desired event in $K$ trials as drawing one sample in a poisson with $\lambda=K \times p_j$.
This gives you a probability of $K \times p_j \times e^{-K p_j}$.
-
$\begingroup$ Thanks! Under these assumptions, I guess we can directly use 1 - (1 - p_j)^K? $\endgroup$– ZillGateCommented Jun 20, 2016 at 19:26
-
1$\begingroup$ You could compare both of these approximations with the Wallenius mentioned by @Kitter Catter, for the values of K, N, and $p_j$ you expect. In R there is a package BiasedUrn. $\endgroup$ Commented Jun 21, 2016 at 4:09