# Exercise 11.7 in Nielsen & Chuang and basic properties of Shannon entropy

I apologize in advance if this question is trivial, I'm aware I'm a total beginner in this field. This is the exercise I would like to solve:

As to the first point, what I get is that one should write the conditional entropy in the form:

$$H(Y\vert X) =H\left(\pi(x,y)\vert\vert\omega(x,y)\right) =\sum_{x,y} \pi(x,y)\,\log \frac{\pi(x,y)}{\omega(x,y)}\,,$$

with $$\pi(x,y)$$ and $$\omega(x,y)$$ both non negative and summing to $$1$$ (I'd say $$\omega(x,y)$$ summing to less than $$1$$ would be fine), since this would imply non negativity. I was not able to do this part.

However, $$H(Y\vert X)\ge0$$ can also be obtained by observing, as the authors have already done in Theorem 11.3, that

$$H(Y\vert X)=-\sum_{x,y} p_{XY}(x,y)\,\log \frac{ p_{XY}(x,y)}{p_X(x)} =-\sum_{x,y} p_{XY}(x,y)\,\log p_{X\vert Y}(x\vert y)\,,$$

which is a sum of non-negative terms, due to $$p_{X\vert Y}(x\vert y)\le 1$$, hence $$-\log p_{X\vert Y}(x\vert y)\ge0$$. On this ground, they conclude that "equality [holds] if and only if $$Y$$ is a deterministic function of $$X$$". I would also like to get a better insight into such necessary and sufficient condition for $$H(Y\vert X)=0$$. My line of reasoning would be more or less as follows. The sum above is just on those $$x,y$$ such that

$$p_{X Y}(x, y)={\rm prob}[X^{-1}(x) \cap Y^{-1}(y)]>0\,.$$

and on such pairs we get $$p_{X\vert Y}(x\vert y)\le 1$$, that is

$${\rm prob}[X^{-1}(x) \cap Y^{-1}(y)]={\rm prob}[X^{-1}(x)]\,.$$

In our context, this should translate into $$X^{-1}(x) \cap Y^{-1}(y)=X^{-1}(x)$$, i.e., $$X^{-1}(x)\subset Y^{-1}(y)$$. Then, for $$x$$ such that $$p_X(x)>0$$, one would have $$X^{-1}(x)\subset Y^{-1}(y)$$ for some (unique) $$y$$. Finally, one could set $$f(x)=y$$, and this would yield $$Y=f(X)$$.

So my questions are:

• How would you address the first point?
• Is my line of reasoning on how to saturate the inequality more or less acceptable?, and, even if yes, how would you do that?, are there simpler/better/more general ways to achieve such result?, maybe further characterizations?

PS (a very minor quibble, as a sidenote): is it correct to call $$p(x)p(y)$$ a probability distribution? I'm no expert in probability theory either.

• Yesterday I posted a comment suggesting an approach to this question, but then upon further consideration decided that it wasn't a helpful suggestion. Maybe it will be a forehead slapper, but I'm actually not sure what the authors are going for with this question when I interpret it literally. Commented Apr 6 at 12:53
• it's better to focus each post on a single question. That helps better tailor answers and improves reusability of posts. Here that might mean for example editing the post to focus it on on the first question, and ask the second one in a separate post
– glS
Commented Apr 6 at 14:12
• I'm not sure I understand your question. You say you were not able to write $H(Y|X)$ as in the first equation. But then isn't your second equation in just that form?
– glS
Commented Apr 6 at 14:25
• @John Watrous. Thank you very much. Btw, if you are who I presume you are, I'm very honoured to "meet" you, since I just studied representations of quantum channels from your book (your exposition is outstanding). I managed to read your previous comment before going to sleep. I tried to gauge the problem with my ignorance, and found out that a flat distribution may work; but, as far as I'm able to do, not always. So that strategy doesn't solve the above problem — unless someone is able to do some wise adjustment, that is. Commented Apr 6 at 17:25
• @glS. Thank you very much. If you think that splitting the question may result in an improvement, and if you assure me that splitting it now would still be admissible (after all, it has already been read and evaluated), I will immediately edit it accordingly. As per your question, in the second equation $H(Y\vert X)$ is expressed as minus the expectation value of $\log (p(x,y)/p(x))$ — also, as a sidenote, the sum of $p(x)$ over $x$ and $y$ could be larger than $1$. Commented Apr 6 at 17:30

It's just a thought experiment inspired by John Watrous's deleted comment. Suppose we have a probability distribution $$p(x,y)$$ and we want to approximate it with $$q(x,y)$$. Suppose that we know $$p(x)$$, but we don't know anything about $$p(y|x)$$. So, the best we can do in this case is guess $$Y$$. This is equivalent to saying that any of the $$n$$ outcomes of $$Y$$ are equally likely even if we observed $$X$$. Hence, in our attempt to approximate $$p(x,y)$$, we will assume that $$Y$$ is a uniformly distributed random variable with a probability of each outcome $$\frac {1}{n}$$. Then our approximation $$q(x,y)$$ is the joint probability distribution of $$X$$ and $$Y$$ given by $$q(x,y) = \frac{1}{n}p(x)$$.

Let's now compare how well $$q(x,y)$$ approximates the true $$p(x,y)$$. This is done by computing the relative entropy between them: \begin{align} H(p(x,y)||q(x,y))&=H\left(p(x,y)\Big|\Big|\frac{p(x)}{n}\right)\\ &=\sum_{xy}p(x,y)\log\frac{p(x,y) \cdot n}{p(x)}\\ &= \sum_{xy}p(x,y)\log\frac{p(x,y)}{p(x)} +\sum_{xy}p(x,y)\log n\\ &= \sum_{xy}p(x,y)\log p(y|x) + \log n \\ &= -H(Y|X) + \log n. \end{align}

Now, recall that $$H(Y|X) \leq H(Y) \leq \log n$$. The first inequality can be understood by realizing that there is less uncertainty about $$Y$$ because we learn something about it from the given $$X$$. Using these inequalities, we can deduce that $$-H(Y|X) \geq -\log n$$, and it follows that $$H(p(x,y)||q(x,y)) \geq 0$$. We can also rewrite the above as $$H(Y|X) = \log n - H\left(p(x,y)\Big|\Big|\frac{p(x)}{n}\right).$$

Let's continue the thought experiment. Suppose that while designing our guess model $$q(x,y)$$, we decide that $$Y$$ has $$n=1$$ equally likely outcomes, so we fix $$n = 1$$. This means that $$Y$$ has only one outcome, which occurs with the probability $$\frac{1}{1}=1$$. With $$n$$ fixed to $$1$$, the joint probability distribution of $$X$$ and $$Y$$ is $$q(x,y) = \frac{1}{1}p(x)$$. Hence, we have: \begin{align} H(p(x,y)||q(x,y)) &= H\left(p(x,y)\Big|\Big|\frac{p(x)}{1}\right)\\ &= -H(Y|X) + \log 1\\ &= -H(Y|X). \end{align} Therefore, we end up with $$$$H(p(x,y)||q(x,y)) = H(p(x,y)||p(x)) = -H(Y|X).$$$$ How does relative entropy, which is positive, equal something negative? The equation above holds if and only if the true probability distribution of $$Y$$ has indeed only one outcome, i.e., $$Y$$ is a deterministic function (could be a constant, for example). Observe that $$p(x,y) = p(x)$$ for the converse statement. Therefore $$H(p(x,y)||q(x,y)) = -H(Y|X) = 0$$.

Nielsen and Chuang suggest writing $$H(Y|X)$$ as a relative entropy of two probability distributions. If we follow directly the definition that you wrote in your question, we get: \begin{align} H(Y | X):&=-\sum_{x,y} p(x,y)\,\log \frac{ p(x,y)}{p(x)}\\ &=-H(p(x,y)||p(x)). \end{align} This is puzzling because we expect both $$H(Y|X)$$ and $$H(p(x,y)||p(x))$$ to be positive. However, we have already seen that the actual meaning of the equation above is $$H(p(x,y)||p(x)) = H(p(x,y)||q(x,y))$$ where the true distribution of $$Y \sim U(n=1)$$, i.e., $$Y$$ is a deterministic function. So, clearly, for an arbitrary random variable $$Y$$, the equation above is simply incorrect unless $$Y$$ is a deterministic function.

Furthermore, without any context, the notation $$H(p(x,y)||p(x))$$ is also incorrect because $$p(x,y)$$ and $$p(x)$$ may not share the same probability space.

So, this already suggests that doing the computation similar to $$H(Y:X) = H(p(x,y)||p(x)q(x))$$ but for $$H(Y|X)$$ is a bit problematic as we start to run into notational or contextual problems.

One could also hack the definition of the relative entropy and write $$H(p(x,y)||p(x,y)p(y|x))$$, which will evaluate to $$H(Y|X)$$, but the second argument is not a probability distribution.

Therefore, the crude baseline of trying to express $$H(Y|X)$$ in terms of relative entropy is probably the following: $$H\left(p(x,y)\Big|\Big|\frac{p(x)}{n}\right) = -H(Y|X) + \log n.$$

• Thanks a lot. In order to answer, rather than editing the question, I will add an "answer" my own question hereafter, then we can discuss, if you want. Hope this is not against the rules, otherwise I apologize, and will immediately delete my post. Commented Apr 7 at 22:23
• Yes, please post your results. I'm curious to know the solution to this problem. Commented Apr 7 at 22:25
• Ok, done. But I'm not sure they deserve the name of "results", and my understanding is that they do not yield a solution. Commented Apr 7 at 23:22

If my calculations are not completely off the mark, the strategy of employing a flat distribution as our $$\tilde p(y)$$ sometimes works (I'm adding a tilde to make clear that it has nothing to do with $$p_{XY}$$, and its marginals). As far as I understand, the critical issue should be that we have no control over the outcome: either we are lucky, or not.

Nielsen & Chuang show that $$H(p(x)\vert \vert q(x))$$ is non negative by assuming $$p, q\ge0$$ and summing to $$1$$; by the same line of reasoning they employ, we may weaken the condition over $$q$$ to $$\sum_x q(x)\le1$$. As far as I understand, this sum should have at least the same support as the sum for $$p$$. If I'm correct on this point, in the case of our concern we end up with a constraint, which is the core issue. (On the other hand, we are dealing just with a sufficient condition, not with a necessary and sufficient one.)

Now consider the relative entropy of $$p_{XY}(x,y)$$ wrt $$p_X(x) \tilde p(y)$$, with $$\tilde p(y)=t$$, $$0, so that

$$H(p_{XY}(x,y)\vert \vert t p_X(x)) =\sum_{x,y} p_{XY}(x,y)\,\log p_{X\vert Y}(x\vert y) -\log t=-H(X\vert Y)-\log t\,.$$

If we try to impose that the above object is equal to the conditional entropy, we get something like

$$t=\exp(-2 H(X\vert Y))\,.$$

However, playing by the above rules, we have the constraint $$t\sum_y= \sum_{x,y} p_X(x)\tilde p(y) \le 1$$.

• We have to have $\sum_x q(x)=1$ and $\sum_{y}\tilde{p}(y)=1$. Furthermore, the way you define $t = \exp(-2H(X|Y))$ makes $t$ a random variable because now it is a function of $Y$. Commented Apr 8 at 0:28
• you could play around with $\tilde{p}(y)$ and find some other distribution besides it being a uniform distribution, but with the approach I outlined the essence will be the same. Perhaps an alternative way is trying to express $H(Y|X)$ as the sum of relative entropies. But in either case, I suspect that it will not be the structure like in the case of $H(Y:X)$ Commented Apr 8 at 0:32
• I may be very well wrong, and in several respects, but, as far as I understand, $𝑡$ is a number, determined by the number $𝐻(𝑋\vert 𝑌)$, determined by the assigned random variables $𝑋,𝑌$. Namely, it is the only number such that you may have $𝐻(𝑝_{𝑋𝑌}(𝑥,𝑦)\vert\vert 𝑡 𝑝_{𝑋}(𝑥))=𝐻(𝑋|𝑌)$. But the relative entropy at LHS is $\infty$ unless the support of $(𝑥,𝑦)\mapsto 𝑝_{𝑋,𝑌}(𝑥,𝑦)$ is a subset of the support of $(𝑥,𝑦)\mapsto 𝑡𝑝_𝑋(𝑥)$. In other words, it's not up to us to decide which values $𝑦$ are taken by our flat function, which then may not be a "probability". Commented Apr 8 at 9:18
• What do you think?, if you are still interested in investigating this problem, of course… Commented Apr 8 at 10:39