1
$\begingroup$

Find the expression for the conditional entropy $H(Y|X)$ as a relative entropy between two probability distributions. Use this expression to deduce that $H(Y |X)≥0$, and to find the equality conditions.

This is given in Exercise 11.7, Page 507-508, Chapter 8, Quantum Computation and Quantum Information by Nielsen and Chuang

The relative entropy of two probability distributions $p(x)$ and $q(x)$ is defined as, $H(p(x)||q(x))=\sum_xp(x)\log\frac{p(x)}{q(x)}$, where the probability distributions $p(x)$ and $q(x)$ must be defined over the same set.

The mutual information $H(X:Y)$ can be expressed as the relative entropy of two probability distributions, as \begin{align} H(X:Y)&=H(X)+H(Y)-H(X,Y)\\ &=-\sum_xp(x)\log p(x)-\sum_y p(y)\log p(y)+\sum_{x,y}p(x,y)\log p(x,y)\\ \text{Since we have }& p(x)=\sum_yp(x,y)\text{ and }p(y)=\sum_xp(x,y)\\ H(X:Y)&=\sum_{x,y}p(x,y)\log\frac{p(x,y)}{p(x)p(y)}=H(p(x,y)||p(x)p(y)) \end{align}

My Attempt

The conditional entropy $H(Y|X)$ between two probability distributions is defined as, $$ H(Y|X)=\sum_x p(x)H(Y|X=x)=\sum_xp(x).-\sum_yp(y|x)\log p(y|x)\\ =-\sum_{x,y}p(x)p(y|x)\log p(y|x)=-\sum_{x,y}p(x,y)\log p(y|x)\\ \text{Since we have } p(y|x)=\frac{p(x,y)}{p(x)}\\ H(Y|X)=-\sum_{x,y}p(x,y)\log \frac{p(x,y)}{p(x)}=\sum_{x}\sum_{y}p(x,y)\log \frac{p(x)}{p(x,y)}\\ =\sum_{x}\sum_{y}p(x,y)\log \frac{p(x)}{p(x,y)} $$

Can I proceed further to obtain that the conditional entropy $H(Y|X)$ as a relative entropy between two probability distributions ?


Or can I write as, $$ H(X:Y)=H(p(x,y)||p(x)p(y))=H(Y)-H(Y|X)\\ \implies H(Y|X)=H(Y)-H(X:Y)=H(Y)-H(p(x,y)||p(x)p(y)) $$

$\endgroup$
5
  • $\begingroup$ what's the required form exactly? Isn't the last expression you write already written in terms of a relative entropy, as it's $H(p \| p_X\otimes I)$ (I'm not sure what notation you use for this; I just mean with $p_X\otimes I$ the function $(x,y)\mapsto p_X(x)$ with $p_X(x)\equiv\sum_y p(x,y)$ the marginal distribution)? $\endgroup$
    – glS
    Dec 23, 2022 at 11:04
  • $\begingroup$ Its just that the second distribution is not normalised. If you want to normalise it then you have to subtract something from the conditional entropy. $\endgroup$
    – Rammus
    Dec 23, 2022 at 20:31
  • $\begingroup$ @glS The question is "find an expression for the conditional entropy $H(Y |X)$ as a relative entropy between two probability distributions". So is it $H(Y|X)=-\sum_{x,y}p(x,y)\log\frac{p(x,y)}{(p_X\otimes I)(x,y)}=-H(p(x,y)||(p_X\otimes I)(x,y))$, where $(p_X\otimes I)(x,y)=p(x)$ ? $\endgroup$
    – Sooraj S
    Dec 24, 2022 at 11:58
  • $\begingroup$ @Rammus you mean then to obtain $H(Y|X)=H(Y)-H(p(x,y)||p(x)p(y))$ ? $\endgroup$
    – Sooraj S
    Dec 24, 2022 at 12:01
  • $\begingroup$ No, that's not correct, see below. $\endgroup$
    – Rammus
    Dec 24, 2022 at 14:50

1 Answer 1

1
$\begingroup$

The relative entropy is defined as $$ D(p\|q) = \sum_x p(x) \log\left(\frac{p(x)}{q(x)}\right). $$ The conditional entropy of $Y$ given $X$ for two random variables $X$ and $Y$ is defined as $$ H(Y|X) = -\sum_{xy} p(x,y) \log(p(y|x))\,. $$

Now consider a distribution $p$ which is the joint distribution for two random variables $X$ and $Y$. And consider also a distribution $q$ which is defined as $q(x,y) := \frac{p(x)}{d_Y}$ where $d_Y$ is the number of outcomes for the random variable Y. Effectively $q$ is a product distribution of the marginal distribution of $X$ together with a uniform distribution over the outcome space of $Y$. Crucially $q$ is a normalized distribution which is what the question seems to be asking for. Then $$ \begin{aligned} -D(p\|q) &= -\sum_{x,y} p(x,y) \log \left(\frac{p(x,y)}{p(x)/d_Y}\right) \\ &= -\sum_{x,y} p(x,y) \left(\log\left(\frac{p(x,y)}{p(x)}\right) + \log(d_Y)\right) \\ &= -\sum_{x,y}p(x,y) \log(p(y|x)) - \sum_{x,y}p(x,y) \log(d_Y) \\ &= H(Y|X) - \log(d_Y) \end{aligned} $$ So overall $$ H(Y|X) = -D(p(x,y) \| p(x)/d_Y) + \log(d_Y)\,. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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