Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, then $H\le L_1 \le H+1$ and $H\le L_2< H+2$, where $H$ is the (base-2 Shannon) entropy of the symbol distribution.

Is anything known about the average redundancy of Huffman and Hu-Tucker codes, that is, the expected value of $R_1 = L_1-H$ or $R_2 = L_2-H$, when the symbol weights are random?

Definition & Details:

Assume we have $n$ symbols $a_1,\ldots,a_n$ with weights $\vec P=(P_1,\ldots,P_n)$, where these weights are themselves random, e.g., they are uniformly drawn from all stochastic vectors (so that $P_i\ge0$ and $P_1+\cdots+P_n = 1$ a.s.); stated otherwise: $\vec P$ has a $\mathrm{Dirichlet}(1,\ldots,1)$ distribution).

Then $H = - \sum_{i=1}^n P_i \log_2(P_i)$ and $L_{1,2} = \sum P_i \operatorname{depth}(a_i)$, where $\mathrm{depth}(a_i)$ is the depth (number of edges on path from root) of leaf $a_i$ in an optimal binary tree on leaves $a_1,\ldots,a_n$ (Huffman tree) for $L_1$ and the depth in an optimal binary search tree with leaves $a_1\le a_2\le\cdots a_n$ (optimal alphabetic tree).

My Attempts:

I am seeking an analytic solution, in the best case as a closed formula in $n$. I can approximate the expectations with a Monte Carlo simulation, here are a few example values (from 10,000,000 repetitions each; up to the given digits several repetitions agreed; * only 10,000 repetitions)

n    E[R2]
3    0.297
4    0.284
5    0.268
6    0.253*
10   0.217*

Note that the upper bound of $2$ is far from tight here.

This question is probably related, but was posed unclearly and does not have an answer.

A somewhat similar problem, has been solved by Szpankowski. There, alphabet symbols are blocks of bits of length $n$, generated by a memoryless source with $p<0.5$ is the probability for $0$ in the block. The average redundancy of different codes, including Huffman's, are computed for large $n$. Here the symbol probabilities are fixed, and so is the redundancy; the average here means average redundancy over all symbols, not over random symbols weights.

This does not answer my question above thus.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.