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<m$ 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<k]\le\delta$ 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.
