<p>This paper may shed some light on the issues: <a href="http://www.springerlink.com/content/w32x70520k8jj617/">http://www.springerlink.com/content/w32x70520k8jj617/</a></p>

CC BY-SA 2.5
2011-02-18T18:33:37.420Z
Its behind a paywall. :(
user3845
CC BY-SA 2.5
2011-02-17T04:12:11.713Z
2011-02-17T04:12:11.713Z
Joseph Malkevitch
<p>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.</p>

CC BY-SA 3.0
2012-12-08T14:30:38.333Z
2012-12-08T14:30:38.333Z
hengxin
<p>I noticed this in my Algorithms class, but just now got around to asking.</p>

CC BY-SA 2.5
2011-02-15T06:53:34.697Z
i don't understand. what does this mean ? is the alphabet here the set of all digits ?
Suresh Venkat
CC BY-SA 2.5
2011-02-15T12:40:35.307Z
Is the question essentially: why is a worst-case Huffman encoding obtained form the probability distribution $\phi$, $\phi^2$, $\phi^3$, $\phi^4$, $\ldots$, where $\phi$ is the golden ratio? (and with the last probability $\phi^k$ increased so the sum is 1.) This is certainly not going to give a good Huffman encoding, but is this really worst-case?
Peter Shor 
CC BY-SA 2.5
2011-02-15T14:42:14.640Z
Googling "huffman fibonacci" gives a possibly related paper: http://arxiv.org/abs/cs/0410013
Radu GRIGore
CC BY-SA 2.5
2011-02-15T14:43:32.297Z
The question is not well-defined.  What do you mean by “worst”?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-15T14:56:59.253Z
@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 
CC BY-SA 2.5
2011-02-15T14:57:49.987Z
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 
CC BY-SA 2.5
2011-02-15T18:44:53.520Z
(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
CC BY-SA 2.5
2011-02-16T11:10:56.047Z
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 
CC BY-SA 2.5
2011-02-18T18:33:01.693Z
By "worst", I mean maximum-height Huffman binary trees.
user3845
CC BY-SA 2.5
2011-02-18T21:51:06.260Z
If that's your definition of worst, I think your question may be answered in the paper given in Joseph Malkevitch's answer (depending on exactly what you mean by the Fibonacci sequence).
Peter Shor 
<co.combinatorics><optimization><it.information-theory><encoding>
Why does the Fibonacci sequence produce a worst-case Huffman encoding?
user3845
# Why does the Fibonacci sequence produce a worst-case Huffman encoding?

(Asked by: username_0 on 2011-02-15)

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

**Tags:** co.combinatorics, optimization, it.information-theory, encoding
> **Comments:**
> **username_1**: i don't understand. what does this mean ? is the alphabet here the set of all digits ?  
> **username_2**: Is the question essentially: why is a worst-case Huffman encoding obtained form the probability distribution $\phi$, $\phi^2$, $\phi^3$, $\phi^4$, $\ldots$, where $\phi$ is the golden ratio? (and with the last probability $\phi^k$ increased so the sum is 1.) This is certainly not going to give a good Huffman encoding, but is this really worst-case?  
> **username_3**: Googling "huffman fibonacci" gives a possibly related paper: http://arxiv.org/abs/cs/0410013  
> **username_4**: The question is not well-defined.  What do you mean by “worst”?  
> **username_2**: @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.  
> **username_2**: 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}$.  
> **username_4**: (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.  
> **username_2**: If we don't get an answer from the OP in a few days, I'll revive the question by asking it myself.  
> **username_0**: By "worst", I mean maximum-height Huffman binary trees.  
> **username_2**: If that's your definition of worst, I think your question may be answered in the paper given in Joseph Malkevitch's answer (depending on exactly what you mean by the Fibonacci sequence).  

---

## 2 answers

### Answer by username_5 on 2011-02-17. Score: 7

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

> **Comments:**
> **username_0**: Its behind a paywall. :(  

---

### Answer by username_6 on 2012-12-08. Score: 3

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.


---

