Randomized prefix code

Question

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?

Answer 1

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".