# Confusion in calculation of conditional entropy

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.

• 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)$.
– whuber
Oct 31, 2015 at 18:06
• 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. Nov 1, 2015 at 13:52
• Ah nevermind, wrong log... Nov 1, 2015 at 14:36