Assume the random variable X ∼ p(x). We design a Huffman code C for this X but unfortunately we assume an incorrect probability distribution p' for the random variable. What can you say about the expected code length L(C) per letter of our code? Your professor thought that it holds L(C) ≤ H(X) + D(p∥p') + 1. Prove him wrong; i.e. find a counterexample to this conjecture.
So we design our tree from the p' distribution but calculate L(C) from the p distribution based on the lengths from p' call them l(x). That is $$L(C) = \sum_{x}^{}p(x)l(x)$$
So I know I can play around with a couple factors to find a distribution such that L(C) - 1 ≤ H(X) + D(p∥p')
I can minimize the H(X) with a skewed distribution and I can minimize the relative entropy by making p and p' similar and I can try and maximize my code length but I am having trouble figuring out which combination of factors will achieve my result. I also know that the true bound on L(C) is 1 + 2H(X) + 2D(p∥p').