1
$\begingroup$

There is a common argument used when investigating the concentration of the maximally loaded bin (say $X$ is the maximum load) when $m$ balls are thrown into $n$ bins under the uniform distribution. I give the argument for $m=n,$ showing that $X$ is approximately $\ln n/\ln \ln n$ with high probability. Using the union bound, and letting $X_i$ be the number of balls in the $i^{th}$ bin $$ \mathbb{P}(X_i=k)=\binom{n}{k}\left(\frac{1}{n}\right)^k \left(1-\frac{1}{n}\right)^{n-k}\leq \binom{n}{k} \left(\frac{1}{n}\right)^k\leq \left(\frac{ne}{k}\right)^k\left(\frac{1}{n}\right)^k= \left(\frac{e}{k}\right)^k $$ yielding $$ \mathbb{P}(X_i\geq k)\leq \sum_{j=k}^n \left(\frac{e}{j}\right)^j \leq \left(\frac{e}{k}\right)^k \left(1+\frac{e}{k}+\frac{e^2}{k^2}+\cdots\right). $$ Now let $k^{\ast}=\lceil e \ln n/\ln\ln n\rceil,$ giving $$ \mathbb{P}(X_i\geq k)\leq \left(\frac{e}{k^{\ast}}\right)^{k^{\ast}} \left[\frac{1}{1-e/k^{\ast}}\right]\leq n^{-2}, $$ and using the union bound, since there are $n$ bins $$ \mathbb{P}\left(\bigcup_{i=1}^n X_i\geq k\right)\leq \frac{1}{n},\quad (1) $$ giving the concentration. What if we now have $p=(p_1,\ldots,p_n)$ with $p_i$ the probability of each ball falling into bin $i$, in an independent manner.

As far as I can tell (sort the bins so $p_1\geq p_2\geq \cdots\geq p_1>0$) as long as the maximum probability obeys $p_1\leq \frac{\ln n}{n}$, a version of this argument works.

What about distributions with larger $p_1$? What can we say? Say we allow the quantity on the RHS of (1) to be $\frac{1}{\sqrt{n}}$, for example.

I am most interested in $m=n,$ or slightly larger $m$ say $m=n (\log n)^a.$

I suppose for $p_1$ large enough wrt the other probabilities its load will highly likely be the maximum. So a kind of convex combination argument is needed...

Edit: As far as lower bounds for the uniform case, it can be addressed in a number of ways, including Lemma 5.12 from Mitzenmacher and Upfal's book Probability and Computing which shows that the maximum load is at least $$\ln n/\ln \ln n$$ with probability at least $1-(1/n)$ for $n$ large.

Remark: This related question here was unanswered

$\endgroup$
1
$\begingroup$

If you only want upper bounds, there is a nice approach based on collisions. (Proving that the max-loaded bin is not too small w.h.p. seems to need completely different techniques.)

Define a $k$-way collision to be a case of $k$ different balls that land in the same bin. For example, if they all land in the same bin, there are ${m \choose k}$ total $k$-way collisions.

Let $C_k$ be a random variable for the number of $k$-way collisions. The probability that a fixed set of $k$ balls collides is $\sum_{i=1}^n p_i^k = \|p\|_k^k$. Therefore $\mathbb{E} C_k = {m \choose k} \|p\|_k^k$.

Now to upper-bound the chance that the max-loaded bin has $\geq k$ balls, we can use Markov's inequality:

\begin{align*} \Pr[\text{exists a $\geq k$ loaded bin}] &= \Pr[C_k \geq 1] \\ &\leq \mathbb{E} C_k \\ &= {m \choose k} \|p\|_k^k \\ &\leq \left(\frac{m e}{k}\right)^k \|p\|_k^k \end{align*} The amazing thing is that this tends to give quite tight/strong asymptotics (I think of it as $C_k$ is already "Chernoff-ized" in a sense, e.g. $k$ is in the exponent here). I have a blog post about this but don't know of another reference.

With an upper-bound on the heaviest bin, the worst case is $1/p_1$ bins of probability $p_1$, so $\|p\|_k^k \leq p_1^{k-1}$. \begin{align*} &\leq \frac{1}{p_1} \left(\frac{m p_1 e}{k}\right)^k \\ &= \exp\left(k \log \left(m p_1 e \right) - k \log(k) + \log\left(\frac{1}{p_1}\right) \right) \end{align*} For example, to recover the well-known result, if you plug in $m = n$ and $p_1 = \frac{1}{n}$, you get $$ \exp\left(-(k-1)\log(k) + \log(n)\right) $$ which is $O(1)$ for $k \approx \frac{\ln(n)}{\ln \ln(n)}$ and exponentially decreasing in $k$ thereafter.

$\endgroup$
  • $\begingroup$ Thanks. Amazingly I had just found your blogpost and glanced over it. When I came back to mathoverflow, I saw your answer. Whats the likelihood of that collision? $\endgroup$ – kodlu Feb 21 '19 at 20:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.