Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have $n$ balls that I am distributing among $m$ bins. Each ball is independently and randomly placed in a bin. Let the bin containing the most balls contain $k$ balls. What is the expected value of $k$?

Currently, my intuition suggests that that

$$E(k) \approx c \frac{n}{m} \log(n)$$

Numerical simulations suggest that $c \approx 1/2$.

Is there a rigorous way to solve this problem?

The inspiration for this question was in finding the list with the longest access times in a hash table; it can also be seen as a variant of the birthday problem with $n$ people and $m$ possible birthdays, where one wants to find the maximum number of people that we expect to share a birthday.

share|improve this question
1  
this seems related.stackoverflow.com/questions/2611776/… the papers I have seen only have an upper bound on a more restricted problem. –  bobbym Mar 8 at 23:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.