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

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.

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.

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.

Would you like to know the equation(s) for the Maximum Load given a set number of bins and any number of balls? You are at the right place. After examining the data and working back from there, these results are pretty straightforward, except for the not-so-obvious UAF.

Definitions: T: tosses of balls, U: urns or bins, EM(T,U): Expected Maximum Load for T random tosses into U urns

Probabilistically, there is a single exact expected value for the Maximum Load for a set number of tosses and urns. For example, EM(200,2), the expected maximum load for 200 tosses into 2 urns, is 105.6348479009 (rounded).

A nice equation can be seen for the expected maximum load when U=2 and T is sufficiently large:

EM(T,2)= T/2 + sqrt( T / (2*π) ) as T → ∞

What if there are 3 urns?

Because the maximum urn count can be as high as T, but the minimum urn can only be as low as zero, there is an unscalable adjustment factor (UAF) of (0.0918881…) / 2 for U=3.

EM(T,3)= T/3 + (3/2) * sqrt( T / (3*π) ) + 0.04594407 as T → ∞

EM(1800,3) = 620.7748847701196 which compares favorably with the equation's output of 620.77559304. (The extra load is 99.996% of the equation’s upper limit at T/U=600.)

To determine EM(T,U), there are definitive increasing constant multipliers for every U. Wonderful. Since EM(T,U) resides at the 50th percentile, my guess is that there may be exact multipliers for each of the other p values, too.

Estimates have been determined for a few of these constants via simulation where U > 3 using a stellar PRNG. Notice that EM(T,U) is scalable by the square root of the expected urn count, T/U.

For 4 urns, where T/U is sufficiently large, the equation is approximately EM(T,4)= T/4 + 1.029 * sqrt( T/4 ) + 0.09

For 13 urns, where T/U is sufficiently large, the equation is approximately EM(T,13)= T/13 + 1.667 * sqrt( T/13 ) + 0.35

For 100 urns, where T/U is sufficiently large, the equation is approximately EM(T,100)= T/100 + 2.51 * sqrt( T/100 ) + 0.9

For 1000 urns, where T/U is sufficiently large, the equation is approximately EM(T,1000)= T/1000 + 3.24 * sqrt( T/1000 ) + 1.6

How many urns / bins are you working with?