Huffman code with probabilities $p_1, p_2,\ldots, p_n$

Question

I have solved the first two subsections of an assignment, but I can't solve the last subsection.

We have a Huffman code with probabilities $p_1,p_2,\ldots, p_n$ and we know that $p_1>p_2>\cdots>p_n>0$.

$y_1$ - the code for the character whose probability is $p_1$? And $|y1|$ is the length of $y_1$.

I proved that:

• if $|y_1| = 1$ then $p_1 \geq 1/3$.
• if $p_1 < 1/3$ then $|y_1| \geq 2$ (it is not the same as above).

I can't prove:

• if $p_1 > 2/5$ then $|y_1| = 1$.

Thanks for all kind of help.

Answer 1

Since you say it's an assignment I won't give you the full answer, but here's an orientation. You can build a proof by contradiction from two components: Dirichlet's principle and the construction of the Huffman tree.

First prove that given that $p_1 = 2/5 + \epsilon$ and $|y_1| > 1$ there must be a merge step where the words are partitioned into three disjoint sets: $\{y_1\}$, $A$, and $B$ such that the total probability of the words in $A$ is more than $p_1$ (and hence the total probability of the words in B is less than $1/5 - 2\epsilon$).

Then prove that the step which generated $A$ by merging the two smallest sets was performed incorrectly because $B$ was actually smaller than one of them.

Answer 2

I use this:

if p1 > 2/5 then at least one symbol is encoded by a codeword of length 1. (Hint: Suppose not and consider the vertices of the Huffman tree which are distance 2 from the root.) Solution: Suppose not. This immediately implies that at distance 2 from the root of the encoding tree there are exactly 4 vertices, say a1, a2, a3, a4 with probabilities p1, p2, p3, p4 . One of these, say a1 corresponds to a1 or was obtained by merging it. It follows that p1 > p1 > 2/5. Suppose a3 and a4 are merged at the next step to form a new symbol a with probability p. Since a1 must be merged before the final step, we must have that p > p1 (otherwise we would merge a2 with a). Since also 2p2 > p3 + p4 = p > p1 and p1 + p2 + p = 1, we obtain that 1 > p1 + p1/2 + p1 = 5p1/2 > 5p1/2, a contradiction.