Past exam of the communication Theory course of the University of Oxford / 2008 / 3 / a / Solution

Unique decipherability makes the map from $(X_1,\dots ,X_m)$ to the concatenated binary string $M$ injective. Entropy is unchanged by an injective relabelling, and memorylessness gives independence, henceGiven $L=\ell$, the string has at most $2^{\ell }$ possibilities. The entropy bound for finite alphabets therefore gives $H(M\mid L=\ell )\le \ell$. Averaging,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,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.