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

## 1 Answer

Let $$N\geq kr$$ denote a possible number of balls. Using Laplace's definition of probability, one finds that the probability that at least $$k$$ bins get at least $$r$$ balls equals $$$$\frac{{m \choose k}{N-kr+m-1 \choose m-1}}{{N+m-1 \choose m-1}},$$$$ which simplifies to $$$${m \choose k}\prod_{i=0}^{kr-1}\frac{N-i}{N-i+(m-1)}.$$$$

The problem comes down to finding the smallest natural number $$N$$ such $$\sum_{i=0}^{kr-1}\log\bigg(1+\frac{m-1}{N-i}\bigg)\leq\log\bigg(\frac{{m \choose k}}{1-\delta}\bigg)$$ (by considering the reciprocals of the factors above).

Now, the LHS is bounded from above by the expression $$kr \log \Bigg( 1 + \frac{m-1}{N-kr+1}\Bigg),$$ which is smaller than or equal to the RHS if and only if $$N \geq \frac{m-1}{exp \Bigg( \frac{\log\big(\frac{{m \choose k}}{1-\delta}\big)} {kr}\Bigg)-1} + kr-1 := C_0.$$

Consequently, $$N_{m,k,r,\delta}=ceiling(C_0)$$ should do.