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.

  • 2
    $\begingroup$ @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? $\endgroup$
    – Matt F.
    Oct 5, 2020 at 16:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.