2
$\begingroup$

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?

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.