 Solution

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

Exchange the two complete codewords while leaving the code tree unchanged. The prefix code property is preserved because the set of codewords is unchanged. If

p_{i} > p_{j}

but

l_{i} > l_{j}

(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. Hence $p_{i} > p_{j}$ implies $l_{i} \leq l_{j}$ . This probability monotonicity of optimal prefix-code lengths is valid even if some probabilities are zero; equal probabilities impose no order.^[ref]

 New to topics? Read the docs here!