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

Summary · qwen2.5:32b

The article explores the binomial channel's capacity and identifies that the optimal input distribution is discrete, unique, symmetric around 1/2, and includes the endpoints {0,1}. The study improves the upper bound on support size to order $n/2$ and derives bounds on the channel's capacity, showing $C(n)=\frac{1}{2}\log\frac{n\pi}{2e}+o(1)$, with a lower bound achieved using a beta-binomial distribution.

Suggested post angle

Exploring a new mathematical model in the context of real-time rendering: The Binomial Channel sheds light on capacity, optimal inputs, and beta-binomial approximation.

Excerpt

arXiv:2607.02683v1 Announce Type: new Abstract: We study the binomial channel with input alphabet $[0,1]$ and output alphabet ${0,\ldots,n}$. We investigate its capacity and the structure of the capacity-achieving input and output distributions. Since the output alphabet is finite whereas the input alphabet is continuous, different input distributions may induce the same output distribution; hence, uniqueness and support properties of optimal inputs do not follow from strict concavity arguments. We first establish structural properties of the capacity-achieving input distribution. In particular, we show that it is discrete, unique, symmetric around $1/2$, and contains the endpoints ${0,1}$ in its support. We also derive location constraints and bounds on the probability masses of support points, and improve the Witsenhausen-type upper bound on the support size from order $n$ to order $n/2$. We derive explicit nonasymptotic upper and lower bounds on the capacity $C(n)$. These bounds imply $C(n)=\frac{1}{2}\log\frac{n\pi}{2e}+o(1).$ The lower bound is obtained by evaluating the mutual information at the reference input $X_r\sim \mathrm{Beta}(1/2,1/2)$, which induces a beta-binomial output distribution, while the upper bound follows from a minimax redundancy construction. Finally, we prove an improved lower bound on the support size of the capacity-achieving input distribution. We show that the beta-binomial output induced by $X_r$ is asymptotically optimal and close to the capacity-achieving output distribution in relative entropy and $\chi^2$ divergence. We also prove a finite-mixture approximation lower bound showing that the beta-binomial output cannot be approximated too accurately by binomial mixtures with few components. Combining these results yields a support-size lower bound of order $\Omega(\sqrt{n\log\log n})$, with explicit constants. Numerical results illustrate the capacity bounds and optimal input distribution.