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

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.

-

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.

-
thank you, I solved this assignment an another way. –  Tatar Elemér Nov 18 '12 at 22:30