3
$\begingroup$

We have $K$ urns and $N$ balls. where $N\geq K$.

For each ball we uniformly select one of the urns and place the ball in it.


Question 1: What is the probability that all the urns will now have at least one ball in them? Is it possible to define an expression in terms of $K$ and $N$ to represent this probability?

I've implemented a simulation, here are some of the results for the following $K$-urns and $N$-Balls:

$$ \begin{align*} Pr(2,3) &\sim 75.0\% \\ Pr(5,10) &\sim 52.2\% \\ Pr(10,20) &\sim 21.5\% \\ Pr(20,40) &\sim 3.6\% \\ Pr(50,100) &\sim 0.0177\%\\ \end{align*} $$

Question 2: Is there an expression that can describe this probability if we wanted a fill percentage.

eg: What is the probability that only 60% of urns have at least one ball in them?

eg: What is the probability that at least 75% of urns have at least one ball in them?

$\endgroup$
  • 1
    $\begingroup$ Note: As an example, if we had 3 balls and 2 urns, there would be 8 ways we could place the balls in the urns, however there are only 6 ways in which there is at least one ball in each urn. $\endgroup$ – J Mkdjion May 13 '17 at 7:35
1
$\begingroup$

Question 1 can be done with inclusion-exclusion.

The probability of a specific urn being empty is $\big(1-\frac1K\big)^N$, because to avoid putting a ball in this urn, you have to choose one of the other urns at each step. Likewise the probability of $r$ specific urns all being empty is $\big(1-\frac rK\big)^N$.

Now the probability of at least one urn being empty is $$\binom K1\Big(1-\frac1K\Big)^N-\binom K2\Big(1-\frac2K\Big)^N+\cdots+(-1)^{r+1}\binom Kr\Big(1-\frac rK\Big)^N+\cdots+(-1)^{K}\binom K{K-1}\Big(1-\frac {K-1}K\Big)^N,$$ so to get the probability that no urns are empty, subtract this from $1$.

$\endgroup$
  • $\begingroup$ I attempted to evaluate your expression, but am not able to get results which are similar to the ones obtained using a simulation. any ideas on what could be amiss? $\endgroup$ – J Mkdjion May 13 '17 at 19:21
  • $\begingroup$ I don't know. What values of $n$ and $k$ did you try, and what did the simulation give? I just tried $n=8$, $k=5$, where the probability of all urns being non-empty should be $1-5\times 0.8^8+10\times 0.6^8-10\times 0.4^8+5\times 0.2^8\approx 0.323$. A quick simulation had this happening in $32113$ of $100000$ trials. $\endgroup$ – Especially Lime May 13 '17 at 21:58
  • $\begingroup$ is the probability defined as the following correct? : $$ 1 - \sum_{i=1}^{K-1} \left( (-1)^{i+1} \begin{pmatrix} K \\ i \end{pmatrix} \left( 1 - \frac{i}{K} \right)^{N} \right) $$ $\endgroup$ – J Mkdjion May 14 '17 at 0:01
  • $\begingroup$ Yes, that's correct $\endgroup$ – Especially Lime May 14 '17 at 7:46
1
$\begingroup$

Total number of ways to fill the urns without any restriction is $\binom{N+K-1}{K}$.

Question 1 is same as the number of tuples of nonnegative integer solutions to $$x_1+\cdots+x_K=N\\s.t.~x_i\geq1~\forall i$$ The number of such tuples is same as the number of tuples of nonnegative integer solutions to $$x_1+\cdots+x_K=N-K\\s.t.~x_i\geq0~\forall i$$ which is $$\binom{N-1}{K}$$ Thus the probability that all the urns will be non-empty is $$\frac{\binom{N-1}{K}}{\binom{N+K-1}{K}}$$

Question 2: Suppose more than fraction $p,~0\leq p\leq(1-1/K),$ of the urns contains at least one ball. Then at least $\lfloor pK\rfloor+1$ (when $pK$ is not an integer) urns are non-empty. It can be any $\lfloor pK\rfloor+1$ urns from the $K$ urns. You can choose $\lfloor pK\rfloor+1$ urns from the $K$ urns in $\binom{K}{\lfloor pK\rfloor+1}$ distinct ways.

Now the number of tuples of nonnegative integer solutions to $$x_1+\cdots+x_K=N-K\\s.t.~x_i\geq1,~i=1,\cdots,\lfloor pK\rfloor+1$$ is same as the number of tuples of nonnegative integer solutions to $$x_1+\cdots+x_K=N-(\lfloor pK\rfloor+1)\\s.t.~x_i\geq0~\forall i$$ which is $$\binom{N-(\lfloor pK\rfloor+1)+K-1}{K}$$

So the number of ways so that more than fraction $p$ of the urns are nonempty, is $$\binom{K}{\lfloor pK\rfloor+1}\binom{N-\lfloor pK\rfloor+K-1}{K}$$

If $pK$ is an integer then the solution is $$\binom{K}{pK}\binom{N- pK+K-1}{K}$$ Thus the probability that more than fraction $p$ of the $K$ urns will be non-empty is $$\frac{\binom{K}{\lfloor pK\rfloor+1}\binom{N-\lfloor pK\rfloor+K-1}{K}}{\binom{N+K-1}{K}}~\text{if}~ pK ~\text{is not an integer}$$ and $$\frac{\binom{K}{pK}\binom{N- pK+K-1}{K}}{\binom{N+K-1}{K}}~\text{if}~ pK ~\text{is an integer}$$

$\endgroup$
  • $\begingroup$ I don't quiet see how your answers apply. In both questions a probability is required (a value between 0 and 1), also please take into account the scenario were all the balls are placed into one urn or the scenario where all the balls bar one are placed into the same one urn and the remaining ball is in another urn - how is that $ \begin{pmatrix} N-1\\ k \end{pmatrix} $ $\endgroup$ – J Mkdjion May 13 '17 at 6:38
  • $\begingroup$ These are the number of ways to fill the urns in the ways specified in the above questions. If you want the probability, just divide these numbers by the total number of ways to fill the urns which is $$\binom{N+K-1}{K}$$ $\endgroup$ – Abishanka Saha May 13 '17 at 6:40
  • $\begingroup$ edited for your help $\endgroup$ – Abishanka Saha May 13 '17 at 6:46
  • 2
    $\begingroup$ This is incorrect because the things you are counting are not equally likely. $\endgroup$ – Especially Lime May 13 '17 at 7:32
  • 2
    $\begingroup$ If you randomly place two balls in two bins, there are $3$ possible arrangements: one in each, both in the first, or both in the second. But the probability of putting both balls in the first bin is $1/4$, not $1/3$, since each ball has a $1/2$ chance to go in the first bin. $\endgroup$ – Especially Lime May 13 '17 at 7:48

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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