TAOCP 6.2.2 Exercise 37

Let $(P_1,\dots,P_n)$ be uniformly distributed over the simplex $P_k>0,\quad \sum_{k=1}^n P_k = 1.$ The entropy is $H(P_1,\dots,P_n) = -\sum_{k=1}^n P_k \log P_k.$ By symmetry, $\mathbb{E}[H(P_1,\dots...

taocpmathematicsalgorithmsvolume-3hm-hard

Section 6.2.2: Binary Tree Searching

Exercise 37. [HM26] [HM26] (P. J. Bayer, 1975.) Suppose (P1,..., Pn) is a random probability distribution, namely a random point in the (n, 1)-dimensional simplex defined by P, > 0 forl1<k<nand Pj +---+P, =1. (Equivalently, (Pi,...,Pn) is a set of random spacings, in the sense of exercise 3.3.2, 26.) What is the expected value of the entropy A(Pi,..., Pn)?

Verified: yes
Solve time: 1m25s

Setup

Let $(P_1,\dots,P_n)$ be uniformly distributed over the simplex

$P_k>0,\quad \sum_{k=1}^n P_k = 1.$

The entropy is

$H(P_1,\dots,P_n) = -\sum_{k=1}^n P_k \log P_k.$

By symmetry,

$\mathbb{E}[H(P_1,\dots,P_n)] = -n,\mathbb{E}[P_1 \log P_1].$

The marginal distribution of $P_1$ is the Beta distribution with parameters $(1,n-1)$, with density

$f(x) = (n-1)(1-x)^{n-2},\quad 0<x<1.$

Thus

$\mathbb{E}[P_1 \log P_1] = \int_0^1 x \log x ,(n-1)(1-x)^{n-2},dx.$

Solution

Introduce, for $t>-1$,

$F(t) = \mathbb{E}[P_1^t] = (n-1)\int_0^1 x^t (1-x)^{n-2},dx.$

This is a Beta integral,

$F(t) = (n-1)\frac{\Gamma(t+1)\Gamma(n-1)}{\Gamma(n+t)} = \frac{\Gamma(t+1)\Gamma(n)}{\Gamma(n+t)}.$

Differentiate using $\frac{d}{dt}\log \Gamma(t)=\psi(t)$, where $\psi$ is the digamma function. Set

$\log F(t)=\log \Gamma(t+1)-\log \Gamma(n+t)+\log \Gamma(n).$

Hence

$\frac{F'(t)}{F(t)}=\psi(t+1)-\psi(n+t).$

Since $F'(t)=\mathbb{E}[P_1^t \log P_1]$, evaluation at $t=1$ gives

$\mathbb{E}[P_1 \log P_1] = F(1)\bigl(\psi(2)-\psi(n+1)\bigr).$

Now

$F(1)=\mathbb{E}[P_1]=\frac{1}{n},$

so

$\mathbb{E}[P_1 \log P_1]=\frac{1}{n}\bigl(\psi(2)-\psi(n+1)\bigr).$

Therefore

= \psi(n+1)-\psi(2).$$ Using $\psi(n+1)=H_n-\gamma$ and $\psi(2)=1-\gamma$, $$\mathbb{E}[H(P_1,\dots,P_n)] = (H_n-\gamma)-(1-\gamma)=H_n-1.$$ Thus $$\boxed{H_n-1}.$$ This completes the proof. ∎ ## Verification The identity $F(t)=\Gamma(t+1)\Gamma(n)/\Gamma(n+t)$ matches the Beta integral with parameters $(t+1,n-1)$. Differentiation yields $F'(t)=\mathbb{E}[P_1^t\log P_1]$ because differentiation under the integral sign is justified by boundedness of $x^t\log x$ on $(0,1]$ for $t>-1$. Symmetry reduces the entropy expectation to $-n\mathbb{E}[P_1\log P_1]$ since all coordinates have identical marginals and linearity applies. ## Notes The result depends only on the uniform Dirichlet$(1,\dots,1)$ structure; for Dirichlet$(\alpha,\dots,\alpha)$, the same method yields expressions in digamma functions that reduce to harmonic numbers when $\alpha=1$.