6
$\begingroup$

We have $n$ balls, each belonging to a group (e.g, color). There are $g$ groups ($g$ may be large but $g=o(n)$). We sequentially put the balls into $m$ bins in the following way: for each ball, we randomly choose $k$ bins; if there is a bin containing balls of the same group, we put the ball into the bin, otherwise we put the ball into the leftmost empty bin; if we cannot find an appropriate bin for the ball, there is a insertion failure. The question is to find at least how many bins (i.e., the value of $m$) are required so as to achieve a small insertion failure probability.

$\endgroup$
  • $\begingroup$ What if there are 2 bins containing balls of the same colour? Just choose at random? $\endgroup$ – Anthony Quas Jun 17 '16 at 16:32
  • $\begingroup$ Hi @AnthonyQuas. Yes, the bin is chosen randomly. $\endgroup$ – lchen Jun 17 '16 at 16:33
  • $\begingroup$ Is the coloring of the balls random? Also, are you thinking of $k\ll n$, or is $k$ arbitrary? $\endgroup$ – Sam Zbarsky Jun 20 '16 at 13:46
  • $\begingroup$ @SamZbarsky. I am interested in both cases. $\endgroup$ – lchen Jun 20 '16 at 14:33
  • 1
    $\begingroup$ @AnthonyQuas: If there are 2 bins containing balls of the same colour, but you only care about the probability of an insertion failure, then it does not matter at all whether you place the ball in one bin or the other, or for that matter if we discard the ball completely. $\endgroup$ – Mark Fischler Jun 20 '16 at 19:55
1
$\begingroup$

The problem seems too vague. I don't have sources to draw from but here are some speculations:

I will assume that the groups are the same size. Also that $g$ is fixed and $n$ goes to infinity. And also that the bins that have colors are equally distributed among the colors (or close enough so that the discrepancy doesn't matter).

In the event that all $m$ bins are colored ahead of time, $g\ln{n}$ seems about right in the sense that if $k=g(\ln{n}+c)$ then the expected number of insertion failures is very close to $e^{-c}.$ That estimate is based on the assumption that the colors of the bins selected are independent. That means $m$ much bigger than $g$. However, if that is not the case, it lowers expected number of failures.

But to get from $m$ empty bins to all or almost all colored might take some time. My rough (and suspect) calculation for $g=2$ is on the order of $2^{mk}.$ I suppose that for $g=2$ and $m$ fixed, as $n$ goes to infinity this would became paltry compared to $2{\ln{n}}.$

Of course $k=m$ is surely enough and if we hold $g$ and $m$ fixed and let $n$ go to infinity then eventually $g\ln{n} \gt m.$ Actually $k=\frac{g-1}{g}m+1$ is enough if their are exactly $\frac{m}{g}$ bins of each color.

All this is pretty sketchy. However if it is generally on the right track then perhaps it is possible to extend it to cases such as $m=\ln^2(n)=\ln(\ln{n})$ and $g=\ln^4(n).$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you Aaron. A clarification: bins are not colored. Once the first ball is thrown into a bin, the bin can only take balls of the same color. I seek the values of $m$ and $k$ so that the insertion failure is small. Ideally I want small $k$ (e.g., $\ln g$). $\endgroup$ – lchen Jun 24 '16 at 13:58
  • $\begingroup$ True, but once a bin takes a ball I give it the color of that ball. Errors are possible only once one starts sometimes getting bins which are all colored. If k<g you are likely to get insertion failures pretty quickly . $m=k=g$ would work great. $\endgroup$ – Aaron Meyerowitz Jun 24 '16 at 17:54

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.