An Entropy View of Fibonacci Trees
Yasuichi Horibe · The Fibonacci Quarterly · 1982
In a binary tree with n terminal nodes weighted by probabilities p1 …, pn, Σpi = 1, it is assumed that each left branch has cost 1 and each right branch has cost 2. The cost ai of terminal node pi is defined to be the sum of costs of branches that form the path from the root to this node. The sum Σpiai is called the average cost of the tree. As a top-down tree-building rule we consider ψ-weight-balancing which constructs a binary tree by successive dichotomies of the ordered set p1, …, pn according to a certain weight ratio closely approximating the golden ratio. Let H = H(p1, …, pn) = -Σpi log pi be the Shannon entropy of these probabilities. The ψ-weight-balancing rule is motivated by the fact that the entropy per unit of cost H (x, 1 - x) / (1 • x + 2 • (1 - x)) for the division x : (1 - x) of the unit interval is maximized when x = ψ = (√5 - 1)/2, the golden cut point. It is then shown that the average cost of the tree built by ψ-weight-balancing is bounded above by H/(-log ψ) + 1, if the terminal nodes have probabilities p1, …, pn , p1 ≥ …pn, from left to right in this order in the tree. If pj +1/pj ≥ (1/2)ψ for each j, the above bound can be improved to H/ (-log ψ) + ψ. For the case p1 = ⋯ = pn, we obtain the following results. The ψ-weight-balancing constructs an optimal tree in the sense of minimum average cost and constructs the Fibonacci tree of order k when n = Fk, the kth Fibonacci number. The average cost of the optimal tree is given exactly. Furthermore, for an arbitrarily given number of terminal nodes, the ψ-weight-balanced tree is also “balanced” in the sense of Adelson-Velskii and Landis, and is the highest of all balanced trees.We will discuss some properties of Fibonacci (Fibonaccian) trees in view of their construction by an entropic weight-balancing, beginning with the following preparatory section: