# Are Huffman code lengths monotonic with respect to probability?

Suppose you have an alphabet of $$k$$ symbols and a probability distribution $$P = p_1, p_2, \ldots, p_k$$ over them. Furthermore, assume that $$p_i > 0$$ for all $$i$$.

Let $$minhuff_i(P)$$ be the length of the minimum code length assigned to symbol $$i$$ among all optimal Huffman codes for the distribution $$P$$, and likewise let $$maxhuff_i(P)$$ be the maximum code length. (There may be multiple optimal Huffman codes for a given distribution, and hence multiple choices for code lengths.)

Now suppose we have a new probability distribution $$P'$$ such that $$p'_1 \geq p_1$$ and $$p'_i \leq p_i$$ for all $$i > 1$$.

Is it always the case that $$minhuff_1(P') \leq minhuff_1(P)$$ and $$maxhuff_1(P') \leq maxhuff_1(P)$$? Intuitively, increasing the probability of a given symbol should cause the optimal Huffman code to assign it a shorter code word, but I can't find any way to prove this.

• Do you assume monotone probabilities, $p_i\geq p_{i+1}$? Also you switched to uppercase from lowercase in defining the probabilities for $P'$. Commented Jul 10, 2023 at 12:38
• The idea was to represent the distribution as a vector with P and the individual components with lowercase p. And no, it doesn't have to be sorted. Commented Jul 11, 2023 at 0:41
• but in "suppose that..."you are using uppercase, that was my confusion. I think this question is not too easy to answer. Did you look for computational counterexamples? Commented Jul 12, 2023 at 15:59
• What do you mean by computational counterexamples? Just generate a bunch of random numbers, calculate the huffman codes, and see if any counterexamples turn up? Commented Jul 13, 2023 at 16:05
• yes that's what I mean. and am I right that your $P_i$ and $P_i'$ should be lowercase? If yes, please fix Commented Jul 13, 2023 at 18:02

Let's A be the optimal code on first probability distribution denoted by $$x_i$$'s, with length of symbol $$i$$ equal to $$a_i$$. and let B be the optimal code the second probability distribution $$y_i$$ with length $$b_i$$ for symbol $$i$$. We know $$x_1 $$\forall i > 1; \; y_i < x_i$$ Optimality on $$X$$: $$\sum_i a_i x_i \le \sum_i b_i x_i$$ Separating the first term and putting on the second side: $$\sum_{i=2}^n a_i x_i \le \sum_{i=2}^n b_i x_i + b_1 x_1 - a_1 x_1$$ We will use this in the middle of the second part.
Optimality on $$Y$$: $$\sum_i b_i y_i \le \sum_i a_i y_i$$ Now separating the first term for ease, $$b_1 y_1 + \sum_{i=2}^n b_i y_i \le a_1 y_1 + \sum_{i=2}^n a_i y_i$$ We know $$y_i < x_i$$ so $$\sum_{i=2}^n a_i y_i < \sum_{i=2}^n a_i x_i$$, $$b_1 y_1 + \sum_{i=2}^n b_i y_i \le a_1 y_1 + \sum_{i=2}^n a_i y_i < a_1 y_1 + \sum_{i=2}^n a_i x_i$$ Using the first section: $$b_1 y_1 + \sum_{i=2}^n b_i y_i \le ... < a_1 y_1 + \sum_{i=2}^n a_i x_i \le a_1 y_1 + \sum_{i=2}^n b_i x_i + b_1 x_1 - a_1 x_1$$ So keeping the first and last terms: $$b_1 y_1 + \sum_{i=2}^n b_i y_i < a_1 y_1 + \sum_{i=2}^n b_i x_i + b_1 x_1 - a_1 x_1$$ Putting thing in one side: $$b_1 y_1 - b_1 x_1 + a_1 x_1 - a_1 y_1 < \sum_{i=2}^n b_i x_i - \sum_{i=2}^n b_i y_i$$ Factoring $$(b_1 - a_1) (y_1 - x_1) < \sum_{i=2}^n b_i (x_i - y_i)$$ and also $$y_1 - x_1 = \sum_{i=2}^n (x_i - y_i)$$, so $$(b_1 - a_1) < \frac{\sum_{i=2}^n b_i (x_i - y_i)}{\sum_{i=2}^n (x_i - y_i)}$$