Consider the standard balls and bins process, where $m$ balls are thrown into $n$ bins, and consider the case where $m >> n$. Denote the load on bin $i$ by the RV $L_i$.

Given a set $S \subseteq [n]$ of size $k$ which does not contain the maximum and minimum load bins, and a threshold $t \in [m]$, a bin $j$ is pivotal to $S$, if $\sum_{i \in S}L_i < t \leq \sum_{i \in S \cup j}L_i$.

For a value $k \in [m-2]$, I want to bound the number of sets of size $k$ for which the maximum load bin is pivotal to, but not the minimum load bin, as a function of $t$.

For $t$ sufficiently bounded away from $\frac{km}{n}$, it is not hard to show that, with high probability, bin $i$ is pivotal to set $S$ iff bin $j \neq i$ is pivotal to $S$, as the difference in the loads of every two bins is $O(\sqrt{\frac{m\log n}{n}})$ (using the Chernoff+union bound)

However, for $t$ very close to $\frac{km}{n}$, the converse seems to be true (i.e., the maximum load bin is pivotal to many more sets $S$).

Now, from this, we know that if $n\log n << m < n\cdot polylog n$, then $L_{max} = \frac{m}{n} + \Theta (\sqrt{\frac{m\log n}{n}})$ w.h.p. By showing that w.h.p. $|L_i - \frac{m}{n}| = O(\sqrt{\frac{m\log n}{n}})$, for all $i=1,\ldots,n$ w.h.p. (using a Chernoff bound), we get that $L_{max} - L_{min} = \Theta(\sqrt{\frac{m\log n}{n}})$ with high probability.

Any ideas on how to lower-bound the number of sets?

The problem is that the loads of the remaining $n-2$ bins cannot be treated as another balls and bins process with $m-L_{min} - L_{max} = m - \frac{2m}{n} - \Theta(\sqrt{\frac{m\log n}{n}})$ balls, as their loads depend on $L_{min}$ and $L_{max}$.

  • 1
    $\begingroup$ related (not duplicate): cstheory.stackexchange.com/questions/6214/… $\endgroup$ Jun 3, 2013 at 16:54
  • $\begingroup$ Could you perhaps apply some distribution-independent bounds on the order statistics? (Given that you want the smallest load to be less than a certain expression, and the largest to be greater.) $\endgroup$ Jun 3, 2013 at 18:14
  • $\begingroup$ Well, I forgot to mention that we already know a tight bound on the difference between the maximal and minimal load, for reasonably large values of $m$). I edited my question accordingly. $\endgroup$
    – JoelO
    Jun 3, 2013 at 18:38


Your Answer

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

Browse other questions tagged or ask your own question.