# Randomized prefix code

An input symbol is randomly chosen from a set of symbols with known associated probabilities and encoded using a prefix code that minimizes the expected codeword length. Is it possible to further reduce the total expected codeword length by randomly choosing the prefix code from a set of prefix codes with associated probabilities?

No, it is not possible. A proof follows.

Let $$\mathrm{E}(L \mid 0)$$ be the expected codeword length for the prefix code $$0$$ that minimizes it. The answer to the question is "no" if it is always true that:

$$\mathrm{E}(L \mid 0) \le \mathrm{E}(L),\tag{1}$$

where $$\mathrm{E}(L)$$ is the total expected codeword length using a randomly chosen prefix code $$i$$ from a set of $$N$$ prefix codes denoted by $$i\in\{1, 2, 3, \ldots, N\}$$. We can divide both sides of Eq. 1 by $$\mathrm{E}(L \mid 0)$$, which is positive, so we could equivalently show that:

$$\Leftrightarrow 1 \le \frac{\mathrm{E}(L)}{\mathrm{E}(L \mid 0)}.\tag{2}$$

Using the law of total expectation:

$$\frac{\mathrm{E}(L)}{\mathrm{E}(L \mid 0)} = \frac{\sum_{i=1}^{N}\mathrm{E}(L \mid i)P(i)}{\mathrm{E}(L \mid 0)} = \sum_{i=1}^{N}\frac{\mathrm{E}(L \mid i)}{\mathrm{E}(L \mid 0)}P(i),\tag{3}$$

where $$\mathrm{E}(L \mid i)$$ is the expected codeword length for a prefix code $$i$$ with an associated non-zero probability $$P(i)$$. Because the prefix code $$0$$ minimizes the expected codeword length, we have $$\mathrm{E}(L \mid 0) \le \mathrm{E}(L \mid i)$$ $$\Rightarrow$$ $$\mathrm{E}(L \mid i)/\mathrm{E}(L \mid 0) \ge 1$$ $$\Rightarrow$$ $$\mathrm{E}(L \mid i)/\mathrm{E}(L \mid 0) - 1 \ge 0$$ for all $$i$$. It follows that:

$$\frac{\mathrm{E}(L)}{\mathrm{E}(L \mid 0)} = \sum_{i=1}^N P(i) + \sum_{i=1}^{N}\left(\frac{\mathrm{E}(L \mid i)}{\mathrm{E}(L \mid 0)}-1\right)P(i) \ge \sum_{i=1}^N P(i)= 1,\tag{4}$$

where the second sum is never negative. This proves Eq. 2. Therefore, the answer to the question is "no".