On the competitive optimality of Huffman codes

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)<El´(X), indicating optimality in long run performance (which is well known), and competitively dominates l´(x), in the sense that Pr{ l (X)<l´(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