Past exam of the information theory course of the University of Oxford / 2021 / 2 / b / iv

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 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.