Skip to main content
1 of 6
TMM
  • 733
  • 10
  • 25

Expectation of Maximum of Uniform Multinomial Distribution

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

TMM
  • 733
  • 10
  • 25