Expected max load with $m$ balls into $n$ bins Suppose that we randomly drop n3/2 balls into n bins. Give an upper bound on the expectation of the maximum number of balls in any bin.
I have seen somewhat similar questions but no good answer for this kind of problem. First, we know that the expected number of balls in any bin is n1/2. Then, I think we need to use Chernoff bounds but that's the part I am struggling with. Usually, we have to set a δ but I don't know equal to what.
Thanks for your help.
 A: Let $X_i$ be the # of balls in the $i$th bin and $X = \max\{X_1, X_2, \cdots, X_n\}$. We have
$$
\mathsf{E}(X) = \sum_{i \geq 1} \Pr(X \geq i) \leq \sum_{i > 2n^{1/2} + 9\ln n} \Pr(X \geq i) + 2n^{1/2} + 9\ln n
$$
and for $i > 2n^{1/2} + 9\ln n$, 
\begin{align}
\Pr(X \geq i) &= \Pr(X_1 \geq i\ \lor\ X_2 \geq i\ \lor\ \cdots\ \lor\ X_n \geq i) \\
&\leq \sum_{j = 1}^n \Pr(X_j \geq i) \\
&\leq \sum_{j=1}^n \mathsf{exp}\left( - \frac{i - n^{1/2}}{3}\right) \\
&\leq \sum_{j=1}^n \mathsf{exp}\left(-3\ln n\right) \\
&= \frac{1}{n^2}
\end{align}
where 


*

*$X_j \sim \mathsf{Binomial}~(n^{3/2}, \frac{1}{n})$ and $\mathsf{E}(X_j) = \sqrt{n}$;

*the first inequality uses the union bound;

*the second inequality uses a loose form of Chernoff bound:
$$
\Pr(X \geq (1 + \delta)\mu) \leq \mathsf{exp}(-\frac{\delta\mu}{3}) \quad\text{for}\ \delta > 1
$$
Therefore,
$$
\sum_{i > 2n^{1/2} + 9\ln n} \Pr(X \geq i) \leq n^{3/2} \cdot \frac{1}{n^2} = \frac{1}{\sqrt{n}}
$$
implying an upper bound
$$
\mathsf{E}(X) \leq 2\sqrt{n} + \frac{1}{\sqrt{n}} + 9 \ln n
$$
