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