1
$\begingroup$

I am unable to solve the following problem:

Let $$n \geq 2$$ $$p_{1} \geq p_{2} \geq ... \geq p_{n}$$ $$p_{i} = 2^{-k_{i}}$$ with $k_{i} \in \mathbb{N}$ and $\sum_{i=1}^{n}p_{i} = 1$.

$p_{i}$ is the probability that the character $c_{i}$ appears. We then execute the Huffman-algorithm. Show: The expected codelength of the resulting Huffman-Code is $$-\sum_{i=1}^{n}p_{i}\log{p_{i}}$$

How does one show that? In the first part of the task I showed that $p_{n-1} = p_{n}$.

This is what I have so far: I think the expected value of the codelength is defined as $E(C) = \sum_{i=1}^{n}p_{i}h(c_{i})$ where $h(c_{i})$ is the height of character $c_{i}$ in the Huffman-Tree.

From that I followed that I have to show that $E(C) = \sum_{i=1}^{n}p_{i}h(c_{i}) = \sum_{i=1}^{n}p_{i}k_{i}$, so I thought that I'd show that $h(c_{i}) = k_{i}$. I was told that this could be done via induction. But how does one show this?

I'd greatly appreciate any help, tips, ideas or solutions/proofs. I hope that I made clear what the problem is, as I translated it from my native language into english. If there's something that is not understandable, please let me know. Thanks in advance and have a great day!

$\endgroup$
2
$\begingroup$

HINT: The induction is on $n$. If $n=2$, the only possibility is that $k_1=k_2=1$: no other combination gives you $p_1+p_2=1$. You can easily verify that in that case $h(c_1)=h(c_2)=1$. For the induction step, assume the result for some $n\ge 2$, and prove it for $n+1$. Note that after you combine the the two least probable characters in the first step of the Huffman algorithm, you have in effect an alphabet of $n$ characters, one corresponding to the union of the two least probable characters, so you can apply the induction hypothesis.

$\endgroup$
2
$\begingroup$

You have the pieces you need. You will show by induction on the number of nodes that $h(c_i)=k_i$. The first step in constructing the Huffman tree $T$ will be to combine $c_{n-1}$ and $c_n$; since $p_{n-1}=p_n=2^{-k}$ the combined node has weight $2^{-(k-1)}$ -- in particular, $1$ over a power of two. So the induction hypothesis applies to the tree $T'$ with the combined node; in particular $h(c_i')=k_i'$ for the $T'$ code. All that remains is to show that when you now split that final node of $T'$ into $c_{n-1}$ and $c_{n}$ the probabilities and depths work out correctly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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