= Solution
First assume a <full-support finite distribution>, as stated above. Let $L$ be the largest <codeword length> and take a <tree leaf> at depth $L$. Every existing <tree child> of its <tree parent> must also be a <tree leaf>: an internal <tree child> would have a descendant deeper than $L$. If the chosen <tree leaf> were its <tree parent>'s only <tree child>, moving its symbol to that <tree parent> would shorten its <codeword> by one, preserve the <prefix code> property, and reduce <expected codeword length> by its positive <probability>. That contradicts optimality. The <tree parent> therefore has at least two <tree children>, both <tree leaves>. A second <codeword> has the same first $L-1$ digits and a different last digit, proving the required \b[deepest <sibling codeword> property] for a <ternary prefix code>.
For the literal wording allowing zero <probabilities>, take $p=(1,0,0)$ and the <prefix code> $(0,10,110)$. Its <expected codeword length> is one, which is minimal: with more than one message an empty <codeword> is impossible, so the positive-probability message must have length at least one. Yet the deepest <tree leaf> $110$ has no <sibling codeword>. \b[Thus positivity or an additional convention removing redundant zero-weight branches is needed.]
Back to article page
