Expectation of Maximum of Uniform Multinomial Distribution

Question

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$.

Answer 1

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.

Answer 2

For every $n$ and $k$ we of course have $\mathbb{E}[m] \geq n/k$.

For the upper bound, Theorem 5.2 in this paper implies that for every $n$ and $k$ we have the upper bound $\mathbb{E}[m] \leq n/k + 2\sqrt{n}$. For fixed $k$ and large $n$, this is pretty close to sharp since, as you mentioned, already for $k = 2$ there is a lower bound of the form $\mathbb{E}[m] \geq n/2 + c \sqrt{n}$. Note that the lower-order term in the upper bound has no dependence at all on $k$; in particular, not the logarithmic dependence you'd get out of a naive use of tail bounds.

In fact, the cited theorem is actually showing an even stronger result: For a random 'word' $w$ of length $n$, formed by choosing each letter uniformly at random from $\{1, 2, \dots, k\}$, the expected length of the longest weakly increasing subsequence is at most $n/k + 2\sqrt{n}$. This immediately implies the abovementioned result, since the subsequence formed by taking all copies of the most frequent letter is weakly increasing, and its length is distributed precisely as $m$.