Probability of filling all urns

Question

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?

Answer 1

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$.

Answer 2

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}$$