Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
long shot question but I am super stuck.
Donald Knuth has proven (p. 8 here, equation 12) that the probability that the maximum value in uniform hashing is smaller than $n/2$ is equal to 0.288. I wonder if with this information I can recover what is the expectation of the maximum value? Simulation strongly suggest 0.63 n but I would like to understand what I am doing.
The probability that the maximum rank $r_{\max}$ is at most $m$ is $$ (1 - q_{1m}) \cdots (1 - q_{nm}), $$ where $$ q_{km} = \binom{k-1}{m} \bigg/ \binom{n}{m}. $$ Therefore $$ \mathbb{E}[r_{\max}] = \sum_{m=1}^n \Pr[r_{\max} \geq m] = \sum_{m=1}^n (1 - \Pr[r_{\max} \leq m-1]) = \\ 1 + \sum_{m=1}^{n-1} \left[1 - \prod_{k=1}^n \left(1 - \binom{k-1}{m}\bigg/\binom{n}{m}\right)\right]. $$ When $m = (1-\alpha) n$, the $m$'th summand is roughly equal to $$ 1 - \prod_{i=1}^\infty (1-\alpha^i) = 1 - \phi(\alpha), $$ where $\phi(x)$ is the Euler function, and so $$ \frac{\mathbb{E}[r_{\max}]}{n} \approx 1 - \int_0^1 \phi(x) \, dx = 1 - \frac{8\sqrt{3/23}\pi\sinh(\sqrt{23}\pi/6)}{2\cosh(\sqrt{23}\pi/3)-1} \approx 0.631587464068566. $$
