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$
3
  • $\begingroup$ You've mistakenly entered $p_j$ for $\Pr(X=x_i)$. $\endgroup$ May 30, 2015 at 22:16
  • $\begingroup$ So I did, I fixed it now $\endgroup$
    – brvh
    May 31, 2015 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$ May 31, 2015 at 11:05

2 Answers 2

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$

You must log in to answer this question.

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