14
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ You are asking in the wrong forum. $\endgroup$ – Gerald Edgar Mar 26 at 20:33
  • 2
    $\begingroup$ In my experience, this is not uniformly distributed. Most people have full heads of hair, except for those with certain patterns of baldness, so there will be peaks in the distribution. $\endgroup$ – Ben McKay Mar 26 at 21:41
  • 1
    $\begingroup$ @Gerald Should it be migrated to MSE? $\endgroup$ – Maximilian Janisch Mar 26 at 21:45
  • 1
    $\begingroup$ @Ben, would those peaks be Widow's peaks? en.wikipedia.org/wiki/Widow%27s_peak#Definition $\endgroup$ – Gerry Myerson Mar 26 at 23:52
  • 4
    $\begingroup$ @GeraldEdgar why? Looks ok here for me. $\endgroup$ – Fedor Petrov Mar 27 at 5:27
14
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ Exactly. To clarify, each $X_i$ is a ball that is thrown uniformly into bins $1,\dots,$ or $k$; we look at the number of balls in the max-loaded bin. $\endgroup$ – usul Mar 27 at 1:12
  • 1
    $\begingroup$ For completeness: The result is, loosely stated: If $n> k\ln(k)$, then the my expectation looks like $\frac{n}{k} +\Theta\left(\sqrt{\frac{n\ln(k)}k}\right)$ and if $n<\frac{k}{\ln(k)}$, it is of the form $\Theta\left(\frac{\ln k}{\ln(k/n)}\right)$. In my case, $n>k \ln(k)$, but $\frac{n}{k} +\Theta\left(\sqrt{\frac{n\ln(k)}k}\right)$ is not much better than $\frac nk$. $\endgroup$ – Maximilian Janisch Mar 29 at 10:40
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you, very interesting asymptotic behavior. I will not accept the answer yet though because I am hoping for a lower bound that is sharper in the case considered here 🙂. $\endgroup$ – Maximilian Janisch Mar 26 at 22:08

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.