0
$\begingroup$

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^{''})$

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 9, 2019 at 21:33
  • $\begingroup$ 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? $\endgroup$
    – user57753
    Mar 10, 2019 at 23:14
  • $\begingroup$ 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. $\endgroup$ Mar 11, 2019 at 18:41

1 Answer 1

1
$\begingroup$

There are several ways to attack this, some of them pointed by stochasticboy321's comment.

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

$\endgroup$

You must log in to answer this question.

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