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.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ What if there are 2 bins containing balls of the same colour? Just choose at random? $\endgroup$– Anthony QuasCommented Jun 17, 2016 at 16:32
-
$\begingroup$ Hi @AnthonyQuas. Yes, the bin is chosen randomly. $\endgroup$– lchenCommented Jun 17, 2016 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 ZbarskyCommented Jun 20, 2016 at 13:46
-
$\begingroup$ @SamZbarsky. I am interested in both cases. $\endgroup$– lchenCommented Jun 20, 2016 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 FischlerCommented Jun 20, 2016 at 19:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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).$
answered Jun 24, 2016 at 8:15
-
$\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$– lchenCommented Jun 24, 2016 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$ Commented Jun 24, 2016 at 17:54