Balls and bins with color

Question

Say I have $n$ balls each of $k$ different colors (i.e. $nk$ balls altogether), and I throw these balls independently into $N$ bins. Is there anything that can be said (in expectation, limits with respect to any of the variables, or otherwise) about the minimum number of bins that collectively contain at least one ball of each color? I can't seem to find this problem in the literature, although it seems natural to me. How about the case where $N = nk$?

To clarify, I am interested in the question "how many bins do I have to look in to see one ball of every color", pursuant to Ben Barber's comment.

Answer 1

If $S$ is a set of bins, the probability that it contains at least one ball of every colour is $(1 - (1 - |S|/N)^n)^k$. There being $N \choose B$ such sets of cardinality $B$, the expected number of sets of cardinality $B$ that contain at least one ball of every colour is $E(B,N,n,k) = {N \choose B} (1 - (1 - B/N)^n)^k$. This is an upper bound on the probability that there is such a set.

EDIT: Here's a little case study. I tried $N = 1000$, $n = 10$, $k = 100$. Here $E(30,1000,10,100) \approx 0.2$ and $E(31,1000,10,100) \approx 109.7$. In 100 trials (using Cplex to solve the set-covering problem of finding the minimum number of bins to get balls of all colours) the minimum numbers of bins needed were as follows:

• $B = 33$ in 4 trials
• $B = 34$ in 16 trials
• $B = 35$ in 41 trials
• $B = 36$ in 32 trials
• $B = 37$ in 7 trials

Answer 2

Let $B$ be the minimum number of bins required. Since you asked about limits with respect to any of the variables, let's observe that the obvious inequality $$1\le B\le \min(k,N)$$ is completely sharp in the limit:

1. Fix $k$ and $N$ and let $n\rightarrow\infty$. Then the limiting distribution is $\mathbb P(B=1)=1$. (In fact, all individual bins will eventually cover all the colors.)
2. Fix $n$ and $k$ and let $N\rightarrow\infty$. Then the limiting distribution is $\mathbb P(B=k)=1$. (Each bin will be likely to contain at most one ball.)
3. Fix $n$ and $N$ and let $k\rightarrow\infty$. Then the limiting distribution is $\mathbb P(B=N)=1$. (Fixing any $N-1$ many bins, as we look through all the different colors, eventually (after a very long search) we will find a color such that all the $n$ many balls of that color are concentrated in the missing $N$th bin.)