# Shannon entropy property proof

X and Y are two discrete random variables having $n$ possible values : $x_{i}(1\leq i \leq n)$ and $y_{j} (1\leq j \leq n)$. The probability mass function of X is given by $$Pr(X=x_{i}) = p_{i}, 1\leq i\leq n$$ And the conditional probability mass function of Y with given X is $$Pr(Y=y_{j}|X=x_{i}) = a_{i,j}$$ Where $$a_{i,j}\geq 0, \sum_{i=1}^{n} a_{i,j} = \sum_{j=1}^{n} a_{i,j} = 1$$ I need to prove that $H(Y)\geq H(X)$ Where $H(X)$ is the Shannon entropy: $H(X) = -\sum_{i}p_{i}\log{p_{i}}$

My thoughts so far: \begin{align} Pr(Y=y_{j}) &= \sum_{i=1}^{n}Pr(Y=y_{j}|X=x_{i})Pr(X=x_{i})\\ &= \sum_{i=1}^{n} a_{i,j}p_{i} = p_{j} \end{align} $$\rightarrow H(Y) = -\sum_{j=1}^{n}p_{j}\log{p_{j}} = -\sum_{j=1}^{n} a_{i,j}p_{i}\log{p_{j}}$$

However, I can't really conclude anything from this... Any ideas?

• You've mistakenly entered $p_j$ for $\Pr(X=x_i)$. – Einar Rødland May 30 '15 at 22:16
• So I did, I fixed it now – brvh May 31 '15 at 9:42
• After the fix, the rest of the derivation is no longer valid since $y_j$ does not have probability $p_j$. – Einar Rødland May 31 '15 at 11:05

## 2 Answers

Let us first, for convenience, define the function $l(p)=-p\ln{p}$. This makes the entropy of $X$ expressed as $H(X)=\sum_i l(p_i)$.

For $Y$, we have the probability $$q_j=\Pr(Y=y_j)=\sum_i p_i a_{i,j}$$ which makes $$H(Y)=\sum_j l(q_j)=\sum_j l\left(\sum_i p_i a_{i,j}\right).$$ Because $l$ is concave and $\sum_i a_{i,j}=1$ with all $a_{i,j}\ge 0$, we may use Jensen's inequality to obtain $$l\left(\sum_i p_i a_{i,j}\right) \ge \sum_i a_{i,j} l\left(p_i\right).$$ Summing this over all $j$ gives $$H(Y)\ge\sum_{i,j} a_{i,j} l\left(p_i\right) =\sum_i l(p_i)=H(X).$$

We can also try do partial differentiation of the entropy (which is a scalar) wrt the elements of our matrix A and show that a minimum is achieved (all partial derivatives 0) iff A is diagonal. It would however need some experience with matrix calculus to be viable.