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](https://mathoverflow.net/questions/259563/variance-of-load-in-maximally-loaded-bin-if-m-balls-are-thrown-into-n-bins) was unanswered



Concentration of the load of the maximally loaded bin ($m$ balls $n$ bins) with nonuniform bin probabilities
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](https://bowaggoner.com/blog/2017/01-06-collisions-in-bins/index.html) 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.


