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

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.

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)}.$$