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

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

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_{m \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$.

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

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.

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_{m \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$.