0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Not decreasing, but non-increasing. $\endgroup$ – gnasher729 Feb 19 at 13:37
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.