Entropy & Coding: Proving Huffman Reduction Cannot Decrease

[CCMarie]

For {p_i}_i=1,n being the probability distribution, I want to show that a Huffman reduction cannot be decreasing, and I reached a point where I need to show that

q+H(p₁,...,p_n-s,q) ≥ H(p₁,...,p_n), where

q = p_n-s+1 + ... + p_n and s is chosen such that: 2 ≤ s ≤ m (m≥n) and s = n (mod(m-1))

where m is the number of m-arr symbols from a Huffmann m-arr algorithm.

 

[Valkarie]

To show this, we can use the definition of the Huffman algorithm to establish the inequality. The Huffman algorithm assigns codes to symbols based on their probabilities, with the most probable symbol being assigned the shortest code. We can use this to show that q+H(p1,...,pn-s,q) is greater than or equal to H(p1,...,pn).Let p⁰ be the probability of the least probable symbol among the first n symbols in the probability distribution. Then, the Huffman code for this symbol will be of length m−1. Since the total probability of all symbols is 1, the total length of the code for all of the symbols must add up to m−1. Therefore, the code for the remaining m−n symbols must have a total length of q+H(p1,...,pn-s,q). Since q+H(p1,...,pn-s,q) ≥ m−1, we can conclude that q+H(p1,...,pn-s,q) ≥ H(p1,...,pn).