Write $p(x)=\mathbb P(X_1^n=x)$, $a(x)=p(x)W(x)$, and
$$
A=\sum_xa(x)=\mathbb E[W(X_1^n)].
$$
On the support of $p$, define the <probability mass function>
$$
R^*(x)=\frac{a(x)}A=\frac{p(x)W(x)}{\mathbb E[W(X_1^n)]}.
$$
For any real length function satisfying the <Kraft inequality>, put $K=\sum_x2^{-L(x)}\leq1$ and $R_L(x)=2^{-L(x)}/K$. The <Gibbs inequality> gives
$$
\begin{aligned}
\sum_xa(x)L(x)
&=A\sum_xR^*(x)\{-\log_2R_L(x)-\log_2K\}\\
&=A\{H(R^*)+D(R^*\Vert R_L)-\log_2K\}\\
&\geq AH(R^*).
\end{aligned}
$$
Equality holds for the ideal weighted lengths
$$
L_n^*(x)=-\log_2R^*(x)
=\log_2\frac{\mathbb E[W(X_1^n)]}{p(x)W(x)}.
$$
Thus the smallest average weighted description length is
$$
\mathbb E[W(X_1^n)]
H\!\left(\frac{p(\mathord\cdot)W(\mathord\cdot)}{\mathbb E W(X_1^n)}\right).
$$
When $p$ has full support, the displayed $L_n^*$ attains this minimum. If some strings have zero probability, the same value is the infimum over finite lengths and is attained by the extended-real ideal assignment $L_n^*(x)=\infty$ there; finite codewords of arbitrarily large length approach it.

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 224 / 3 / c / Solution

 Solution

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