Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing

I am trying to prove that, in an optimal encoding (possibly Huffman?), if letter frequencies are increasing, their encoding lengths are monotonically decreasing. It is intuitive that this makes sense, but I'm not sure how to write it formally.

Here is what I have:

Let $$x_1$$ and $$x_2$$ be two letters in the encoding where $$x_1$$ is before $$x_2$$.

It is given that $$\text{freq}(x_1) < \text{freq}(x_2)$$.

Suppose the contradiction, $$\text{code_length}(x_1) < \text{code_length}(x_2)$$.

The cost would be $$B(A) = \text{freq}(x_1)\times\text{code_length}(x_1) + \text{freq}(x_2)\times\text{code_length}(x_2)+r$$ where $$r$$ is the remaining cost of the other letters in the code.

If we were to swap the code lengths of $$x_1$$ and $$x_2$$, the cost would become $$B(A) = \text{freq}(x_1)\times\text{code_length}(x_2) + \text{freq}(x_2)\times\text{code_length}(x_1)+r$$

The cost would decrease, meaning the code where they are not swapped is not an optimal encoding.

The problem is I'm not sure how to prove that the cost would decrease. Is that provable? Also, is there a better approach?

• Not decreasing, but non-increasing. Feb 19 '20 at 13:37

I have come up with a solution.

To show that the old $$B(A)$$ is larger than the new $$B(A)$$, it is necessary to show that

$$\text{f}(x_1)\times\text{c_len}(x_1) + \text{f}(x_2)\times\text{c_len}(x_2) > \text{f}(x_1)\times\text{c_len}(x_2) + \text{f}(x_2)\times\text{c_len}(x_1)$$

($$\text{f}(x)$$ = frequency of $$x$$, $$\text{c_len}(x)$$ = length of $$x$$'s encoding.)

By moving terms over and using distributive law:

$$\text{f}(x_1)(\text{c_len}(x_1) - \text{c_len}(x_2)) > \text{f}(x_2)(\text{c_len}(x_1) - \text{c_len}(x_2))$$

Since $$\text{c_len}(x_1) < \text{c_len}(x_2)$$, $$\text{c_len}(x_1) - \text{c_len}(x_2) < 0$$

Therefore dividing both sides by $$\text{c_len}(x_1) - \text{c_len}(x_2)$$ leaves:

$$\text{f}(x_1) < \text{f}(x_2)$$

Which is true as it is a premise.

Correct me if I have made a mistake.