Finding the coding scheme for an optimum variable length code

Question

Suppose X is an i.i.d. r.v. with an infinite alphabet, X = {1, 2, ...}. I also have P(X = i) = 2^{−i}

I want to find the coding scheme for an optimum variable length code however I don't follow the solutions coding scheme.

It appears that they have a 0 preceded by a 1 each time as you go down. Can someone please explain this to me.

For reference I have attached images/links of my question and solution as I am unsure of the policy of this website with not typing questions.

https://i.stack.imgur.com/QPudG.png

https://i.stack.imgur.com/gLYGj.png

Answer 1

You get a prefix free code due to the pattern you mention.

Apply Huffman's algorithm to any finite truncation (you'd need to scale the probabilities but huffman doesn't care). For example

• A:1/2
• B:1/4
• C:1/8

would lead to B,C being merged giving the codewords, say,

• A:0
• B:10
• C:11

This argument may be extended to any finite length code source distribution $$(2^{-i})_{i=1}^n,$$ and also used to prove the achievability of the infinite expected codeword length of 2.