Kraft Inequality

Assume that we would like to encode a set of symbol $S = \{ s_1, s_2, ..., s_n \}$ into binary strings $T = \{ t_1, t_2, ..., t_n : t_i \text{ is a 0, 1 sequence of finite length} \}$ , such that $\forall i \neq j$ , $t_i$ is not a prefix of $t_j$ . Denote the length of $t_i$ as $n_i$ . Then the Kraft Inequality states that

\sum_{i = 1}^n 2^{-n_i} \le 1

For convenience, we write $t_i \ll t_j$ if $t_i$ is a prefix of $t_j$ . Intuitively, we can view a particular sequence $t_i = t_i^1t_i^2 ...t_i^{n_i}$ as the abbreviation of number $0.t_i^1t_i^2 ...t_i^{n_i}$ . The fact that for $j \neq i$ , neither $t_i \ll t_j$ nor $t_j \ll t_i$ implies that $t_j$ does not lies in the interval $[0.t_i^1t_i^2 ...t_i^{n_i}, 0.t_i^1t_i^2 ...t_i^{n_i} + 2^{-n_i})$ . As the intervals induced by $t_i$ 's are mutually exclusive, we can easily conclude that

\sum_{i = 1}^n 2^{-n_i} \le 1

Indeed, the statement of Kraft Inequality can be made stronger such that the inequality holds as long as $\{ t_1, t_2, ..., t_n \}$ are uniquely decodable. To verify this, note that for any sequence $\tau \in T^*$ with length $k$ , there are at most only $2^k$ possible combinations. Therefore,

(\sum_{i = 1}^n 2^{-n_i})^l = \sum_{k = 1}^{l \cdot n_{max}} C_k 2^{-k}

where $n_{max} = \max\{n_1, n_2, ..., \}$ and $C_k \le 2^k$ . Hence

(\sum_{i = 1}^n 2^{-n_i})^l \le l \cdot n_{max} \rightarrow \sum_{i = 1}^n 2^{-n_i} \le l^{1/l} \cdot n_{max}^{1/l}

Taking $l$ to infty we get the desired result.

An immediately implication is that Entropy is the lower bound of the encode length of a document. To see this, denote the probability of $s_i$ as $p_i$ . Then

\begin{aligned} \sum_{i} p_i \log \frac{1}{p_i} - \sum_{i} p_i n_i &= \sum_{i} p_i \log \frac{1}{p_i} \cdot \frac{1}{2^{n_i} } \\ &\le \log \sum_{i} p_i \frac{1}{p_i} \cdot \frac{1}{2^{n_i} } \\ &\le \log \sum_{i} \frac{1}{2^{n_i} } \\ &\le 0 \end{aligned}