# 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. – Yuval Filmus May 30 at 20:06
• This is essentially a calculus question. – Yuval Filmus May 30 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. – Abishek Puri May 31 at 22:41
• I don’t think your solution works. Perhaps you could provide more details? – Yuval Filmus Jun 1 at 4:37

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.