0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.