Suppose we have a uniform multinomial distribution with $k$ buckets, i.e. we put $n$ items uniformly at random in $k$ buckets leading to $n_1, \dots, n_k$ items in each bucket respectively. Let $m = \max \{n_1, \dots, n_k\}$. Can we say anything about $\mathbb{E}(m)$, and in particular, its asymptotics as $n \to \infty$?
For the case $k = 2$, this is equivalent to looking at the distance from the origin after $n$ steps in a $1$-dimensional random walk. Then $n_1$ counts the number of steps in the positive direction, $n_2$ counts the number of steps in the negative direction, and $2m – n = m – (n – m) = |n_1 – n_2|$ considers the distance from the origin after $n$ steps in a simple $1$-dimensional random walk. A derivation at for instance MathWorld shows that in this case, $\mathbb{E}|n_1 – n_2| \sim \sqrt{2n/\pi}$ leading to exact asymptotics for $\mathbb{E}(m)$.
I am now interested in the case $k > 2$ and large $n$, for which I could not find an answer. Anything would be appreciated, e.g. specific results for $k = 3$ or any other value of $k$, or even results for the regime $k = n \to \infty$ would be great.
Slightly related is this question, which is about getting bounds on the tails of the distribution of the maximum of a multinomial distribution. But I am interested in (exact) asymptotics for the mean, so such approximations don't seem very useful.
Edit: As noted in Waldemar's answer below, the "balls into bins"-problem is closely related to this question. This indeed shows how $\lim_{n \to \infty} \mathbb{E}(m)$ roughly behaves in terms of $k$. However, the classic paper of Raab and Steger only gives bounds on the tails of the distribution of the maximum, and does not tell you what the mean is. In particular, using those bounds alone seems to be insufficient, as one would not be able to derive the $\sqrt{2n/\pi}$ for $k = 2$ then.
So I'm still looking for further pointers that would help me get a better understanding of the exact value of $\mathbb{E}(m)$ for smaller $k$ and large $m$.
Best Answer
Usul is quite right that your problem is of a "balls into bins" type.
For the case $n\gg k$ we get $\Theta \left ( \frac{n}{k} \right )$. $\frac{n}{k}$ is of course the mean load of the bucket (bin). The intuition is that the asymmetry between the loads of different buckets (bins) tends to zero as the number of items (balls) tends to infinity.
For the case $k=n$ we get $\Theta (\frac{log\: k}{log\: log\: k})$ see e.g. here
The formula for the exact value can be find in this paper.