Consider $n$ color balls. We throw them as follows. For a given ball $i$, randomly choose $k$ bins; create $k$ 'copies' of the ball (i.e., of the same color of the ball $i$); throw a 'copy ball' into each of the chosen $k$ bins. Define the color load of a bin as the number of colors of the balls thrown into the bin, e.g., if the bin has 2 red balls and 3 blue balls, then its color load is 2. The question I ask is: what is the maximum expected color load (in order of magnitude)? There are $m$ colors in total.
4
-
$\begingroup$ @domotorp $n$ is the number of balls and $m$ the number of colors $\endgroup$– lchenCommented Nov 15, 2016 at 13:15
-
$\begingroup$ there are $n$ bins $\endgroup$– lchenCommented Nov 15, 2016 at 14:01
-
1$\begingroup$ What is the distribution of colors among the balls? $\endgroup$– Michael BiroCommented Nov 15, 2016 at 20:49
-
$\begingroup$ @MichaelBiro We can consider the case where there are $n/m$ balls for each color. A further interesting question is to consider the setting below. For a given ball $i$, randomly choose $k+k'$ bins; create k 'copies' of the ball (i.e., of the same color of the ball i); choose $k$ less color-loaded bins among the $k+k'$ chosen bins; throw a 'copy ball' into each of the chosen k bins. The question is again: what is the maximum expected color load ? $\endgroup$– lchenCommented Nov 16, 2016 at 9:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let me see if I understand you right by repraphsing the question.
- We have $n$ bins and $m$ colors.
- For each color, $j$, we independently repeat the following process $\lambda$ times:
- Pick $k$ bins uniformly without replacement, and put a ball of color $j$ in each of these bins.
After we've done this, we will have placed a total of $m \lambda k$ balls. Let $X_1, X_2, \ldots , X_n$ denote how many different colors of balls are in each bin. You want to estimate $\max_{i} X_i$.
(And you say in a comment we can take $\lambda = n/m$)
If my understanding of the problem is incorrect, let me know. Below I solve the problem I just described.
Consider the first bin. Let $Y_1, Y_2, \ldots , Y_m$ denote the indicator random variables that the first bin receives a ball of color $j$ for $j=1, 2, \ldots , m$. Then $X_1$ (the number of different colors) is simply $Y_1 + Y_2 + \cdots + Y_m$. Moreover, each $Y_j$ is independent of the others, and the $Y_j$ are identically distributed. Thus $X_1$ is just a binomial random variable with mean $mp$, where $$ p = 1 - \left(1 - \frac{k}{n} \right)^{\lambda}.$$
So each $X_i$ is very easy to analyze. If you want the order statistics, then just assume that the $X_i$ are independent (which is reasonable for large values of the parameters). Then you are just trying to estimate the maximum of a collection of independent identically distributed binomials. See for example this link, but the fastest way to estimate this would be to find for which value of $t$ we expect $\#\{i\ : \ X_i > t\} \approx 1$.
(Depending on the range of parameters you're interested in, the approximation $p \approx k \lambda / n$ is likely reasonable. Then just estimate for which $t$ we have $\mathbb{P}(X_1 > t) \approx 1/n$, and $t$ will be a good approximation to your answer.)
