# Prove that the upper bound in the Noiseless-coding theorem is strict

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.

• I suggest you keep trying. May 30, 2019 at 20:06
• This is essentially a calculus question. May 30, 2019 at 20:18
• I've found a solution by letting there be m letters in the alphabet, each equiprobable. Then the entropy is logm and the expected length is logm + 2a/m, where a is the gap between m and the nearest power of 2. Then I show that for all choices of epsilon you can find integer values for d and m. I am not sure how to solve it using a calculus approach. May 31, 2019 at 22:41
• I don’t think your solution works. Perhaps you could provide more details? Jun 1, 2019 at 4:37

## 1 Answer

Take the probability distribution that you consider: there are two symbols, one with probability $$\delta$$, the other with probability $$1-\delta$$.

Any minimum redundancy code for this distribution has average codeword length $$1$$. Therefore the redundancy is $$1 - h(\delta)$$. Since $$h(1/2) = 1$$, $$\lim_{\delta\to0} h(\delta)=0$$ and $$h$$ is continuous, for every $$0 < \gamma \leq 1$$ you can find $$\delta > 0$$ such that $$h(\delta) = \gamma$$. Choosing $$\gamma = 1 - \epsilon$$, we get a distribution whose redundancy is $$1-\gamma = \epsilon$$.

It is natural to "outlaw" such distributions by requiring all probabilities to be smaller than some $$\kappa$$. For small $$\kappa$$, we can no longer find distributions whose redundancy is close to 1. It is natural to conjecture that as $$\kappa$$ goes to zero, the maximum redundancy also goes to zero. However, this is not the case: for arbitrarily small $$\kappa$$, there are distributions whose redundancy is roughly 0.086. See Gallager's Variations on a theme by Huffman, which establishes that the limiting value of the maximum redundancy is (roughly) 0.086.

• Ah so you don't have to find an explicit value for delta w.r.t gamma, we can use the properties of entropy to argue that there must exist a value that allows entropy to equal gamma. I didn't think of that, thanks a lot! Out of interest, can my solution be continued as well, or is it not possible to show that the final sum can be made equal to epsilon? Jun 1, 2019 at 19:40
• I don't understand your solution well enough to answer this question. Jun 1, 2019 at 19:41
• I'll keep working on it then to see if I can find some way to prove it, thanks for the solution you proposed though :) Jun 1, 2019 at 19:44