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.

1more comment