<p>This conjecture is false. Here is a counterexample.</p>
<p>Suppose we have a binary symmetric channel:</p>
<p><span class="math-container">$x_1 \rightarrow y_1$</span> with probability <span class="math-container">$1-\epsilon$</span> and <span class="math-container">$y_2$</span> with probability <span class="math-container">$\epsilon$</span>,</p>
<p><span class="math-container">$x_2 \rightarrow y_2$</span> with probability <span class="math-container">$1-\epsilon$</span> and <span class="math-container">$y_1$</span> with probability <span class="math-container">$\epsilon$</span>.</p>
<p>Now add a third input <span class="math-container">$x_3$</span> that goes to <span class="math-container">$y_1$</span> and <span class="math-container">$y_2$</span> with probability <span class="math-container">$\frac{1}{2}$</span> each.</p>
<p>Then the optimal input probability distribution is <span class="math-container">$(\frac{1}{2}, \frac{1}{2}, 0)$</span>.</p>
<p>Proof: Let <span class="math-container">$X$</span> be the random variable describing the input, and <span class="math-container">$Y$</span> be the random variable describing the output. The capacity <span class="math-container">$C = H(Y) - H(Y|X)$</span>, where <span class="math-container">$H(Y)$</span> is the entropy of <span class="math-container">$Y$</span>, and <span class="math-container">$H(Y|X)$</span> is the conditional entropy of <span class="math-container">$Y$</span> given <span class="math-container">$X$</span>.</p>
<p>If you have an input distribution <span class="math-container">$(p_1, p_2, p_3)$</span> for <span class="math-container">$X$</span>, you can replace it by the distribution <span class="math-container">$(p_1+p_3/2, p_2 + p_3/2, 0)$</span>. This keeps <span class="math-container">$Y$</span> the same, so <span class="math-container">$H(Y)$</span> is unchanged, and it reduces <span class="math-container">$H(Y|X)$</span>. Thus, capacity strictly increases.</p>

CC BY-SA 4.0
2019-05-11T02:02:04.333Z
2022-10-07T11:17:12.807Z
2022-10-07T11:17:12.807Z
Peter Shor 
<p><strong>Setting:</strong> We look at a discrete memoryless channel which takes an input probability distribution acting over symbols in <span class="math-container">$\mathcal{X}$</span> to an output probability distribution over symbols in <span class="math-container">$\mathcal{Y}$</span>. </p>

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

<p><span class="math-container">$$C = \max_{p}\sum_{i=1}^N\sum_{j=1}^M p_iQ_{ij}\log\frac{Q_{ij}}{q_j}$$</span></p>

<p>Let the distribution that achieves <span class="math-container">$C$</span> be <span class="math-container">$p^*$</span>. </p>

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

<p>Can anyone help prove this or show a counterexample?  </p>

<it.information-theory><proofs><examples>
Uniqueness of the distribution maximizing the channel capacity
user1936752
# Uniqueness of the distribution maximizing the channel capacity

(Asked by: username_0 on 2019-05-10)

**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?

**Tags:** it.information-theory, proofs, examples


---

## 1 answers

### Answer by username_1 on 2019-05-11. Score: 4 | Accepted answer

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.


---

