= Solution
A <discrete memoryless channel> is specified by discrete input and output <alphabets> and a transition <probability> $W(y|x)$, with $W(y|x)\geq0$ and $\sum_yW(y|x)=1$. Its successive outputs are conditionally independent given the inputs, with the same transition rule at every use:
$$
\Pr(Y_1=y_1,\ldots,Y_n=y_n\mid X_1=x_1,\ldots,X_n=x_n)
=\prod_{j=1}^nW(y_j|x_j).
$$
Operationally, its <channel capacity> is the supremum of communication rates in <bits> per use attainable by increasingly long block codes with decoding error <probability> tending to zero. For finite <alphabets>, the equivalent Shannon characterization is
$$
C=\max_{P_X}I(X;Y),\qquad
I(X;Y)=H(Y)-H(Y|X),
$$
where $H$ is <Shannon entropy>, $H(Y|X)$ is classical <conditional entropy>, and the maximization is over the input <probability distribution>.
For the channel in question, the transition <matrix>, with input symbols indexing rows, is
$$
W=\begin{pmatrix}
2/3&1/3&0\\
0&2/3&1/3\\
1/3&0&2/3
\end{pmatrix}.
$$
Every row has the same <Shannon entropy>, namely the <binary entropy> $h_2(1/3)$. Consequently $H(Y|X)=h_2(1/3)$ for every input <probability distribution>. Since the output has three symbols, the <maximum entropy on a finite alphabet> gives
$$
I(X;Y)\leq\log_2 3-h_2(1/3).
$$
Choose a uniform input. Each column of $W$ sums to one, so $P_Y(y)=1/3$ for every output symbol and the upper bound is attained. Finally
$$
h_2(1/3)=-\frac13\log_2\frac13-\frac23\log_2\frac23
=\log_2 3-\frac23.
$$
Thus the <cyclic ternary channel capacity> is
$$
\boxed{C=\frac23\text{ bits per channel use},}
$$
achieved by a uniform input <probability distribution>. This is a <weakly symmetric channel capacity> calculation: the <matrix> rows are permutations and the column sums agree. The channel is not the usual ternary symmetric-error channel, since an error has only one possible changed output for each input.
Back to article page
