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.

  • 1
    $\begingroup$ Can you edit your question to set up the problem in a self-contained way? What is "uniform hashing", and what is "the maximum value in uniform hashing"? What is $n$? Also: Are you really asking "given only the probability that something is smaller than $n/2$, can I recover what is the expectation?" Or are you asking "What is the expectation of this thing? I know the probability that it is smaller than $n/2$." I suggest being precise about what your question is. $\endgroup$
    – D.W.
    Jun 2, 2021 at 0:30
  • $\begingroup$ No, you cannot derive the expectation of a random variable from the probability that it is at most $x$ for a single value of $x$. $\endgroup$ Jun 2, 2021 at 5:57

1 Answer 1


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. $$

  • $\begingroup$ Super helpful, thanks. $\endgroup$
    – fox
    Jun 2, 2021 at 11:08
  • $\begingroup$ Thanks a lot! Do you have a reference for the integral of the Euler constant on [0,1] equal to the sinh expression? I read it on the Wikipedia article but no citation is provided either. $\endgroup$
    – fox
    Jun 2, 2021 at 13:02
  • $\begingroup$ I took it from Wikipedia as well. $\endgroup$ Jun 2, 2021 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.