= Solution
Exchange the two complete <codewords> while leaving the <code tree> unchanged. The <prefix code> property is preserved because the set of <codewords> is unchanged. If $p_i>p_j$ but $l_i>l_j$, the change in <expected codeword length> is
$$
(p_il_j+p_jl_i)-(p_il_i+p_jl_j)=(p_i-p_j)(l_j-l_i)<0,
$$
contradicting optimality. Hence \b[$p_i>p_j$ implies $l_i\leq l_j$]. This <probability monotonicity of optimal prefix-code lengths> is valid even if some <probabilities> are zero; equal <probabilities> impose no order.<A Method for the Construction of Minimum-Redundancy Codes by David A. Huffman>[p. 1099, Derived Coding Requirements: probability ordering and permissible exchange of equal-probability messages]{ref}
Back to article page
