5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Maybe this is already obvious, but you can think of this as repeating an "$n$ balls in $N$ bins" process $k$ times, with each process independent, and asking about the number of bins that are nonempty in all $k$ repetitions. Since the $k$ processes are independent, $\Pr[$a bin is nonempty $\forall k] = \Pr[$a bin is nonempty in an $n,N$ process$]^k$. $\endgroup$ – usul Jul 15 '14 at 18:40
  • $\begingroup$ That was my original interpretation, but Bjørn Kjos-Hanssen's answer deals with the sensible question "how many bins do I have to look in to see one ball of every colour?" Kellar, perhaps you could clarify this in the OP? $\endgroup$ – Ben Barber Jul 16 '14 at 9:20
2
$\begingroup$

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
$\endgroup$
2
$\begingroup$

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.)
$\endgroup$

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.