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.
Best Answer
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 $$