Huffman code - Probability of finding a specific bit in the code

Question

Let $X$ be a random variable in $A = \{1,2,3,4\}$ with pmf $p(1) = \frac{1}{8}$, $p(2) = \frac{1}{8}$, $p(3) = \frac{1}{4}$ and $p(4) = \frac{1}{2}$. Let $c$ be the binary Huffman code $c(1) = 110$, $c(2) = 111$, $c(3) = 10$ and $c(4) = 0$. Generate a sequence in $A^n$ iid based on pmf p, then encode the sequence using $c$. Pick a bit uniformly at random from this encoded sequence. What is the probability that this bit is $1$?

Answer 1

This is a very special case of Huffman coding that every symbol has a power of $2^{-k}$ for the length of k. This is the case that the expected length of Huffman is equal to the entropy of the source.

It also results in the sequence generated from i.i.d. source to have random i.i.d. bitstream. So independent of the position, all bits have an equal probability of $1/2$.

For your case, I will explain case by case. Assume that the bit we pick is the 3rd bit of a Huffman codeword then the probability of getting 0 of the codeword 110 is equal to getting 1 of 111 both equal to 1/8. Now assume that we pick the 2nd bit, the probability of getting 1 is (1/8+1/8=1/4) for the codewords of 110 and 111 and the probability of getting 0 is 1/4 for codeword 10. And if you picked the 1st bit, you have a probability of 1/2 of getting 0 of the codeword 0, and a probability of getting 1 is (1/8+1/8+1/4=1/2) for the codewords 110, 111, and 10. So independent of where your bit is the probability of 0 and 1 are equal.