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

  • $\begingroup$ Dear @TMM: The visibility of this question would likely increase if you were to add the top level tag 'pr.probability'. In general, it is advised that one always add a top level tag (the ones with two letter codes in front) to a question, whenever possible. See also: meta.mathoverflow.net/questions/1075/… $\endgroup$ Oct 30 '13 at 15:20
  • $\begingroup$ @Ricardo: Thanks for the suggestion. I've added pr.probability. $\endgroup$
    – TMM
    Oct 30 '13 at 15:29
  • 2
    $\begingroup$ You may find answers by searching the phrase "balls into bins". $\endgroup$
    – usul
    Oct 31 '13 at 1:25
  • $\begingroup$ Has anyone tried to approximate the multinomial distribution with a multivariate normal distribution? I am also having to solve a similar problem and trying this approach with my limited knowledge in probability theory so hopefully, someone with more experience might elaborate as this could provide the approximation the OP is looking for. $\endgroup$
    – Alex
    Jan 18 '17 at 9:45

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.

  • $\begingroup$ Thanks, I totally forgot about the "balls into bins" problem, and that it applies here. Still I'm not sure how precise this is. In the case $k = 2$ shouldn't these bounds also give you the $\sqrt{2n/\pi}$ then? Or are these bounds not tight enough for that? $\endgroup$
    – TMM
    Nov 1 '13 at 10:31

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.