# When Huffman coding is inefficient?

I have a question regarding the redundancy of Huffman coding. I know that for a general prefix code we have the following inequality:

$$H(X) \le R \le H(X) + 1$$

$$R$$ being the rate (average codeword length) and $$H$$ is the entropy. Based on this relation, how can we conclude that Huffman coding is very inefficient if entropy of the source is much smaller than 1 bit/symbol?

If $$X$$ is any non-constant source, then any codeword in any prefix code for $$X$$ has length at least $$1$$, and so $$R \geq 1$$. Therefore if $$X$$ is a source with very low entropy then there's a large discrepancy between $$H(X) \approx 0$$ and $$R \approx 1$$.
As a concrete example, consider a binary source in which the probability of one of the options is $$\epsilon$$. Then $$H(X) = \epsilon \log (1/\epsilon) + O(\epsilon)$$ whereas $$R = 1$$.
• It’s not based on that relation. It’s based on the definition of $R$. – Yuval Filmus May 24 at 9:14