Lesson 9

It turns out that one can estimate the redundancy of the Huffman code based on a given frequency set, without running the algorithm. For this, we define the Shannon entropy of the distribution \((p_{1}, \dotsc, p_{n})\), where \(p_{i}>0\) and \(p_{1}+\dotsb+p_{n}=1\): \[H(p_{1}, \dotsc, p_{n})=-\sum_{i=1}^{n}p_{i}\log_{2} p_{i}.\] The graph of the function \(H(p)=H(p,1-p)\) is shown below.

Theorem. Let \(p_{i}>0\) and \(p_{1}+\dotsb+p_{n}=1\). Then for the minimum redundancy \(\alpha\) of a code (with frequencies \(p_{1}, \dotsc, p_{n}\)) the following inequality holds: \[H(p_{1}, \dotsc, p_{n}) \le \alpha \le H(p_{1}, \dotsc, p_{n}) + 1 \ .\]

Proof.

• Upper bound.  Let \(l_{i}\) be an integer such that \(2^{-l_i}\le p_{i} < 2^{-(l_i - 1)}\). Then, by the theorem above, there exists a prefix code with these symbol lengths. Its redundancy is: \[\sum_{i=1}^{n}p_{i}l_{i} \le \sum_{i=1}^{n}p_{i}(-\log_{2} p_{i}+1) = H(p_{1}, \dotsc, p_{n}) + 1 \ .\]


• Lower bound.  We need to prove that for any uniquely decodable code with lengths \((l_{1}, \dotsc, l_{n})\) the inequality \(\sum p_{i}(-\log_{2}p_{i}) \le \sum p_{i}l_{i}\) holds. \[\begin{align*}\sum p_{i}\left(\log_{2} \left(\frac{1}{p_i}\right) - l_{i}\right)&=\sum p_{i}\log_{2}\left(\frac{2^{-l_i}}{p_i}\right)&\text{(properties of \(\log\))}\\&\le \log_{2} \left(\sum p_{i} \cdot \frac{2^{-l_i}}{p_i}\right)&\text{(concavity of \(\log_{2}\))}\\&= \log_{2}\left(\sum2^{-l_i}\right)\\&\le \log_{2}1&\text{(Kraft–McMillan inequality)}\\&= 0 \ .\end{align*}\]

◼