Huffman algebras for independent random variables |
| |
Authors: | Cheng-Shang Chang Joy A Thomas |
| |
Affiliation: | (1) IBM Research Division, T.J. Watson Research Center, 10598 Yorktown Heights, NY |
| |
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. |
| |
Keywords: | Huffman algorithm entropy stochastic ordering (max +) algebras |
本文献已被 SpringerLink 等数据库收录! |
|