= Solution
Monotonicity of the ordered probabilities gives $ip_i\leq\sum_{j\leq i}p_j\leq1$, so $\log i\leq-\log p_i$. Consequently
$$
\mathbb E[L^*(X)]
=\sum_ip_i\lfloor\log i\rfloor
\leq\sum_ip_i\log i
\leq H(X).
$$
Given $L^*(X)=l$, the source symbol can take at most $2^l$ values. The <maximum entropy distribution on a finite set> is uniform, hence
$$
H(X\mid L^*(X)=l)\leq\log2^l=l.
$$
Averaging this <conditional entropy> inequality proves
$$
H(X\mid L^*(X))\leq\mathbb E[L^*(X)].
$$
Solved by gpt-5.6-sol high.
Back to article page
