# 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.

• Let $Y$ be the maximum number of balls in any bin. Chernoff like arguments give you $P(Y \ge k) \le f(k)$ for some $f$. Since $Y\ge 0$ surely, you can now use $\mathbb{E}[Y] = \sum_{k \ge 1} P(Y \ge k) \le \sum_{k\ge 1} f(k)$ for an upper bound on the expectation. Mar 20, 2017 at 2:50
• Thanks for your answer, I follow what you are doing. My question is how do we find that f(k) ? @stochasticboy321 Mar 20, 2017 at 2:56

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$$

• Very neat thank you ! Mar 21, 2017 at 2:35
• Sorry but I don't understand where $2n^{1/2}+9 ln n$ comes from
– Rob
Mar 23, 2017 at 18:24
• @Rob It is a value selected such that when we apply the Chernoff bound, the formula would not be too tedious. Mar 24, 2017 at 1:47