Take the 2-minute tour ×
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.

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|improve this question

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

1  
What have you tried? Where did you get stuck? –  Yuval Filmus Apr 18 at 23:25
2  
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 at 23:27
    
How to prove max bin load using chernoff bound ? –  user3367692 Apr 19 at 1:09

1 Answer 1

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|improve this answer
    
Can i get a more detailed solution ? –  user3367692 Apr 19 at 1:11
1  
Look at the paper. It has a very detailed solution. –  Yuval Filmus Apr 19 at 20:03

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