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$ – Suresh Venkat Jun 3 '13 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$ – András Salamon Jun 3 '13 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 '13 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.