maximum load of balls and bins when $m \neq n$

Question

When $m=n$, there is a classical result such that the maximum load would be $\theta(\frac{\ln n}{\ln \ln n})$. However, what happens when $m \neq n$? Say if $m = n^{0.5}$ or $m=n^{0.9}$, how can we analyze the max load in this case?

$m$ is the number of balls and $n$ is number of bins

Answer 1

The general asymptotic formula for any $m \leq n \log n$ is $$ \Theta \left( \frac{\log n}{\log \left( \frac{4n}{m} \cdot \log n\right)}\right), $$ and for any $m \geq n \log n$ it is $$ \frac{m}{n} + \Theta\left(\sqrt{\frac{m}{n} \cdot \log n} \right). $$ Both of these hold in expectation and with probability at least $1 - n^{-\Omega(1)}$.

For the cases $m = n^{0.5}$ and $m = n^{0.9}$, that you mentioned, the maximum load is $\Theta(1)$ using the first formula.

For more information, see:

• These notes by Artur Czumaj
• “Balls into Bins” — A Simple and Tight Analysis by Raab and Steger (1999)
• The books Probability and Computing by Mitzenmacher and Upfal (2017) and Lecture notes on bucket algorithms by Luc Devroye (1986)