How many people have the same exact number of hairs?

Question

Assume we look at $n\in\mathbb N$ people that can have anywhere between $1$ to $k\in\mathbb N$ hairs on their head.

Formally, I look at $n$ independent (in fact, this is not really true in real life because of inheritance etc., but bear with me) uniformly (might also not be true in real life) distributed random variables $$X_1, X_2, \dots, X_n \sim \text{Uniform}(\{1, 2, 3, \dots, k\}).$$

---

My question: How many people am I expected to be able to find that have the same number of hairs? Formally, what is, where $\lvert\cdot\rvert$ denotes cardinality,

$$\mathsf E\left(\max_{i\in\{1, 2, \dots, k\}} \lvert\{j\in\{1,2,\dots, n\}: X_j = i\}\rvert\right).$$

---

Remark. According to the Pigeonhole Principle, we have $$\max_{i\in\{1, 2, \dots, k\}} \lvert\{j\in\{1,2,\dots, n\}: X_j = i\}\rvert\geq\frac nk.$$

For example, if we assume that there are $n=82$ million people living in Germany, and everyone has at most $k=1$ million hairs, then we can always find at least $82$ people that have the exact same number of hair. (Note that the Pigeonhole Principle doesn't need the uniform distribution nor the independence of the $X_j$ !)

---

Note that the random variables $\lvert\{j\in\{1,2,\dots, n\}: X_j = i\}\rvert$ for $i\in\{1,2,\dots, k\}$ are not independent.

Answer 1

This question has been studied extensively in the computer science literature under the name "balls in bins"; see [1] which gives quite tight bounds in Theorem 1, page 161 and also describes prior work before 1999.

[1] Raab, Martin, and Angelika Steger. "“Balls into bins”—A simple and tight analysis." In International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 159-170. Springer, Berlin, Heidelberg, 1998. Available on page 159 of https://link.springer.com/content/pdf/10.1007%2F3-540-49543-6.pdf

Answer 2

We need to estimate $EN$, where \begin{equation} N:=\max_{j\in[k]}N_j,\quad N_j:=\sum_{i\in[n]}1(X_i=j), \end{equation} the $X_i$'s are iid uniform in $[k]:=\{1,\dots,k\}$.

We have \begin{equation} EN=\int_0^\infty dt\,P(N\ge t) \end{equation} and \begin{equation} P(N\ge t)\le\sum_{j\in[k]}P(N_j\ge t)=kP(N_1\ge t)\le ke^{-2(t-np)^2/n} \end{equation} for $t\ge np$ and $p:=1/k$, by Hoeffding's inequality. Also, $P(N\ge t)\le1$. So, for \begin{equation} t_*:=np+\sqrt{\frac n2\ln k}, \end{equation} \begin{equation} EN\le t_*+I, \end{equation} where \begin{align*} I&:=k\int_{t_*}^\infty dt\,e^{-2(t-np)^2/n} \\ &=\frac k2\,\sqrt n\,\int_{\sqrt{2\ln k}}^\infty dz\,e^{-z^2/2} \\ &<\frac k2\,\sqrt n\,\int_{\sqrt{2\ln k}}^\infty dz\,\frac z{\sqrt{2\ln k}}\,e^{-z^2/2} \\ &=\frac k2\sqrt n\, e^{-\ln k} \frac1{\sqrt{2\ln k}} =\frac12\sqrt{\frac n{2\ln k}}. \end{align*}

So, \begin{equation} EN\le U_{n,k}:=\frac nk+\sqrt{\frac n2\,\ln k}+\frac12\sqrt{\frac n{2\ln k}}. \end{equation} On the other hand, \begin{equation} EN\ge L_{n,k}:=EN_1=\frac nk. \end{equation} We see that the upper and lower bounds $U_{n,k}$ and $L_{n,k}$ are asymptotic to each other if $k^2\ln k=o(n)$.

This does not seem to work that well when, say, $n=82\times10^6$ and $k=10^6$ or even $k=10^5$, which latter seems to be closer to the usual number of human hairs on the head.

However, as noted in the comment by Ben McKay, the actual distribution of the number of hairs is far from uniform -- which may make an effective dimension of the random vector $(N_1,\dots,N_k)$ much less than $k$, and which may then bring the upper and lower bounds closer to each other.