Solution

ID: past-exam-of-the-information-theory-course-of-the-university-of-oxford/2021/2/b/ii/solution

First assume a full-support finite distribution, as stated above. Let be the largest codeword length and take a tree leaf at depth . Every existing tree child of its tree parent must also be a tree leaf: an internal tree child would have a descendant deeper than . 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 digits and a different last digit, proving the required deepest sibling codeword property for a ternary prefix code.
For the literal wording allowing zero probabilities, take and the prefix code . 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 has no sibling codeword. Thus positivity or an additional convention removing redundant zero-weight branches is needed.

New to topics? Read the docs here!