# Why does the Fibonacci sequence produce a worst-case Huffman encoding?

I noticed this in my Algorithms class, but just now got around to asking.

• The question is not well-defined. What do you mean by “worst”? Feb 15 '11 at 14:43
• @Ito: The obvious definition of "worst" is the difference between the average codeword length of the Huffman code and the Shannon entropy of the probability distribution. I don't know if this is what the OP had in mind. See my next comment. Feb 15 '11 at 14:56
• Change the probability distribution in my previous comment to start with $\phi^2$, so the sum is 1. This certainly produces a maximum depth Huffman encoding. I don't know whether that qualifies as worst. Certainly it isn't the worst, using the definition in my previous comment, if you are allowed probabilities close to 1. But maybe it's worst-case if you are restricted to distributions with probabilities $< \frac{1}{2}$. Feb 15 '11 at 14:57
• (1) @Peter: That definition of “worst” sounds reasonable (under the restriction on the maximum probability of a symbol, as you wrote), and I think that that question is interesting. (2) I had voted the question down because of the underspecification. When the asker edits the question to clarify what “worst” in the question means, I will reconsider the vote. Feb 15 '11 at 18:44
• If we don't get an answer from the OP in a few days, I'll revive the question by asking it myself. Feb 16 '11 at 11:10