The Binomial Channel: On Capacity, Optimal Inputs, and Beta-Binomial Approximation

Technical Summary: The Binomial Channel: On Capacity, Optimal Inputs, and Beta-Binomial Approximation

Problem Statement
This paper investigates the binomial channel, a communication model where the input $X$ is a continuous random variable on the interval $[0, 1]$ and the output $Y$ is a discrete random variable on $\{0, \dots, n\}$, governed by the binomial distribution $P_{Y|X}(y|x) = \binom{n}{y} x^y (1-x)^{n-y}$. The primary objectives are to determine the channel capacity $C(n)$ and to characterize the structure of the capacity-achieving input distribution (CAID), denoted $P_{X^\star}$. A significant challenge addressed is that while the output alphabet is finite, the input alphabet is continuous; consequently, the mutual information is not strictly concave with respect to the input distribution, complicating the proof of uniqueness and the determination of the support size of the optimal input.

Methodology
The authors employ a combination of information-theoretic optimization, estimation theory, and approximation theory:

1. KKT Conditions: The analysis relies on the Karush-Kuhn-Tucker (KKT) conditions to characterize the support of the optimal input. The set of points where the information density equals the capacity ($A_n$) is central to proving discreteness and uniqueness.
2. Estimation-Theoretic Identities: The paper utilizes derivative formulas for information density and properties of the conditional mean $E[X|Y=y]$, establishing its monotonicity.
3. Reference Distribution: A specific reference input $X_r \sim \text{Beta}(1/2, 1/2)$ is introduced. This distribution is the Jeffreys prior for the binomial channel and induces a Beta-Binomial output $Y_r$.
4. Orthogonal Polynomials and Approximation: To bound the support size, the authors utilize the theory of orthogonal polynomials (specifically shifted Chebyshev polynomials) associated with the Beta(1/2, 1/2) distribution. They derive a Parseval-type identity for the $\chi^2$-divergence between a general binomial mixture output and the reference Beta-Binomial output.
5. Minimax Redundancy: Upper bounds on capacity are derived using the minimax redundancy construction of Xie and Barron, while lower bounds are obtained by evaluating mutual information at the reference input $X_r$.

Key Contributions and Results

• Structural Properties of the CAID:

  • Discreteness and Uniqueness: The authors prove that all capacity-achieving distributions are discrete and, crucially, that the CAID is unique. This uniqueness is established by showing that the mutual information is strictly concave over the set of distributions supported on any set of $n+1$ points, combined with the fact that the set $A_n$ has cardinality at most $n+1$.
  • Symmetry and Support: The optimal input is symmetric around $1/2$, and its support necessarily includes the endpoints $\{0, 1\}$.
  • Support Constraints: There is at most one support point in the intervals $(0, 1/n]$ and $[1-1/n, 1)$.

• Capacity Bounds:

  • The paper derives explicit non-asymptotic upper and lower bounds on $C(n)$.
  • These bounds imply the asymptotic behavior: $C(n) = \frac{1}{2} \log \left( \frac{n\pi}{2e} \right) + o(1)$.
  • The lower bound is achieved by the reference input $X_r$, and the gap between the upper and lower bounds vanishes as $n \to \infty$.

• Support Size Bounds:

  • Upper Bound: The classical Witsenhausen-type upper bound of order $n$ is improved to an upper bound of order $n/2$.
  • Lower Bound: The paper establishes a new lower bound on the support cardinality. By proving that the Beta-Binomial output induced by $X_r$ is asymptotically optimal and close to the true capacity-achieving output in relative entropy and $\chi^2$-divergence, and combining this with a finite-mixture approximation lower bound, the authors derive a support size lower bound of order $\Omega(\sqrt{n} \log \log n)$.

• Numerical Results:

  • The authors provide numerical estimates for the CAID and capacity for $n$ up to 350.
  • The results suggest that the support points of the optimal input, when transformed by the cumulative distribution function of the Beta(1/2, 1/2) input, are roughly uniformly spaced.
  • Numerical data for $n \le 350$ appears consistent with a conjecture that the support size scales as $\Theta(n^{3/4})$, though the authors caution that this range may still be in a finite-$n$ regime where asymptotic scaling is not yet fully visible.

Significance
The paper provides a more detailed theoretical picture of the binomial channel, closing gaps regarding the uniqueness and specific structural properties of the optimal input distribution. By establishing that the optimal input is unique and discrete, and by providing tight bounds on the capacity and support size, the work advances the understanding of channels with continuous inputs and finite outputs. The derivation of the $\Omega(\sqrt{n} \log \log n)$ lower bound on the support size represents a significant improvement over previous order-$\sqrt{n}$ bounds, utilizing a novel combination of best-approximation theory and information-theoretic divergence measures. The results also highlight the asymptotic optimality of the Beta-Binomial distribution, linking information theory with Bayesian estimation (Jeffreys prior).