# Analysis of Entropy on Two Distributions: Proving $H(X) < H(X')$

Let $$P=\{p_1, p_2, p_3 ..., p_n\}$$ and $$P^{'}= \left\{ \dfrac{(p_1 + p_2)}{2}, \dfrac{(p_1 + p_2)}{2}, p_3, ..., p_n\right\}$$ be distributions on the same random variable $$X$$.

$$1$$. Show $$H(X)\leq H(X^{'})$$ where $$H(X)$$ is Shannon's entropy formula:$$H(X) = -\sum_{i=1}^n p_i\log_{2}p_i$$

This make sense since $$P^{'}$$ is closer to the uniform distribution, which maximizes entropy, but I'm not sure how to go about proving this. I believe there is some expectation that we will use the the fact that entropy can be decomposed to its binary components (with normalization along the way.)

$$2$$. Define $$P^{''}=\left\{ p_1, ..., p_{i-1}, \dfrac{(p_i + p_j)}{2}, p_{i+1}, ..., p_{j-1}, \dfrac{(p_i + p_j)}{2}, p_{j+1}, ..., p_n \right\}$$. Use the "permutation principle" and $$(a)$$ to show $$H(X)\leq H(X^{''})$$

• What did you try? There's a direct approach, which is just to expand $H(X') - H(X)$, cancel terms, and argue via convexity of $-\log$. A more operational approach is to note that $X'$ is the output of pushing $X$ through a channel that randomises the first two symbols, and then using the data processing inequality. Mar 9, 2019 at 21:33
• I believe we ought to use convexity in our argument, but I can not get the inequality in the proper form to argue it directly. I currently have: "It suffices to show $p_1\log_{2}p_1 + p_2\log_{2}p_2 \geq p_1 + p_2 \log_{2}\frac{p_1+p_2}{2}$, but the coefficient for the right side does not align correctly if I want to argue the convexity of f(x) = $x\log_{2}x$. Note that the right side occurs form having H(X) - H(X') = $-p_1\log_{2}p_1 - p_2\log_{2}p_2 + \frac{p_1+p_2}{2} \log_{2}\frac{p_1+p_2}{2} + \frac{p_1+p_2}{2} \log_{2}\frac{p_1+p_2}{2}$ How can I go about this? Mar 10, 2019 at 23:14
• Right, so, by convexity of $x\log x,$ you have $$\frac{(p_1 + p _2)}{2} \log \frac{p_1 + p_2}{2} \le \frac{1}{2} \left( p_1 \log p_1 + p_2 \log p_2\right),$$ which finishes the job. That said, I think leonbloy's suggestion is a whole lot cleaner and thus better. Mar 11, 2019 at 18:41

Another way, which looks elegant to me, but it requires you to know this (useful, and not hard to prove) property of entropy: $$H(p)$$ is a concave function of the distribution $$p$$.
Granted this, consider the two distributions $$p_A=(p_1,p_2, p_3 \cdots p_n)$$ and $$p_B=(p_2,p_1, p_3 \cdots p_n)$$ and let $$p_C = (p_A +p_B)/2$$. Clearly, $$H(p_A)=H(p_B)$$.
Hence, by concavity $$H(X')=H(p_C) \ge \frac{H(p_A)+H(p_B)}{2}= H(p_A)=H(X)$$