# Expected maximum bin load, for balls in bins with equal number of balls and bins [closed]

Suppose we have $n$ balls and $n$ bins. We put the balls into the bins randomly. If we count the maximum number of balls in any bin, the expected value of this is $\Theta(\ln n/\ln\ln n)$. How can we derive this fact? Are Chernoff bounds helpful?

-

## closed as unclear what you're asking by D.W., Wandering Logic, tanmoy, David Richerby, vonbrandApr 23 '14 at 16:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

What have you tried? Where did you get stuck? –  Yuval Filmus Apr 18 '14 at 23:25
It is not true that the maximum number of balls that can go into a bin is $\log n/\log\log n$. The maximum number of balls that can go into a bin is $n$. The expected maximum bin load is $\Theta(\log n/\log\log n)$. –  Yuval Filmus Apr 18 '14 at 23:27
How to prove max bin load using chernoff bound ? –  user3367692 Apr 19 '14 at 1:09

The correct approximation here is Poisson. The occupancy of each bin is distributed roughly $P(1)$ (Poisson with expectation $1$), and tail bounds for Poisson random variables show that with probability $1-1/n^2$ (say), the variable is at most $O(\log n/\log\log n)$. A union bound shows that with high probability, all bins contain at most $O(\log n/\log\log n)$ balls.
A good resource on balls and bins is "Balls into Bins" – A Simple and Tight Analysis by Raab and Steger. They use elementary methods to a range of $m$ (balls) and $n$ (bins) that covers the classical case $m = n$.