If I want to use entropy as an approximation for the expected length of Huffman coding, how good is the approximation? I know the following identity:

$H(X)\leq L(X)< H(X)+1\ $

where expected length is:

$L(X)= \sum_i p_il_i$

and entropy is:

$H(X)= \sum_i p_ilog_2(1/p_i)$

But it's not tight enough, or in other words, helpful enough in some cases. Is there a way to approximate the residual using $p_i$, like what we do in Taylor series?

  • 1
    $\begingroup$ "But it's not tight enough". Well, in some sense it is. Take for example a Bernoulli variable with $p \approx 0$... $\endgroup$ – leonbloy Jan 6 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.