= Solution
With a <full-support finite distribution>, suppose two distinct <tree parents> at depth $L-1$ each have exactly two <tree children>, both <tree leaves>. Move one <tree leaf> from the second pair into the vacant third <tree child> slot of the first <tree parent>. Its length remains $L$, so this relocation does not change <expected codeword length>. The second <tree parent> now has a single <tree child>, which is a <tree leaf>. Replace that remaining <tree child>'s <codeword> by the <tree parent>'s word. This preserves the <prefix code> property and shortens a positive-probability <codeword> by one. <Expected codeword length> strictly decreases, a contradiction. Thus \b[there is at most one deepest pair with exactly two <sibling codewords>].
If zero-probability symbols are retained without a reduction convention, the claim can fail. The <probability mass function> $(1,0,0,0,0)$ with <prefix code> $(0,100,101,110,111)$ has the optimal <expected codeword length> one, yet contains the two deepest pairs $(100,101)$ and $(110,111)$. The contraction would only shorten a zero-probability word.
Back to article page
