Skip to main content
7 of 11
deleted 1 character in body

A balls into bins problem with combinatorial capacity constraints

We are given $m$ balls and $n$ bins, with $m>n\log 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 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'$?)