Variance of load in maximally loaded bin, if $m$ balls are thrown into $n$ bins

Question

In the paper "Balls and bins a simple and tight analysis" by Raab and Steger, available here strong upper and lower bounds are proved about the number $M$ of balls in a maximally loaded bin when $m$ balls are independently and uniformly thrown into $n$ bins.

For example, if $$n \log n \ll m \leq n \cdot polylog (n) $$ then $$Pr[M >k_{\alpha}]= o(1),\qquad~~ if ~~\alpha> 1$$ and $$Pr[M >k_{\alpha}]=1−o(1),~\qquad~ if ~~0< \alpha<1,$$ where $$k_{\alpha}=\frac{m}{n}+\alpha \sqrt{ 2\frac{m}{n}~ \log n}.$$

I am interested in estimates of the variance of $M.$

Also, I know that $M$'s expectation is exactly of order

$$\log n/\log \log n$$ if $m=n,$ but not in general.

Answer 1

Theorem 4.4 in Devroye's book On Bucket Algorithms answers this question. His $n,m$ are opposite to those in the question and uniformity is not assumed. Subject to some technical conditions on a nonlinear, nonnegative, convex fumction $g(x)$ on $[0,\infty)$ which are satisfied here, with $g(x)=x^2,$ his result can be written as $$ \mathbb{E}(g(M))=(1+o(1))g(\log n/\log\log n) $$ which yields by subtraction $$ \textrm{Var}(M)=f(n,m) \times \left(\frac{\log n}{\log \log n}\right)^2 $$ where $$ f(n,m)\sim \frac{n e^{-u \log\left(un/emq\right)}e^{-mq/n}}{\log\left(un/emq\right)} $$ where $u=(1+\varepsilon) \log n/\log\log n$, and $q=n\max_i \{p_i\}=1$ here which yields $$ f(n,m)\sim \frac{n e^{-u \log\left(un/em\right)}e^{-m/n}}{\log\left(un/em\right)}. $$