An algebraic, analytic, and algorithmic investigation on the capacity and capacity-achieving input probability distributions of finite-input-finite-output discrete memoryless channels

In this paper, we investigate the capacity and capacity-achieving input probability distributions (IPDs) of finite-input-finite-output discrete memoryless channels (DMCs). In the general respect, we establish a novel and simple characterization for the capacity-achieving IPDs of a DMC, which is equivalent to the conventional Kuhn-Tucker conditions. We then prove a conjecture of Majani and Rumsey, which claims that every probability component of each capacity-achieving IPD of a DMC with positive capacity is less than 1 - e(-1), where e = 2.71828182... is the base of natural logarithms. It remains an open problem whether there exists an explicit closed-form solution for the capacity and capacity-achieving IPDs of a general finite-input-finite-output DMC, except for the two-input-two-output DMC. In the algebraic respect, we demonstrate that there does not, in general, exist an algebraic solution for the capacity-achieving IPDs of an m-input-n-output DMC for any m >= 2 and any n >= 3. In the analytic respect, however, we can obtain an explicit closed-form analytic solution, represented as an infinite series, for the capacity-achieving IPD of a two-input-three-output DMC. We also provide a formula for the average capacity of weakly symmetric DMCs and show-that the average capacity in nats per channel use of the n-input-n-output weakly symmetric DMCs increases for n >= 2 but has a finite limit of 1 -> gamma as n -> infinity, where gamma = 0.57721566... is Euler's constant. In the algorithmic respect, the convergence of the Arimoto-Blahut algorithm is proved in a direct and elementary way. A new and simple iterative algorithm for calculating a capacity-achieving IPD is then proposed, which is provably convergent for all DMCs with positive transition probabilities. Finally, the characterization and determination of the set of all capacity-achieving IPDs of a DMC are addressed.