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

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

<p>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$.</p>

<p>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)</p>

<p>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$).</p>

<p>Now, from <a href="http://www.ic.unicamp.br/~celio/peer2peer/math/balls-into-bins.pdf" rel="nofollow">this</a>, we know that if $n\log n &lt;&lt; m &lt; 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. </p>

<p>Any ideas on how to lower-bound the number of sets? </p>

<p>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}$.</p>

CC BY-SA 3.0
2013-06-03T16:54:09.207Z
related (not duplicate): http://cstheory.stackexchange.com/questions/6214/balls-and-bins-analysis-in-the-m-n-regime
Suresh Venkat
CC BY-SA 3.0
2013-06-03T18:14:37.517Z
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.)
András Salamon
CC BY-SA 3.0
2013-06-03T18:38:01.117Z
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.
JoelO
<reference-request><pr.probability>
The balls and bins model: bounding the marginal contributions in the m>>n regime
JoelO
# The balls and bins model: bounding the marginal contributions in the m>>n regime

(Asked by: username_0 on 2013-06-03)

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](http://www.ic.unicamp.br/~celio/peer2peer/math/balls-into-bins.pdf), 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}$.

**Tags:** reference-request, pr.probability

> **Comments:**
> **username_1**: related (not duplicate): http://cstheory.stackexchange.com/questions/6214/balls-and-bins-analysis-in-the-m-n-regime  
> **username_2**: 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.)  
> **username_0**: 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.  

---

## 0 answers

