# A balls into bins problem with combinatorial constraints

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'$$?)

• 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. May 4, 2019 at 12:52
• Yes, of course, thank you! May 4, 2019 at 12:55
• 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. May 6, 2019 at 7:05
• Does "an integer $n' \in [n]$" mean "a positive integer $n' \le n$" ? May 7, 2019 at 2:48
• 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$)? May 7, 2019 at 14:34

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...