How to show that in noiseless coding theorem, the bound $\mathrm{MinACL}<H(P)+1$ is tight?

The theorem states that

$$H(P)\leq\mathrm{MinACL}(P)

where, $$\mathrm{MinACL}$$ means the minimum average code word length of a given information source, i.e. the average code word length of any Huffman coding and $$H$$ means the entropy of the probability distribution $$P$$.

Now, the problem is how to show that for any $$\epsilon>0$$, there is a probability distribution $$P$$ s.t. $$\mathrm{MinACL}(P) - H(P)\geq1-\epsilon$$?

(I was given a hint that I can start with a source s.t. $$H(P)=\mathrm{MinACL}(P)$$ and try to change the probabilities in order to skew the code.}

Em…… I seem to have figured out how to construct a probability distribution to achieve $$\mathrm{MinACL}$$ as close to $$H(P)+1$$ as possible. Suppose, for the information source $$(S,P)$$ with $$|S| = 2^l + 1$$, $$p_0 = 1 - \epsilon$$, $$p_i = \epsilon/2^l,1\leq i\leq2^l$$, a valid Huffman tree could be constructed as follows: First build a full binary tree with $$s_i,1\leq i\leq2^l$$, as leaves and then make $$s_0$$ sibling of the root of this binary tree, and child of the Huffman tree root node. This scheme can be justified easily given $$\epsilon\in(0,0.5)$$. Then, $$H(P) = -(1-\epsilon)\log(1-\epsilon)-(\epsilon/2^l)\log(\epsilon/2^l)$$ and $$\mathrm{MinACL}(P) = (l+1)\cdot\epsilon+1\cdot(1-\epsilon)$$.
$$\lim_{\epsilon\to0}\mathrm{MinACL}(P)-H(P) = 1$$
(I haven't calculated the limit, but the graph below if of much evidence: )
• Take $l=0$ for a simple example. – Yuval Filmus Feb 9 at 2:59
You can take the distribution $$P(0) = 1-\epsilon$$, $$P(1) = \epsilon$$. This distribution has entropy $$h(\epsilon) = O(\epsilon \log 1/\epsilon)$$, but $$\mathrm{MinACL}(P) = 1$$. As $$\epsilon$$ tends to $$0$$, the gap tends to $$1$$, since $$\lim_{\epsilon\to 0} h(\epsilon) = 0$$.