Question

Given a probability distribution $p$ across an alphabet, we define redundancy as:

Expected Length of codewords - entropy of p = $\ E(S) - h(p)$

Prove that for each $\epsilon$ with $0 \le \epsilon \lt 1$ there exists a $p$ such that the optimal encoding has redundancy $ \epsilon$.

Attempts

I have tried constructing a probability distribution like $p_o = \epsilon, p_1 = 1 - \epsilon $ based on a previous answer, but I can't get it to work.

Any help would be much appreciated.

Edit:

The solution I think I have found is mapped below.

redundancy = $E(S) - h(p) = \sum p_is_i + \sum p_ilogp_i$. We want to show that for a given $\epsilon$, we can find a $p$ that makes redundancy = $\epsilon$. So $\sum p_is_i + \sum p_ilogp_i = \epsilon ==> \sum p_is_i = -\sum p_ilogp_i + \epsilon$.

We know the optimal value for $s_i$ will be less than $-logp_i + 1$, so we can write all $s_i$ as $s_i = -logp_i+\alpha_i$.

Now, $\sum p_is_i = -\sum p_ilogp_i + \epsilon ==> \sum p_i(-logp_i + \alpha_i) = -\sum p_ilogp_i + \epsilon ==> \sum p_i\alpha_i = \epsilon$.

Intuitively I feel that you can always find a p so that the above is true for $epsilon$, because the $\alpha$ values are governed by how far away from a power of two your $m$ is, but I am not sure how to prove this last step.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top