Question 9

from Answers to questions

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 (a): I agree, you only need that the rows are permutations of each other for this part. I think the hint might be to remind you of properties of this type of channel that were discussed during the class that year; I think we spent less time on classical channels this year.

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.