Skip to main content
1 of 5
Don C
  • 51
  • 2

How many balls we need to through into $m$ bins to get at least $k$ with 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\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.

Don C
  • 51
  • 2