On the competitive optimality of Huffman codes
Thomas M. Cover · IEEE Transactions on Information Theory · 1991
Let X be a discrete random variable drawn according to a probability mass function p(x), and suppose p(x), is dyadic, i.e., log(1/p(x)) is an integer for each x. It is shown that the binary code length assignment l(x)=log(1/p(x)) dominates any other uniquely decodable assignment l'(x) in expected length in the sense that El(X)Pr(l (X)>l'(X)), which indicates l is also optimal in the short run. In general, if p is not dyadic then l=(log 1/p) dominates l'+1 in expected length and competitivity dominates l'+1, where l' is any other uniquely decodable code.>