# Uniqueness of the distribution maximizing the channel capacity

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?

• Here you're conflating $X,Y$ (the alphabet) and $X,Y$ (random variables, resp. distributed according to $p$ and $q$, I gather?). Can you confirm what $X,Y$ in $I(X:Y)$ are? – Clement C. May 10 '19 at 21:15
• @ClementC. sorry about that. I have removed the confusing notation. – user1936752 May 10 '19 at 22:08

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.