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.


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 \begin{equation} \frac{{m \choose k}{N-kr+m-1 \choose m-1}}{{N+m-1 \choose m-1}}, \end{equation} which simplifies to \begin{equation} {m \choose k}\prod_{i=0}^{kr-1}\frac{N-i}{N-i+(m-1)}. \end{equation}

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.