# Prove the MinAveCodeLen of a product information source is less than the sum of that of the multiplicand and multiplier source?

The product of 2 independent sources $$(S_A,P_A)$$ and $$(S_B,P_B)$$ is defined as

$$(S,P)\text{ s.t. }S = \{s_As_B|s_A\in S_A,s_B\in B\}\text{ and }\ P(s_As_B) = P_A(s_A)\cdot P_B(s_B)\,\forall s_A\in S_A,s_B\in S_B$$

and the MinAveCodeLen is the minimum average codeword length which is equal to the average codeword length of a Huffman coding.

The problem is to prove

$$\mathrm{MinAveCodeLen}(P)\leq\mathrm{MinAveCodeLen}(P_A)+\mathrm{MinAveCodeLen}(P_B)$$

The original problem is quite confusing. I am asked to prove $$H(P_A)+H(P_B)=H(P)$$ in the previous part, so I was trying to relate the problem with $$H$$ at first with no progress.

An encoding scheme for $${P}$$ could be described graphically as follows: Suppose $$T_A$$, $$T_B$$ are 2 Huffman trees for $${P}_A$$ and $${P}_B$$ respectively. For each leaf $$s_{Ai}$$ in $$T_A$$ replace it with $$T_B$$, i.e. Letting $$|S_A| = q,|S_B| = q$$, the average code word length of this coding scheme is $$C = \frac{\sum l_{Ai}+l_{Bj}}{pq} = \frac{q\sum l_{Ai}+p\sum l_{Bj}}{pq} = \mathrm{MinAveCodeLen}({P}_A)+\mathrm{MinAveCodeLen}\mathbb{P}_B)$$ where $$l_{Ai}$$, $$l_{Bj}$$ are the codeword length of $$s_{Ai}$$ and $$s_{Bj}$$ in the Huffman code corresponding to $$T_A$$, $$T_B$$. Therefore, $$\mathrm{MinAveCodeLen}({P})\leq C\leq\mathrm{MinAveCodeLen}({P}_A)+\mathrm{MinAveCodeLen}({P}_B)$$