# 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

## 2 Answers

This paper may shed some light on the issues: http://www.springerlink.com/content/w32x70520k8jj617/

• Its behind a paywall. :( – user3845 Feb 18 '11 at 18:33

The Huffman algorithm considers the two least frequent elements recursively as the sibling leaves of maximum depth in code tree. The Fibonacci sequence (as frequencies list) is defined to satisfy F(n) + F(n+1) = F(n+2). As a consequence, the resulting tree will be the most unbalanced one, being a full binary tree.