= Solution
A binary code $c:\mathcal A\to\{0,1\}^*$ is a <prefix code> when no codeword is a proper prefix of another. If the source letters have probabilities $p_1,\ldots,p_m$ and codeword lengths $l_1,\ldots,l_m$, the <expected value> of its codeword length is
$$
L=\sum_{r=1}^m p_r l_r.
$$
It is an <optimal prefix code> when it minimizes $L$ among all binary prefix codes for that source.
Suppose $p_i>p_j$ but $l_i>l_j$. Exchanging the codewords assigned to $\mu_i$ and $\mu_j$ leaves the set of words, and hence prefix-freeness, unchanged. The change in expected length is
$$
p_i l_j+p_j l_i-(p_i l_i+p_j l_j)
=(p_i-p_j)(l_j-l_i)<0,
$$
contradicting optimality. Thus
$$
\boxed{p_i>p_j\ \Longrightarrow\ l_i\leq l_j},
$$
which is the <probability monotonicity of optimal prefix-code lengths>.
Represent the code by its binary prefix tree and choose a codeword $wb$ of maximal length, where $b\in\{0,1\}$. Its sibling is $w(1-b)$. If that sibling were not a codeword, it could not have a codeword below it either, since such a word would be longer than $wb$. Replacing $wb$ by $w$ would then preserve prefix-freeness and strictly reduce $L$. This is impossible for an optimal code, so $w(1-b)$ is also a maximal-length codeword. The pair differs only in its last digit, proving the <deepest sibling property of an optimal prefix code>.
Back to article page
