How can I prove that the conditional entropy of $X$ given $Y$ is $0$ if and only if $Y = f(X)$? I want to show that:
$$
H(X|Y) = 0 \iff Y=f(X)
$$
Where $H(X|Y)$ is the average conditional entropy of the discrete random variable $X$ over all values of the discrete random variable $Y$, and $f$ is an arbitrary invertible function. $H(X|Y)$ is defined as:
$$
H(X|Y) = \mathbb{E}_{p(y)} [H(X|Y=y)] = \sum_y p(y) H(X|Y=y)
$$
$H(X|Y=y)$ is the conditional entropy of the discrete random variable $X$ given $Y = y$:
$$
H(X|Y=y) = \mathbb{E}_{p(x|y)} [-\log_2{p(x|y)}] = - \sum_x p(x|y) \log_2 (p(x|y))
$$
So:
$$ \begin{align}
H(X|Y) &= - \sum_y p(y) \sum_x p(x|y) \log_2 (p(x|y)) \\
&= - \sum_y \sum_x p(x,y) \log_2 (p(x|y)) \\
&= - \mathbb{E}_{p(x,y)} [\log_2 (p(x|y))]
\end{align}$$
I am aware of these questions and their answers:

*

*Conditional Entropy: if $H[y|x]=0$, then there exists a function $g$
such that $y=g(x)$

*when it is conditional entropy minimized?

*Zero conditional entropy
However, none of them offer a satisfactory and straightforward answer.

It turns out that problem 2.5 in the 2nd edition of the book Elements of Information Theory by Cover & Thomas addresses this problem, although using different wording. Problem 2.5 states:

Zero conditional entropy. Show that if $H(Y|X)=0$, then $Y$ is a function of $X$ [i.e., for all $x$ with $p(x)>0$, there is only one possible value of $y$ with $p(x,y)>0$]

This is actually how I intended to word my question. I've checked the solutions manual for the solution to this problem, but I don't fully understand the proof and would appreciate a bit of explanation. Here is the solution verbatim:
Assume that there exists an $x$, say $x_0$ and two different values of $y$, say $y_1$ and $y_2$ such that $p(x_0,y_1)>0$ and $p(x_0,y_2)>0$. Then $p(x_0) \geq p(x_0,y_1) + p(x_0,y_2) > 0$, and $p(y_1|x_0)$ and $p(y_2|x_0)$ are not equal to $0$ or $1$. Thus
$$ \begin{align}
H(Y|X) &= -\sum_x p(x) \sum_y p(y|x) \log p(y|x) \\
& \geq p(x_0)(-p(y_1|x_0) \log p(y_1|x_0) - p(y_2|x_0) \log p(y_2|x_0)) \\
& > 0,
\end{align}$$
since $-t \log t \geq 0$ for $0 \leq t \leq 1$, and is strictly positive for $t$ not equal to $0$ or $1$. Therefore the conditional entropy $H(Y|X)$ is $0$ if and only if $Y$ is a function of $X$.
 A: It can't be proved because it's not true. Here are a couple counterexamples.
Suppose $p(x,y) = p(x) p(y)$ and $p(x)$ is a delta function, so $X$ always takes a constant value. This implies that $H(X \mid Y) = 0$. However, if $p(y)$ is anything other than a delta function, $Y$ cannot be a deterministic function of $X$. Therefore:
$$H(X \mid Y) = 0 \enspace {\not\!\!\!\implies} Y = f(X)$$
Conversely, consider a case where $Y=f(X)$ and $f$ is noninvertible over the support of $p(x)$ (e.g. $p(x)$ could be uniform and $f$ could be a constant function). That is, we have a non-zero probability of drawing multiple values of $X$ that are mapped to the same value of $Y$. This implies that $H(X \mid Y) \ne 0$. Therefore:
$$Y = f(X) \enspace {\not\!\!\!\implies} H(X \mid Y) = 0$$
A: I'll give you some hints.
The fact $p(x_0) = \sum_yp(x_0,y)$ gives you the bound on $p(x_0)$.
The fact $-t\log t \geq 0$ for $0 < t <1$ allows you to say that the sum over all $x,y$ is bigger than the sum over only $x_0,y_1, y_2$ as you're summing positive quantities.
Then you're multiplying 2 strictly positive quantities, so it's bigger than $0$.
But you assumed it was zero, contradiction! CQFD.
