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

Question

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

Answer 1

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.