# Concentration of the load of the maximally loaded bin ($m$ balls $n$ bins) with nonuniform bin probabilities

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

## 1 Answer

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.

• 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? Feb 21, 2019 at 20:44