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?

  • $\begingroup$ 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? $\endgroup$
    – Clement C.
    May 10 '19 at 21:15
  • $\begingroup$ @ClementC. sorry about that. I have removed the confusing notation. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.