3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Do you assume monotone probabilities, $p_i\geq p_{i+1}$? Also you switched to uppercase from lowercase in defining the probabilities for $P'$. $\endgroup$
    – kodlu
    Commented Jul 10, 2023 at 12:38
  • $\begingroup$ 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. $\endgroup$
    – Antimony
    Commented Jul 11, 2023 at 0:41
  • $\begingroup$ 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? $\endgroup$
    – kodlu
    Commented Jul 12, 2023 at 15:59
  • $\begingroup$ 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? $\endgroup$
    – Antimony
    Commented Jul 13, 2023 at 16:05
  • $\begingroup$ yes that's what I mean. and am I right that your $P_i$ and $P_i'$ should be lowercase? If yes, please fix $\endgroup$
    – kodlu
    Commented Jul 13, 2023 at 18:02

1 Answer 1

1
$\begingroup$

I have an upper bound on it. I have to make the notation a bit different so things are easier to read.

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<y_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)} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .