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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.