Asymptotic Average Redundancy of Huffman (and Shannon-Fano) Block Codes

We study the redundancy of Huffman code (which, incidentally, is as old as the author of this paper). It has been known from the inception of this code that in the worst case Huffman code redundancy- defined as the excess of the code length over the optimal (ideal) code length- is not more than onc. Over more than forty years, insightful, elegant and useful constructions have been set up to determine tighter bounds on the redundancy. One should mention here Gallager's upper bound of PI +0.086 (PI is the probability of the most likely symbol), and tighter bounds due to Capacelli, de Santis and others. However, to the best of our knowledge no precise asymptotic results have been reported in literature thus far. We consider here a memoryless binary source generating a sequence of length n distributed as binomial(n,p) with p being the probability of emitting O. Based on recent result of Stubley, we prove that for p ¥- 1/2 the average redundancy Rn of the Huffman code as n-)- 00 becomes ~- lJ~2 = 0.057304..