# Obtaining an expectation in uniform hashing

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.

• 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.
– D.W.
Jun 2, 2021 at 0:30
• 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$. Jun 2, 2021 at 5:57

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