= Solution
Work on the source support, so its listed probabilities are positive; zero-probability symbols may be omitted. An optimal binary <prefix code> minimizes the <expected codeword length> for that distribution. The same optimal expected length is attained when optimization is over uniquely decipherable codes, by the converse and existence parts of <Kraft–McMillan inequality>.
Choose Shannon lengths $\ell_k=\lceil-\log_2p_k\rceil$. They satisfy $2^{-\ell_k}\le p_k$, so the preceding existence theorem gives a <prefix code> with those lengths. Also $\ell_k<-\log_2p_k+1$ for every symbol, including the integer cases. Thus its expected length is less than $H(X)+1$. An optimal code cannot have a larger expected length, proving
$$
\boxed{\sum_kp_k\ell_k<H(X)+1}.
$$
For a deterministic one-symbol source the empty word has length zero, consistent with this bound.
Back to article page
