Expected max load with $n$ balls in $n$ bins?

Question

If you throw $n$ balls into $n$ bins uniformly and independently at random, let $X$ be the number of balls in the bin with the largest number of balls in it.

Is there an elementary way to compute $\mathbb{E}(X)$?

This problem comes up when considering hashing in computer science, for example, or randomized load balancing.

EDIT. Having seen the current answer, if there is a simpler way to prove that $\mathbb{E}(X) =\Theta(\log{n}/\log{\log{n}})$ instead of an exact formula I would be happy with that.

Answer 1

The discussion in Section 4 of "Balls into Bins" - A Simple and Tight Analysis by Raab and Steger (found here) seems simple enough, as long as you're comfortable using moment method inequalities to bound probabilities of events.

Answer 2

More generally, suppose we have N balls and M bins. Section 9.4 of An Introduction to the Analysis of Algorithms, Second Edition by Robert Sedgewick and Philippe Flajolet shows that the average maximum occupancy is given by

$$\frac{N!}{M^N} [z^N] \sum_{k \ge 0} \left( e^{Mz} - \left( \sum_{0 \le j \le k} \frac{z^j}{j!} \right)^M \right) $$

where $[z^N]$ denotes the coefficient of $z^N$ when the expression following is expanded. The book also quotes an asymptotic approximation due to Gonnet:

$$\sim \frac{\ln N}{\ln \ln N} \text{ as } N, M \to \infty$$ in such a way that $N/M = \alpha$ with $\alpha$ constant.

Answer 3

For the maximum load the answer is $\Theta (\log n/ \log \log n)$.

Question: is the answer known for the 2-nd highest maximum load? what for the third? And so on.