= Solution
Put $S=\sum_{k=1}^a2^{-l_k}$ and let $l_{\max}$ be the largest length. Expanding $S^n$ sums $2^{-L}$ over all strings of $n$ source symbols, where $L$ is the total code length. By unique decodability, the concatenations of length $r$ in this <sum> are all distinct, so there are at most $2^r$ of them. Since $n\leq r\leq nl_{\max}$,
$$
S^n\leq\sum_{r=n}^{nl_{\max}}2^r2^{-r}\leq nl_{\max}.
$$
Taking $n$th roots and sending $n$ to infinity proves the <Kraft–McMillan inequality>
$$
\boxed{\sum_{k=1}^a2^{-l_k}\leq1.}
$$
Now $q_k=2^{-l_k}/S$ is a <probability distribution>. With base-two logarithms, <Gibbs inequality> gives
$$
0\leq D(p\Vert q)=\sum_kp_k\log_2\frac{p_k}{q_k}
=-H(X)+\mathbb EL+\log_2 S.
$$
Terms with $p_k=0$ contribute zero. Therefore
$$
\boxed{\mathbb EL-H(X)=D(p\Vert q)-\log_2S\geq0.}
$$
The normalization by $S$ is important: the raw numbers $2^{-l_k}$ need not <sum> to one.
Back to article page
