2
$\begingroup$

I'm reading about Huffman coding, more precisely, the proof that it is an optimal code. Most proofs I found assume an existence of an optimal code (without justifying the existence). This is pointed out at the beginning of the video followed by a proof of the above fact.

In the video, I didn't understand why there exists $i$ such that $\sup l_i^{(n)}=\infty$, so I tried to prove the statement myself.

My question is whether the following "proof" is correct:

Let $\mathcal C=\{C: C\text{ is a uniquely decodable code}\}$ and let $\mathcal L=\{L_C: L_C \text{ is the expected length of the code }C \in\mathcal C\}$. Then $\mathcal L$ is a non-empty set of positive integers, so by the well-ordering principle, it has a least element. The least element must correspond to the optimal code (by definition of optimality).

$\endgroup$

1 Answer 1

2
$\begingroup$

Well, the expected length need not be an integer: you're averaging, and there's plenty of laws over integers which have a noninteger mean (e.g., the Bernoulli laws). For a nonempty set of reals (which $\mathcal{L}$ is because the Huffman code is UD), with a lower bound (which $\mathcal{L}$ has since length is nonnegative), there \emph{is} an infimum for the set, but this doesn't mean that the infimum is achieved, e.g., for $S = (0,1),$ $\inf_{x \in S} x = 0,$ but of course no $x \in S$ is actually $0$, so this infimum is not achieved in $S$. It is true, however, that in such a case, there is always a sequence of numbers in the set that approaches the infimum in the limit.

That's the point of the question in the video: it could be that there is some alphabet $\mathcal{X}$, and message distribution $p$ such that no code actually achieves the infimum, i.e. for any code $C, L_C > \inf \mathcal{L}$.

I do agree that the video skips the key point, why must there be a symbol for which the length explodes. To see this, suppose for the sake of contradiction it were the case that there was some maximum length $\ell_\max$ such that for any $C^{(n)},$ and any symbol $x \in \mathcal{X},$ $\sup_{C^{(n)}} \ell_x^n \le \ell_{\max}$, where $\ell_x^n$ is the length of the codeword for $x$ in $C^{(n)}$. But then notice that there are at most $2^{\ell_{max} |\mathcal{X}|}$ such codes in total (for each $x$, we have only $\le 2^{\ell_{\max}}$ choices for codeword, and there are only $|\mathcal{X}|$ messages). But this means that we cannot have an infinite sequence of codes $C^{(n)}$ such that $L^{(n)}$ is monotonically decreasing (since we only have a finite possible choices of codes, and so eventually the $L^{(n)}$ would have to stop decreasing and be equal to the previous one instead). This contradicts the assumption in the video $L^{(1)} > L^{(2)} > \cdots,$ and we're done.

$\endgroup$
5
  • $\begingroup$ But the proofs that I found which show optimality of the Huffman code don't really show $L_H\le L_C$ for all $C$. Instead they show that if $C$ is an optimal code, then $L_H\le L_C$. This assumes existence of an optimal code, right? $\endgroup$ Dec 3, 2023 at 10:08
  • 1
    $\begingroup$ Ah, you're quite right, there's that lemma that talks about "optimal code with lowest frequencies merged first" (it's been a while since I read this I guess). I'll edit that bit out :) $\endgroup$ Dec 3, 2023 at 18:42
  • $\begingroup$ Oh, actually, there's maybe another way to see the existence that may be simpler, then: recall the reduction of binary codes over $\mathcal{X}$ to binary trees with $|\mathcal{X}|$ leaves. Its a straightforward observation that if a tree has an internal node with only one child, we can get a better tree by eliminating this internal node, and so we can reduce to optimising over full trees. But observe that the depth of a full tree with $|\mathcal{X}|$ leaves is bounded by $|\mathcal{X}|,$ and so for any code-tree $C$, there exists a $\endgroup$ Dec 3, 2023 at 18:56
  • $\begingroup$ (contd.) full tree of depth $\le |\mathcal{X}|$ which has cost no worse than $C$, and so we can restrict to optimising over such trees. But now observe that there are only a finite number of these, and so trivially there must exist an optimal such tree, and we're done. In fact given this reduction, one can see the Huffman argument as saying that for any code corresponding to this restricted set of trees, the Huffman-tree is no worse, so I guess it's implicitly doing the strategy I was describing: for any $C$, there exists a $C'$ with $L_{C'} \le L_C,$ and then $L_H \le L_{C'}$. $\endgroup$ Dec 3, 2023 at 18:58
  • $\begingroup$ In other words, it should be possible to rewrite this proof without an explicit reference to "optimal trees" in the body of the proof. This would make things more clunky, though, so I doubt it helps in the structure of the proof per se :) $\endgroup$ Dec 3, 2023 at 19:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .