0

Elements of alphabets $X$ and $Y$ are statistically related. It is known that $H(X)=4$ bits and $H(Y) =11$ bits.

What are a range of variation for a conditional entropy $H(Y|X)$ and $H(X|Y)$ changes from min to max?

Saket Gurjar
  • 1,663
Sultan Akhmetbek
  • 1

1 Answers1

1

Short answers are as following: \begin{align*} \max H(X|Y)&=4,\\ \max H(Y|X)&=11,\\ \min H(X|Y)&=0. \\ \min H(Y|X)&=7, \end{align*} To show the first two equations, first note that $H(Y|X) \leq H(Y)=11$ and $H(X|Y) \leq H(X)=4$. Now, we give an example to show that they are achievable. Suppose that X is a 4 bit random variable, where each bit is uniform and independent of other bits, and Y is a 11 bit random variable, where each bit is uniform and independent of other bits, and also independent of X. This gives $H(X|Y)=4$ and $H(Y|X)=11$.

To show the last two relations, first notice that $H(X|Y)\geq 0$ and moreover $$H(Y|X)=H(X,Y)-H(X)=H(X|Y)+H(Y)-H(X)=7+H(X|Y) \geq 7.$$ Now, we show that these bounds are tight. Suppose, Y is a 11 bit random variable, where each bit is uniform and independent of other bits and X is equal to the first four bits of Y. Then you have $H(X|Y)=0$ and $H(Y|X)=7$.

Mini
  • 373
  • 2
  • 14
  • I think the minima should be 0. My understanding of $X$ and $Y$ being "statistically related" is that they are not independent, but not necessarily deterministic functions of each other. Then, their dependence can be made arbitrarily small. A trivial example is one variable being a die roll outcome and the other being the parity. Given the outcome, parity is determined, but not the other way around. By adjusting the probability space, we can find an example that satisfies the given entropies – curlycharcoal May 30 '20 at 20:53
  • 1
    Well, clearly I have shown that always $H(Y|X) \geq 7$. Hence, it cannot be zero. The example (which contains deterministic mappings) is to show that this minimum (7) is achievable. Your trivial example is not matched with the assumptions of the problem: $H(Y)=11$ and $H(X)=4$. – Mini May 30 '20 at 21:19
  • 1
    I think I had a brainfart earlier. Now thinking about it again, what I was thinking corresponds to the fact that $I(X;Y)$ can be made arbitrarily small, not the conditional entropies. You already showed that implicitly while proving the maxima. Sorry about the confusion – curlycharcoal May 30 '20 at 21:38