(IC 4.12) Optimality of Huffman codes (part 7) - existence

We prove that Huffman codes are optimal. In part 7, we show that there exists an optimal code for any given p.
A playlist of these videos is available at:
• Information Theory

[@DrHalfbaked]

Nicely done. I think the remark at the beginning can actually be made into a complete proof in the following way: note that the ECL of a given code is only determined by the codeword lengths corresponding to positive probability masses. Therefore, a set of infinitely many distinct ECLs *must* be generated by infinitely many distinct *restricted* length-vectors (i.e. length-vectors restricted to the positive probability indices). The rest follows exactly as in the remark.

[@ZHeisenberg]

nice job