TAOCP 7.2.1.4 Exercise 35
The Erdős–Lehner distribution (43) is the limiting distribution for the normalized random variable arising from the largest part (equivalently, the number of parts) of a random partition of $n$.
Section 7.2.1.4: Generating All Partitions
Exercise 35. [HM21] [HM21] In the Erdős–Lehner probability distribution (43), what value of x is (a) most probable? (b) the median? (c) the mean? (d) What is the standard deviation?
Verified: no
Solve time: 23m26s
Solution
The Erdős–Lehner distribution (43) is the limiting distribution for the normalized random variable arising from the largest part (equivalently, the number of parts) of a random partition of $n$. In Knuth’s normalization, it is the Gumbel distribution with cumulative distribution function
$$ F(x)=\exp(-e^{-x}), $$
and probability density function
$$ f(x)=F'(x)=e^{-x}\exp(-e^{-x})=\exp(-x-e^{-x}). $$
All four requested quantities follow from direct analysis of this density and distribution function.
For the most probable value, the mode is the maximizer of $f(x)$. Since $\log f(x)=-x-e^{-x}$, differentiation gives
$$ \frac{d}{dx}(-x-e^{-x})=-1+e^{-x}. $$
Setting this to zero yields $e^{-x}=1$, hence $x=0$. The second derivative is $-e^{-x}$, negative at $x=0$, so this point is a strict maximum. Thus the most probable value is $x=0$.
For the median, the defining condition is $F(x)=\tfrac12$. This gives
$$ \exp(-e^{-x})=\frac12, $$
hence $e^{-x}=\log 2$, and therefore $x=-\log\log 2$.
For the mean, the distribution is the standard Gumbel law. Its expectation is the Euler–Mascheroni constant $\gamma$, obtained from the classical identity
$$ \int_{-\infty}^{\infty} x, e^{-x} e^{-e^{-x}},dx = \gamma. $$
Thus the mean equals $\gamma$.
For the variance, the standard Gumbel distribution has second central moment $\pi^2/6$, obtained from the evaluation of the integral
$$ \int_{-\infty}^{\infty} (x-\gamma)^2 e^{-x} e^{-e^{-x}},dx = \frac{\pi^2}{6}. $$
Therefore the standard deviation is $\pi/\sqrt{6}$.
Collecting the results, the most probable value is $0$, the median is $-\log\log 2$, the mean is $\gamma$, and the standard deviation is $\pi/\sqrt{6}$.
$$ \boxed{\text{(a) }0,\quad \text{(b) }-\log\log 2,\quad \text{(c) }\gamma,\quad \text{(d) }\frac{\pi}{\sqrt{6}}} $$
This completes the solution.