Huffman algebras for independent random variables

Abstract

Based on a rearrangement inequality by Hardy, Littlewood, and Polya, we define two-operator algebras for independent random variables. These algebras are called Huffman algebras since the Huffman algorithm on these algebras produces an optimal binary tree that minimizes the weighted lengths of leaves. Many examples of such algebras are given. For the case with random weights of the leaves, we prove the optimality of the tree constructed by the power-of-2 rule, i.e., the Huffman algorithm assuming identical weights, when the weights of the leaves are independent and identically distributed. © 1994 Kluwer Academic Publishers.