An Algebraic, Analytic, and Algorithmic Investigation on the Capacity and Capacity-Achieving Input Probability Distributions of Finite-Input– Finite-Output Discrete Memoryless Channels

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> 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 <emphasis><formula formulatype="inline"><tex>1-e⁻¹</tex></formula></emphasis>, where <emphasis><formula formulatype="inline"><tex>e=2.71828182…</tex></formula></emphasis> 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 <emphasis><formula formulatype="inline"><tex>m</tex></formula></emphasis>-input–<emphasis><formula formulatype="inline"><tex>n</tex></formula></emphasis>-output DMC for any <emphasis><formula formulatype="inline"><tex>m≥ 2</tex></formula></emphasis> and any <emphasis><formula formulatype="inline"><tex>n≥ 3</tex></formula></emphasis>. 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 <emphasis><formula formulatype="inline"><tex>n</tex></formula></emphasis>-input–<emphasis><formula formulatype="inline"><tex>n</tex></formula></emphasis>-output weakly symmetric DMCs increases for <emphasis><formula formulatype="inline"><tex>n≥ 2</tex> </formula></emphasis> but has a finite limit of <emphasis><formula formulatype="inline"> <tex>1-γ</tex></formula></emphasis> as <emphasis><formula formulatype="inline"> <tex>n→ ∞</tex></formula></emphasis>, where <emphasis><formula formulatype="inline"> <tex>γ =0.57721566…</tex></formula></emphasis> 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. </para>