Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

closed as unclear what you're asking by D.W., Wandering Logic, tanmoy, David Richerby, vonbrand Apr 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.

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

share|cite|improve this answer
Can i get a more detailed solution ? – user3367692 Apr 19 '14 at 1:11
Look at the paper. It has a very detailed solution. – Yuval Filmus Apr 19 '14 at 20:03

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