This question is related to this math.se question but I need a bit more guidance.

For two discrete random variables $X,Y$ we define their conditional entropy to be $$H(X|Y) = -\sum_{y \in Y} Pr[Y = y] ( \sum_{x \in X} Pr[X = x | Y = y] \log_2{Pr[X=x|Y=y]}).$$

I would like to show that $H(X|Y) = 0$ if and only if $X = f(Y)$ for some function $Y.$

Can someone help me with this? I don't know how the fact that $X,Y$ are related by a function implies $H(X|Y) = 0$ and vice versa.

  • $\begingroup$ Hint: Since every term is nonpositive, for every y such that Pr[Y = y]>0 you want that Pr[X = x | Y = y].log_2Pr[X=x|Y=y]=0 for every x. When is this possible? You might want to first solve t.log_2(t)=0 for t. $\endgroup$ – Did Aug 21 '15 at 9:35
  • $\begingroup$ @Did The condition Pr [Y = y] > 0 implies $Pr [X = x | Y = y] \in \{0,1\}$ for every $x.$ How does it then imply that $X$ is a function of $Y?$ $\endgroup$ – rwalk Aug 21 '15 at 10:34
  • $\begingroup$ For each y, select the unique x such that Pr[X=x|Y=y]=1 and call it x=u(y). What do you think of the random variable u(Y)? $\endgroup$ – Did Aug 21 '15 at 12:22
  • $\begingroup$ @Did Thanks. That helped! If you care to put this in an answer I am glad to accept it. $\endgroup$ – rwalk Aug 23 '15 at 8:56
  • $\begingroup$ Better idea: you write down a solution and post it as an answer here. After a while, you might even "accept" it (cool, eh?). $\endgroup$ – Did Aug 23 '15 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.