# Question 9

Regarding Q2.i of the 2014 exam: For part (a) I don’t understand why bistochastic is important; my solution is simply $$H(Y|X=x) = H(q)$$ for each $$x$$, so $$H(Y|X) = H(q)$$.
For part (b) I got an answer $$\log(3) - H(q)$$ but my argument is not that convincing: solve $$p(y|x)p(x) = \{1/3, 1/3, 1/3\}$$ but $$p(y|x)$$ may not be invertible.
For part (b): That’s right, and I think a good way to see find it is to first compute an upper bound of $$\log 3 - H(q)$$, then show it can be achieved. We know the classical capacity is given by the maximum over input distributions of $$I(X:Y)$$. But for any $$X$$, we have $I(X:Y) = H(Y) - H(Y|X) = H(Y) - H(q) \leq \log 3 - H(q)$ since $$H(Y)\leq \log 3$$ as the Shannon entropy of a random variable with three values. In order to achieve equality, we need to choose an input distribution so that the output distribution is uniform. But in fact, a uniform input distribution will work: if $$p(x) = \frac{1}{3}$$ for each value of $$x$$, then $p(y) = \sum_x p(y|x) p(x) = \frac{1}{3} \sum_x p(y|x) = \frac{1}{3}$ since $$\sum_x p(y|x)$$ is the sum of one of the columns of the matrix $$(p(y|x))_{x,y}$$ which is $$q_1 + q_2 + q_3 =1$$ for each $$y$$. So a uniform input distribution yields a uniform output distribution, and gives $$H(Y) = \log 3$$. Thus, the capacity is given by $$\log 3 - H(q)$$.
Note: there was an error in the first version of this answer; I had mistakenly written $$I(X:Y)$$ as $$H(X) - H(Y|X)$$. Thanks to the asker for pointing out my error.