= Solution
Unique decipherability makes the map from $(X_1,\ldots,X_m)$ to the concatenated binary string $M$ <injective>. <Shannon entropy>[Entropy] is unchanged by an <injective> relabelling, and <memoryless classical information source>[memorylessness] gives <independence>, hence
$$
H(M)=H(X_1,\ldots,X_m)=mH(X).
$$
Given $L=\ell$, the string has at most $2^\ell$ possibilities. The <Shannon entropy>[entropy] bound for finite alphabets therefore gives $H(M\mid L=\ell)\le\ell$. Averaging,
$$
H(M\mid L)\le\mathbb EL=m\mathbb E|c(X)|.
$$
The random length cannot simply be discarded: it can also carry information. Let $\ell_{\max}$ be the maximum <codeword length>, finite since the alphabet is finite. Since $L$ is a <function> of $M$ and takes at most $m\ell_{\max}+1$ values,
$$
mH(X)=H(L)+H(M\mid L)\le\log_2(m\ell_{\max}+1)+m\mathbb E|c(X)|.
$$
Divide by $m$ and let $m\to\infty$. This proves $\boxed{\mathbb E|c(X)|\ge H(X)}$. The conclusion also covers a deterministic source; the source's lowercase $x$ in its final <expectation> denotes the random source letter.
Back to article page
