# What discrete memoryless channels have zero capacity?

Let $W$ be a $n \times n$ square (discrete memoryless) channel matrix (hence stochastic) and let $p^{(W)}$ be a capacity-acheiving distribution for $W$. Let $1$ denote the vector of all ones. If we consider (the entries of) $W$ as variable, what is the solution space of

$p^{(W)}W = \frac{1}{n}1$?

Alternatively (not, I think, equivalently), what channels $W$ have zero capacity?

Of course I know that the completely noisy channel $W_{jk} = 1/n$ has zero capacity--I am interested in the rest of the story.

-
I must be misunderstanding something. Why that condition is equivalent with zero capacity? Doesn't the completely noiseless channel also verify it? –  leonbloy Nov 30 '12 at 19:45
Edited to remove the question's ambiguity. –  S Huntsman Dec 6 '12 at 13:00

There are two properties here for a discrete memoryless $n\times n$ channel , and they are not equivalent: a) zero capacity and b) capacity-achieving distribution has equiprobable outputs

a) The channel has zero capacity iff $p(y_j | x_i) = g(j)$, i.e if the transition probabilities depends only on the ouput (the Markov matrix is a single row repeated $n$ times)

Proof:

($\Leftarrow$) The condition readily implies $p(x_i | y_j) = \frac{p(y_j | x_i) p(x_i)}{ p(y_j)}$, hence $H(X|Y) = H(X) \Rightarrow I(X;Y)=0$ for any input distribution, hence $C = 0$

($\Rightarrow$) Suppose that the condition is violated, then for some $j$ there exist two inputs $i_a$, $i_b$ ,with $p(y_j|x_{i_a}) > p(y_j|x_{i_b})$. Just by using a source that produces those two inputs with equal probability we attain $H(X|Y) < H(X) \Rightarrow C>0$

b) The second part of the problem seems more difficul to answer in general. A sufficient (perhaps non-necessary) condition is that the matrix is weakly-symmetric: all the rows differ only on a permutation, and all columns have the same sum. In this case, it's clear that $H(Y | X=x) = H(q)$ does not depend on $x$ ($q$ is a row), and hence $I(X;Y) = H(Y) - H(q)$ is maximized by an equiprobable output, which is attained (because of all columns sum the same) by an equiprobable input. Notice that this includes both the completely noisy channel, the completely noisless channel, the binary simmetric channel, the "noisy typewriter" channel, as well as generalizations of this one, as "assymetric noisy typerwriter", also with more than two outputs (say, 0.7 probability of hitting the right key, 0.2 of hittting the next, 0.1 of hitting the previous).

Updated: By deriving $I(X|Y)$ with respect to $p_y$ it can be shown that the necessary condition to attain a local extreme at $p_y=1/n$ is that the transition matrix has constant "row entropy" ($H(q)$ above). This cover much more matrix space ample than requiring each row to be a permutation of the others (weakly symmetric), but it's not enough: one must also that there exists some valid $p_x$ that verifies $p_y = 1/n = p_x A$.

Of course, in this case the capacity is $C=\log(n) - H(q)$

As an example:

>>> A =[.1, .5, .4 ; .5, .4, .1 ; .19382, .2 ,.60618]
A =
0.10000   0.50000   0.40000
0.50000   0.40000   0.10000
0.19382   0.20000   0.60618

>>> y = [1/3,1/3,1/3];
>>> x=y*inv(A)
x =  0.11681   0.49145   0.39174
C= -A .* log(A);
>>> C * ones(3,1) % entropy of each row
0.94335
0.94335
0.94335
>>>  ixy = (log(3) - (C*ones(3,1))(1) )/log(2)
ixy =  0.22400

-