OurBigBook.comSite Source code

Probability monotonicity of optimal prefix-code lengths

If symbols of probabilities

p_{i} > p_{j}

have codeword lengths

l_{i}

and

l_{j}

in an optimal prefix code, then

l_{i} \leq l_{j}

. Otherwise, exchanging their codewords preserves the prefix property and changes the expected length by

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

contradicting optimality.

 Ancestors (7)

 Incoming links (1)

Solution