23
$\begingroup$

I would like to know if I have discovered or merely rediscovered the following pretty fact.

A partition of $[0,1]$ into intervals of lengths $p_{i, i=1\ldots n}$ induces a probability distribution with entropy $-\sum p_i \log_2 p_i$; call this also the entropy of the partition.

For a given $n$, entropy gets maximized by the uniform partition, namely taking all the $p_i$ equal to $1/n$.

Alternatively, one can generate a type of random partition by randomly sampling $n-1$ points according the uniform distribution on $[0,1]$, and then making the sampled points the endpoints of intervals.

The pretty fact: as $n$ grows large, the average amount by which the entropy of the uniform partition exceeds the entropy of this sort of random partition tends to a limit with the simple expression $(1-\gamma)/\ln(2)=0.609948863612\ldots$.

Question: does this fact appear anywhere in the literature? (Also interested if it's a folk theorem.)

$\endgroup$
  • 10
    $\begingroup$ $\gamma-1$ shows up in Shao, Y. & Jiménez, R., Entropy for random partitions and its applications, Journal of Theoretical Probability (1998) 11: 417. doi.org/10.1023/A:1022683822547. $\endgroup$ – Gerry Myerson Feb 13 '19 at 2:22
  • 6
    $\begingroup$ It also turns up in Florian Hermanns, Asymptotic behavior of the entropy of random partitions of the interval, pdf available online. $\endgroup$ – Gerry Myerson Feb 13 '19 at 2:29
13
$\begingroup$

The earliest reference I have found for this result is Entropy and maximal spacings for random partitions (E. Slud, 1978).

Theorem 2.2 states that the entropy $W_n=-\sum_{i=1}^n p_i \ln p_i$ of the random partition is asymptotically normally distributed for $n\rightarrow \infty$ as ${\cal N}(\ln n +\gamma-1,\alpha_n)$, with $\alpha_n={\cal O}(1/n)$.
(Note that $\ln n$ is the "maximal entropy" from the OP, with natural logarithms rather than base 2.)
Theorem 2.3 then specifies that, almost surely as $n\rightarrow\infty$, $$\ln n - W_n=1-\gamma+{\cal O}\left(\sqrt{\frac{\ln\ln n}{n}}\right).$$

The proof follows directly from formulas for moments of $W_n$ derived in On a Class of Problems Related to the Random Division of an Interval (D.A. Darling, 1953).


A related result that also follows from Darling (1953) is the large-$n$ limit of $T_n=-\sum_{i=1}^n \ln(np_i)$. As derived in Logarithms of sample spacings (S. Blumenthal, 1968), $n^{-1/2}(T_n-n\gamma)$ is asymptotically normally distributed as ${\cal N}( 0,\zeta(2)-1)$.

| cite | improve this answer | |
$\endgroup$

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.