Consider a classical discrete memoryless channel (DMC). Let $p$ be an input probability distribution and $Q$ be the channel's transition matrix. $q = Qp$ is a valid output probability distribution. The components of $p$ and $q$ are given as $p_i$ and $q_i$ respectively.

The capacity of this channel is given by maximizing the mutual information.

$$I = \max_{p}\left[\sum_ip_i\left(\sum_{j}Q_{ij}\log(Q_{ij})\right) - \sum_{j}q_j\log q_j\right]$$

But, we know (Theorem 2.7.4 in Cover and Thomas, 2006) that $I(p)$ is concave in $p$.

If $I(p)$ is not simply a linear function (i.e. $q = Qp$ is not a trivial relationship) and is differentiable everywhere (seems like a reasonable assumption), does this not imply that the capacity achieving $p$ is unique?

  • $\begingroup$ The capacity is a function of the channel. Given the channel, it has a unique value. Maybe you are asking whether there is a unique maximizer distribution $p$? $\endgroup$ – Yuval Filmus Jul 4 '19 at 7:27
  • $\begingroup$ @YuvalFilmus that's right, my question is about the uniqueness of the capacity achieving distribution $p$. $\endgroup$ – user1936752 Jul 4 '19 at 9:11

I believe the answer is "yes", when $Q$ is square and nonsingular, and "not necessarily", otherwise. See "On the Capacity of a Discrete Channel. I", by Saburo Muroga, Journal of the Physical Society of Japan, Vol. 8, No. 4, July - August 1953, pp 484-494.

You might also be interested in my note on Muroga's paper, in which I attempt to provide an alternate proof of the feasibility of the optimal input probability distribution, in the special case of a binary channel, and to correct what I think is a trivial error in Muroga's paper (although this might simply have been Muroga being too polite to point out a trivial mistake by Shannon), and I also try to simplify a part of Muroga's argument:

"On the Computation of the Shannon Capacity of a Discrete Channel with Noise", S. Cowell, arXiv:1701.08731v2 [cs.IT] [here]1

| cite | improve this answer | |

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.