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.



How many people have the same exact number of hairs?
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>


