4
$\begingroup$

We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into one bin selected independently and uniformly at random from the set of non-full bins remained (i.e. the ones containing less than $c$ balls).

Question: Given a positive integer $n'\le n$, what is the minimum number of balls that it is necessary to place into bins in such a way that the expected number of bins containing at least $\frac{c}{2}$ balls is equal to at least $n'$?

(What about the minimum number of balls for having that the expected number of full bins is equal to at least $n'$?)

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Maybe you want to write "at least $n'$" at the end, since the expectation might never be exactly $n'$. It will step up in the rational numbers, hitting an integer only sometimes. $\endgroup$
    – Brendan McKay
    May 4, 2019 at 12:52
  • $\begingroup$ Yes, of course, thank you! $\endgroup$
    – Penelope Benenati
    May 4, 2019 at 12:55
  • 1
    $\begingroup$ I am not sure what to do with the condition $m > n\log n$ (especially, what if $\log n>c$?). Otherwise, if $m/n$ and $c$ are kept constant with $n\to\infty$, one can probably construct a hydrodynamic limit. $\endgroup$
    – N. Gast
    May 6, 2019 at 7:05
  • 1
    $\begingroup$ Does "an integer $n' \in [n]$" mean "a positive integer $n' \le n$" ? $\endgroup$
    – Brian Hopkins
    May 7, 2019 at 2:48
  • 1
    $\begingroup$ Since m doesn't appear in the actual question, the fact that $m\gg n$ is not very helpful. Can we replace it with $nc \gg n$ (i.e. $c\gg 1$)? $\endgroup$
    – Yoav Kallus
    May 7, 2019 at 14:34

1 Answer 1

Reset to default
-1
$\begingroup$

(Not a full answer, but too long for a comment.)

This is more or less the generalized coupon collector problem. The only thing is that in your model, you stop collecting coupons of types that you already have $c$ of. You could probably convert it exactly into the coupon collector problem by doing the following...

Coupling model: First drop balls into bins uniformly at random, and stop after a while (this is classical coupon collector). When you stop, then remove balls from all the bins that have too many until no bins are over capacity. This has the same distribution as your model, and it sounds easier to analyze.

In the classical model, the number of bins with enough balls (if there's no issue about capacity) is very well understood. And the number of "excess balls" that you'd have to throw away to go from the classical coupon-collector model to your setting is hopefully something you can also control sufficiently well.

So hopefully that coupling will give you whatever you might want.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your comment, but as you wrote, this is not an answer. Anyway, it is not clear what you formally mean by removing balls from bins, sorry. $\endgroup$
    – Penelope Benenati
    May 10, 2019 at 22:25
  • $\begingroup$ Ah yes. Thanks for asking (my post wasn’t very clear). I mean the following: first add balls in bins without worrying about capacities, and stop as soon as n’ bins have c/2 balls (this is classical coupon collector). For each bin, let B_i denote the number of balls in bin i when you stop. Then your question is to understand sum_i min(c, B_i) [which is the number of balls dropped in your model until n’ bins have at least c/2 balls]. I’m not sure if I’m being clear yet (and I don’t know if it’s even particularly helpful to view it this way). Let me know. :-) $\endgroup$
    – Pat Devlin
    May 11, 2019 at 0:18

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.