Skip to main content
3 of 11
added 19 characters in body

A balls into bins problem with combinatorial capacity constraints

We are given $m$ balls and $n$ bins, with $m\gg n$. Each bin has the same capacity integer value $c$, i.e. it 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 an integer $n'\in [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 more than $\frac{c}{2}$ balls is equal to at least $n'$?

What if $n'=1$?