# How many balls should we throw into $m$ bins so that at least $k$ bins get at least $r$ balls, with probability $1-\delta$?

Let $$m,k,r\in\mathbb N$$ and $$\delta\in(0,1)$$, such that $$k\le m$$.

Suppose that we throw balls uniformly and independently into $$m$$ bins.

I am looking for an upper bound $$N_{m,k,r,\delta}$$ on the number of balls that we need to throw to get at least $$k$$ bins with at least $$r$$ balls in each with probability at least $$1-\delta$$.

If $$r=1$$, this becomes a partial Coupon Collector process, and we can use a simple Chernoff bound to get a bound of $$N_{m,k,1,\delta}= m\ln \psi^{-1}+\psi^{-1}\ln\delta^{-1}+\sqrt{2m\psi^{-1}\ln\psi^{-1}\ln\delta^{-1}}\ ,$$ where $$\psi=\frac{m-k}{m}$$ is the fraction of in that is still empty.

Similarly, if $$k=m$$ (i.e., we want all bins to have at least $$r$$ balls), the problem is called the Double Dixie Cup, and using the Chernoff bound yields: $$N_{m,m,r,\delta}= 2m\cdot\left(r-1 + \ln(m/\delta)\right).$$

However, getting a bound for the general case (where $$k and $$r>1$$) seems more challenging.

Any ideas on how to derive such a bound?

Some thoughts:

We can mark by $$p_N=\sum_{i=r}^N{N\choose i}(1/m)^i(1-1/m)^{N-i}$$ the probability that a specific bin gets at least $$r$$ balls when we throw $$N$$.

Then the expected number of bins with at least $$r$$ balls is $$p_N\cdot m$$, and since they are negatively correlated (given that some bin has less than $$r$$ balls, the probability of another having more than $$r$$ increases), we can lower bound on the number by a binomial random variable $$X\sim(m,p_N)$$. Then we want to get $$\Pr[X which means that we will have to set $$N$$ such that $$p_N\approx c\cdot (k/m+\log(1/\delta))$$ for a suitable constant $$c$$.

However, translating this into a formal bound (extracting $$N$$ from it) may not be easy.

• @DenisSerre, "how many balls should we throw" and "how many balls should be thrown" are both grammatical, but your edit was not. Will you either fix this or revert? Oct 5, 2020 at 16:41