Uniqueness of the distribution maximizing the channel capacity

Question

Setting: We look at a discrete memoryless channel which takes an input probability distribution acting over symbols in $\mathcal{X}$ to an output probability distribution over symbols in $\mathcal{Y}$.

To simplify notation, let the input symbols be labelled as $[1,2, ..., N]$ where $N = |\mathcal{X}|$ and the output symbols be labelled as $[1,2, ..., M]$ where $M = |\mathcal{Y}|$. The input probability vector of size $1\times N$ is denoted by $p$ and the output probability vector of size $1\times M$ is denoted by $q$. The stochastic matrix $Q$ of size $N\times M$ is the channel matrix i.e. $q = Qp$. The capacity of this channel is given by

$$C = \max_{p}\sum_{i=1}^N\sum_{j=1}^M p_iQ_{ij}\log\frac{Q_{ij}}{q_j}$$

Let the distribution that achieves $C$ be $p^*$.

Conjecture: If $p^*$ does not use the entire input alphabet in $X$ i.e. $p^*_i = 0$ for some component $i$, then it is guaranteed that there exists another distribution $\tilde{p}^* \neq p^*$ which also achieves the capacity of the channel.

Can anyone help prove this or show a counterexample?

Answer 1

This conjecture is false. Here is a counterexample.

Suppose we have a binary symmetric channel:

$x_1 \rightarrow y_1$ with probability $1-\epsilon$ and $y_2$ with probability $\epsilon$,

$x_2 \rightarrow y_2$ with probability $1-\epsilon$ and $y_1$ with probability $\epsilon$.

Now add a third input $x_3$ that goes to $y_1$ and $y_2$ with probability $\frac{1}{2}$ each.

Then the optimal input probability distribution is $(\frac{1}{2}, \frac{1}{2}, 0)$.

Proof: Let $X$ be the random variable describing the input, and $Y$ be the random variable describing the output. The capacity $C = H(Y) - H(Y|X)$, where $H(Y)$ is the entropy of $Y$, and $H(Y|X)$ is the conditional entropy of $Y$ given $X$.

If you have an input distribution $(p_1, p_2, p_3)$ for $X$, you can replace it by the distribution $(p_1+p_3/2, p_2 + p_3/2, 0)$. This keeps $Y$ the same, so $H(Y)$ is unchanged, and it reduces $H(Y|X)$. Thus, capacity strictly increases.