# 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”? –  Tsuyoshi Ito 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. –  Peter Shor 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}$. –  Peter Shor 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. –  Tsuyoshi Ito 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. –  Peter Shor Feb 16 '11 at 11:10