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.

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 224 / 4 / c / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-224/4/c/solution