An Improved Lower Bound on Support Size of Capacity-Achieving Inputs for the Binomial Channel: Extended version
Abstract
We study the binomial channel and the structure of its capacity-achieving input and output distributions. It is known that the capacity-achieving input distribution is discrete and supported on finitely many points. The best previously known bounds show that the support size of the capacity-achieving distribution is lower-bounded by a term of order √n and upper-bounded by a term of order n/2, where n is the number of trials. In this work, we derive a new lower bound on the support size of order √(nloglog n), up to explicit constants. The proof consists of three main steps. First, we derive new upper and lower bounds on the capacity with a gap that vanishes as n→∞, which yields C(n)=1/2lognπ/2e+o(1). Second, we show that the Beta-binomial output distribution induced by the reference input Xr∼Beta(1/2,1/2) is asymptotically optimal: it approaches the capacity-achieving output distribution in relative entropy and, after a comparison step, in χ2 divergence. Third, we prove a quantitative χ2 approximation lower bound showing that this Beta-binomial output cannot be approximated too well by the output induced by a K-point input. Combining these ingredients forces the capacity-achieving input distribution to have at least order √(nloglog n) mass points.
Related
- On the Evolution of the Capacity-Achieving Input Support for the Amplitude-Constrained AWGN Channel
- Extended One-Liners for the Gamma, Poisson, and Binomial Distributions
- Extended Tropical Characteristic Fibers and Slopes of Binomial D-Modules
- The binomial distribution maximises entropy among sums of negatively related indicators with fixed mean and support
- Efficient capacity-achieving entanglement generation with application to pure-loss Bosonic channels
BibTeX
@misc{baniasadi2026improved,
title = {{An Improved Lower Bound on Support Size of Capacity-Achieving Inputs for the Binomial Channel: Extended version}},
author = {Mohammadamin Baniasadi and Antonino Favano and Luca Barletta and Alex Dytso},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.12472},
eprint = {2605.12472},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.12472},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An Improved Lower Bound on Support Size of Capacity-Achieving Inputs for the Binomial Channel: Extended version
AU - Mohammadamin Baniasadi
AU - Antonino Favano
AU - Luca Barletta
AU - Alex Dytso
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2605.12472
UR - https://arxiv.org/abs/2605.12472
AB - We study the binomial channel and the structure of its capacity-achieving input and output distributions. It is known that the capacity-achieving input distribution is discrete and supported on finitely many points. The best previously known bounds show that the support size of the capacity-achieving distribution is lower-bounded by a term of order √n and upper-bounded by a term of order n/2, where n is the number of trials. In this work, we derive a new lower bound on the support size of order √(nloglog n), up to explicit constants. The proof consists of three main steps. First, we derive new upper and lower bounds on the capacity with a gap that vanishes as n→∞, which yields C(n)=1/2lognπ/2e+o(1). Second, we show that the Beta-binomial output distribution induced by the reference input X_r∼Beta(1/2,1/2) is asymptotically optimal: it approaches the capacity-achieving output distribution in relative entropy and, after a comparison step, in χ^2 divergence. Third, we prove a quantitative χ^2 approximation lower bound showing that this Beta-binomial output cannot be approximated too well by the output induced by a K-point input. Combining these ingredients forces the capacity-achieving input distribution to have at least order √(nloglog n) mass points.
ER -