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

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.

Answer 1

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.