= Solution
The <Shannon second coding theorem> states that the operational <channel capacity> of a finite <discrete memoryless channel> is $C=\max_{p(x)}I(X:Y)$: rates below this maximum admit block codes with error tending to zero, and rates above it cannot have vanishing error. For this channel the preceding calculation gives
$$
I(X:Y)=H(Y)-H(q)\leq\log_2 3-H(q),
$$
using <maximum entropy on a finite alphabet>. The transition matrix is a <doubly stochastic matrix>. Therefore the uniform input has uniform output: $p(y)=\frac13\sum_xp(y\mid x)=1/3$. It achieves the entropy upper bound, and hence
$$
\boxed{C=\log_2 3-H(q)\quad\text{bits per channel use}.}
$$
Equivalently this is the <weakly symmetric channel capacity> theorem: permutations of a common row and equal column sums make the uniform input optimal. If $q$ is uniform, the output contains no information about the input and the formula gives zero.
Back to article page
