= Solution
Put $L=L^*(X)$ and $\mu=\mathbb E L$. Since $L$ is a function of $X$, the <chain rule for information entropy> and part (c) give
$$
H(X)=H(L)+H(X\mid L)\leq H(L)+\mu.
$$
Part (a), applied to the nonnegative integer-valued random variable $L$, yields
$$
H(L)\leq(1+\mu)h\left(\frac1{1+\mu}\right)
=\log(1+\mu)+\mu\log\left(1+\frac1\mu\right).
$$
The <logarithm inequality> $\log(1+t)\leq t\log e$ implies $\mu\log(1+1/\mu)\leq\log e$. Thus
$$
H(X)\leq\mu+\log(1+\mu)+\log e.
$$
Part (c) also gives $\mu\leq H(X)$, so monotonicity of the <logarithm> lets us replace $\log(1+\mu)$ by $\log(H(X)+1)$. Rearranging proves
$$
\mathbb E[L^*(X)]
\geq H(X)-\log[H(X)+1]-\log e.
$$
Back to article page
