2
$\begingroup$

Suppose I have $N$ bins and a set of balls with $m$ different colors, where there are $n_i$ balls of color $i$. I also have values $0 < p_i \leq 1$ for all colors $i$. I throw all $\sum_i n_i$ balls into bins uniformly at random and then I want the set of bins of smallest cardinality, such that I have at least $p_i n_i$ balls of each color $i$. Is the asymptotic behavior of (the distribution of the cardinality of the smallest set), in the limit as $N\to\infty$ and $n_i\to\infty$, well understood? Specifically, let's say that they all scale at the same rate so that $N = N_0 t$ and $n_i = n_i^0 t$ for fixed $N_0, n_i^0$ and we're letting $t\to\infty$.

$\endgroup$
6
  • 1
    $\begingroup$ Do you mean you want the distribution of the cardinality of that set? $\endgroup$ Aug 15, 2018 at 21:19
  • $\begingroup$ @BillBradley yes, exactly, edited. $\endgroup$ Aug 15, 2018 at 21:21
  • $\begingroup$ The problem does not seem very well specified. If $N$ goes to infinity very much more rapidly than the $n_i$ then it would be highly unlikely to have any bin with two balls in it so $\sum p_in_i$ would be needed. If the $n_i$ are very very much larger than $N$ then I supect that for any $q\gt \max{p_i}$ we have $k=q N$ are enough and that a large proportion of the $\binom{N}k$ picks work. $\endgroup$ Aug 16, 2018 at 3:22
  • $\begingroup$ @AaronMeyerowitz thanks, I clarified the notion of "going to infinity". $\endgroup$ Aug 16, 2018 at 7:17
  • $\begingroup$ Are you asking for all bins to have at least $p_in_i$ balls of each color $i$? Or are you asking for the smallest set that would have at least $p_in_i$ balls of each color $i$? $\endgroup$ Aug 16, 2018 at 7:42

1 Answer 1

2
$\begingroup$

Here's an informal pointer towards an answer. The number of bins required should grow linearly with $N$, with the rate given by an optimisation problem involving Poisson probabilities.

As $N\to\infty$ in your model, the distribution of balls in bins becomes very close to a collection of independent Poisson random variables: the answer to the question should be nearly the same as if each bin had a number of balls of colour $i$ with Poisson($\lambda_i$) distribution where $\lambda_i=n_i^0/N_0$, independently between different colours and different bins.

Let's say a bin has type $\mathbf{a}=(a_1, \dots, a_m)$ if it has $a_i$ balls of colour $i$ for $1\leq i\leq m$. In the Poisson model, the probability that a bin has type $\mathbf{a}$ is $$ p(\mathbf{a}):= \frac{\lambda_1^{a_1} e^{-\lambda_1}}{a_1!} \dots \frac{\lambda_m^{a_m} e^{-\lambda_m}}{a_m!}. $$ Consider the strategy of taking all bins whose type is in some given set $A\subset\mathbb{N}^m$. This strategy is likely to be "succesful" (in the sense of taking at least $p_i\lambda_i N$ balls of each colour) if for each $i=1,\dots,m$, $$ \sum_{\mathbf{a}\in A} a_i p(\mathbf{a}) > p_i \lambda_i. $$ Also, the number of bins taken will be roughly $Np(A)$ where $p(A):=\sum_{\mathbf{a}\in A} p(\mathbf{a})$.

This suggests the optimisation problem $$ p^*=\min_{\textstyle A: \sum_{\mathbf{a}\in A} a_i p(\mathbf{a}) > p_i\lambda_i \text{ for each }i} p(A). $$

The claim is that (to first order) the number of bins required behaves like $p^*N$. Clearly the optimising $A$ will be an increasing set (in the sense that if $\mathbf{a}\in A$ and $\mathbf{b}\geq\mathbf{a}$ componentwise, then also $\mathbf{b}\in A$).

It should be relatively straightforward to show that this is an upper bound, just by considering strategies of the form described above.

I'm confident that this is also a lower bound, but a rigorous proof of that might need more care since you need to justify that the random fluctuations are not helping you much in the long run. Some sort of concentration argument for the number of bins of each type could be the way to go.

EDITED: I think this is correct in spirit, but there is at least one subtlety that I missed, so that it (mostly) gives the wrong answer. Consider the case $m=1$. Then the strategies that I considered above are of the form "take every bin which contains at least $K$ balls", and I asserted that one of these would be optimal. However (except for cases where $\lambda_1$ and $p_1$ are carefully chosen) in fact there are better strategies of the form "take every bin that contains more than $K$ balls, and some proportion $\alpha$ of the bins that contain precisely $K$ balls". Extending to the case of multiple colours, we need to allow weights between $0$ and $1$ for types in the boundary of the set $A$ described above. Although the behaviour should be similar, it will make a more complicated optimisation problem than the one I originally claimed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.