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

Question

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.

Answer 1

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 \begin{equation} H(p(x,y)||q(x,y)) = H(p(x,y)||p(x)) = -H(Y|X). \end{equation} 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.$$

Answer 2

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<t<1$, 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$.