# Constraint on number of codes of maximum length in a binary Huffman code.

A Random Variable '$X$' take values from a discrete alphabet $K = \{k_1, k_2, k_3,k_4 \}$, with probability mass function {$p(k_i)$} = {$0.6, 0.2, 0.15, 0.05$}.

The constructed Binary Huffman codes on $K$ are {$0, 10, 110, 111$}. The length of codewords are {$l_1, l_2,l_3,l_4$} = {$1, 2, 3, 3$}. The maximum of {$1, 2, 3, 3$} is $L = 3$. The number of codewords with length $L = 3$ is $2$, which is even.

Suppose if $K = \{k_1, k_2, k_3,....k_m \}$($m$ is very large), having some valid probability mass function. I constructed Binary Huffman Codes on the alphabet $K$. The length of the Huffman codewords be {$l_1, l_2,....l_m$} . Suppose the maximum of {$l_1, l_2,....l_m$} is $L$. Then can I say 'The number of Huffman codewords of length $L$ is even'$?$

• Your nomenclature is odd. "for each realization $k_i$ : I guess you mean "for each symbol $k_i$ " (or value). Further, what is $l(max)$ ? Second, your "argument" does not look as an argument but as an affirmation. And I frankly don't understand it. Care to elaborate? Sep 4, 2018 at 23:19
• @leonbloy, for each realization $k_i$, yes I mean for each symbol $k_i$. I elaborated the question. Go through it! Sep 5, 2018 at 17:28
• It's clear now. One thing that confused me is that you use the word "code" for "codeword". Sep 6, 2018 at 13:03

Yes, you can. The easiest way to see it is to take a maximum length code of length $L$. Invert the lat bit of the code and you must get another code. If the version with the last bit flipped were not another code, it must be a prefix of some code, but that would be longer than $L$. You can group the maximum length codes in pairs that agree on the first $L-1$ bits and have opposite last bits, so there is an even number of them.