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.
Best Answer
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.