Solution

A binary code

c : A \to {0, 1}^{*}

is a prefix code when no codeword is a proper prefix of another. If the source letters have probabilities

p_{1}, \dots, p_{m}

and codeword lengths

l_{1}, \dots, l_{m}

, the expected value of its codeword length is

L = \sum_{r = 1}^{m} p_{r} l_{r} .

It is an optimal prefix code when it minimizes

L

among all binary prefix codes for that source.

Suppose

p_{i} > p_{j}

but

l_{i} > l_{j}

. Exchanging the codewords assigned to

μ_{i}

and

μ_{j}

leaves the set of words, and hence prefix-freeness, unchanged. The change in expected length is

p_{i} l_{j} + p_{j} l_{i} - (p_{i} l_{i} + p_{j} l_{j}) = (p_{i} - p_{j}) (l_{j} - l_{i}) < 0,

contradicting optimality. Thus

p_{i} > p_{j} ⟹ l_{i} \leq l_{j},

Represent the code by its binary prefix tree and choose a codeword

w b

of maximal length, where

b \in {0, 1}

. Its sibling is

w (1 - b)

. If that sibling were not a codeword, it could not have a codeword below it either, since such a word would be longer than

w b

. Replacing

w b

w

would then preserve prefix-freeness and strictly reduce

L

. This is impossible for an optimal code, so

w (1 - b)

is also a maximal-length codeword. The pair differs only in its last digit, proving the deepest sibling property of an optimal prefix code.

Solved by gpt-5.6-sol high.

 Ancestors (11)