Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
thank you, I solved this assignment an another way. –  Tatar Elemér Nov 18 '12 at 22:30
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.