2
$\begingroup$

I'm following a course on Information Theory and came across a problem about conditional entropy that I thought I understood, but when I tried calculating the actual values my results didn't satisfy the simple relation $$H(X,Y) = H(Y | X) + H(X)$$

The problem is as follows: suppose that $$P_X(x) = 1/6$$ $$P_{Y|X}(y|x) = 1/x$$ Here $x = 1, 2, ..., 6$ and $y = 1, 2, ..., x$. Now calculate $H(X)$, $H(Y|X)$ and $H(X,Y)$.

Originally, I thought the answers simply were $\log6$, $\log x$ and $\log 6x$ respectively, which does statisfy the abovementioned relation, but doesn't take into account that $Y$ depends on $X$.

Taking that into account, I started with the simplest one. $$H(X) = - \sum_{x \in \mathcal{X}} P_X(x) \log P_X(x) = 6 \cdot 1/6 \cdot \log 6 = \log 6 \approx 2.58$$

Numerical values are in bits. Obviously this one didn't change from before.

Next:

\begin{align} H(Y|X) &= \sum_{x \in \mathcal{X}} P_X(x) H(Y | X = x) \\ &= \frac{1}{6} \left[ H(Y | X = 1) + H(Y | X = 2) + H(Y | X = 3) + H(Y | X = 4) + H(Y | X = 5) + H(Y | X = 6) \right] \\ &= \frac{1}{6} \left[ \log1 + \log2 + \log3 + \log4 + \log5 + \log6 \right] \approx 1.58 \end{align}

So now we expect $H(X,Y)$ to be about $4.16$ bits.

\begin{align} H(X,Y) &= - \sum_{x \in \mathcal{X}} \sum_{y=1}^x P_{XY}(x,y) \log P_{XY}(x,y) \\ &= \sum_{x \in \mathcal{X}} \sum_{y=1}^x \frac{1}{6y} \log 6y \approx 6.05 \end{align}

Which clearly isn't 4.16 bits. So I thought maybe I evaluated the sum wrongly, and tried another route.

$$H(X,Y) = \sum_{x \in \mathcal{X}} H(Y, X = x)$$

Now we can calculate that $$H(Y,X=1) = - P_{XY}(Y=1, X=1) \log P_{XY}(Y=1, X=1) = \frac{1}{6} \log 6$$

since for $X = 1$ only $Y = 1$ is possible.

Continuing, we have

\begin{align} H(Y, X = 2) &= \frac{1}{6} \log 6 + \frac{1}{12} \log 12 \\ H(Y, X = 3) &= \frac{1}{6} \log 6 + \frac{1}{12} \log 12 + \frac{1}{18} \log 18 \\ H(Y, X = 4) & = \dots \end{align}

Up to $H(Y, X = 6)$. In the end we evaluate $$H(X,Y) = \log 6 + \frac{5}{12} \log 12 + \frac{4}{18} \log 18 + \frac{3}{24} \log 24 + \frac{2}{30} \log 30 + \frac{1}{36} \log 36 \approx 6.05$$

So this is at least consistent, but still doesn't seem right. As you can probably see I'm rather stuck, so any help is appreciated.

$\endgroup$
3
  • $\begingroup$ Make a table displaying the probabilities of $(x,y)$ for every possible $x$ and $y$: that will immediately show the error in your computation of $H(X,Y)$. $\endgroup$
    – whuber
    Oct 31, 2015 at 18:06
  • $\begingroup$ Aah, got it. It should be 1/6x log 6x in the sum, right? Sadly this yields an entropy of 2.89, so I'm still messing up somewhere. $\endgroup$
    – Timsey
    Nov 1, 2015 at 13:52
  • $\begingroup$ Ah nevermind, wrong log... $\endgroup$
    – Timsey
    Nov 1, 2015 at 14:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.