An Improved Lower Bound on Support Size of Capacity-Achieving Inputs for the Binomial Channel: Extended version

Mohammadamin Baniasadi † , Luca Barletta ∗ , and Alex Dytso ∗∗ · 2026

Read An Improved Lower Bound on Support Size of Capacity-Achieving Inputs for the Binomial Channel: Extended version by Mohammadamin Baniasadi † , Luca Barletta ∗ , and Alex Dytso ∗∗ (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-12472.txt.

Introduction

Baniasadi and three colleagues sharpen a lower bound for the binomial channel's capacity-achieving inputs. Those inputs are known to be discrete with finite support, previously bounded below by a term of order square root of n and above by order n over two. The new bound reaches order square root of n times log log n, with explicit constants. The proof tightens capacity bounds until the gap vanishes, shows a Beta-binomial output is asymptotically optimal, and then proves a quasi-concavity step that forces the support to grow.

Catalog record

CREATORMohammadamin Baniasadi † , Luca Barletta ∗ , and Alex Dytso ∗∗
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39834
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.12472

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Improved Lower Bound on Support Size of Capacity-Achieving Inputs for the Binomial Channel: Extended version Mohammadamin Baniasadi † , Luca Barletta ∗ , and Alex Dytso ∗∗ 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 \sqrt{n} and upper-bounded by a term of order n / 2 n/2 , where n n is the number of trials. In this work, we derive a new lower bound on the support size of order n ​ log ⁡ log ​ n \sqrt{n\log\log 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 → ∞ n\to\infty , which yields C ⁡ ( n ) = 1 2 ​ log ⁡ n ​ π 2 ​ e + o ⁡ ( 1 ) C(n)=\frac{1}{2}\log\frac{n\pi}{2e}+o(1) . Second, we show that the Beta-binomial output distribution induced by the reference input X r ∼ Beta ⁡ ( 1 / 2 , 1 / 2 ) X_{r}\sim\mathrm{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 \chi^{2} divergence. Third, we prove a quantitative χ 2 \chi^{2} approximation lower bound showing that this Beta-binomial output cannot be approximated too well by the output induced by a K K -point input. Combining these ingredients forces the capacity-achieving input distribution to have at least order n ​ log ⁡ log ​ n \sqrt{n\log\log n} mass points. † University of California, Davis, USA. Email: [email protected] ∗ Politecnico di Milano, Milan, Italy. Email: [email protected] ∗∗ Qualcomm Flarion Technologies, Bridgewater, USA. Email: [email protected] I Introduction We consider the binomial channel with input-output law P_{Y|X}(y|x)=\binom{n}{y}x^{y}(1-x)^{n-y},\quad x\in[0,1],\,y\in\{0,\ldots,n\}. (1) The channel capacity is C(n)=\max_{P_{X}:\,X\in[0,1]}I(X;Y)=I(X^{\ast};Y^{\ast}), (2) where P_{X^{\ast}} and P_{Y^{\ast}} are the capacity-achieving input and output distributions, respectively. The binomial channel naturally arises in molecular communications, and the interested reader is referred to [ 5 , 4 , 6 , 9 ] and references therein. The channel is also useful in the study of the deletion channel [ 13 , 1 ] . The capacity of the binomial channel was first considered in [ 12 ] , where the minimax redundancy theorem of [ 19 ] was used to show that the capacity scales asymptotically as \frac{1}{2}\log n . The exact capacity for the case n=1 was computed in [ 5 ] , where the binary distribution supported on \{0,1\} was shown to be capacity-achieving. However, sharp non-asymptotic bounds on the capacity remain limited. The structure of the capacity-achieving input distribution has also been studied. For example, the authors of [ 5 ] designed an algorithm for computing the capacity and a capacity-achieving input distribution using a dual representation of the maximization problem. It is also known, by the Witsenhausen technique [ 18 ] , that there exists a capacity-achieving distribution with at most n+1 mass points. More recently, [ 20 ] studied structural properties of capacity-achieving distributions for the binomial channel. In particular, it was shown that all capacity-achieving distributions are discrete. This discreteness was then used to establish strong concavity of the mutual information, which implies uniqueness of P_{X^{\star}} . It was also shown that the capacity-achieving distribution is symmetric around \frac{1}{2} . The same work improved the Witsenhausen upper bound of n+1 mass points to an upper bound of order \frac{n}{2} , and proved a lower bound of order \sqrt{n} . The authors also derived capacity bounds. However, the gap between these bounds does not vanish with n , which limits their use for obtaining sharper cardinality lower bounds. In this work, we improve the lower bound on the number of mass points of P_{X^{\ast}} from order \sqrt{n} to order \sqrt{n\log\log n} . We also derive new upper and lower bounds on the capacity whose gap vanishes as n\to\infty . This vanishing-gap estimate is a key ingredient in the support-size argument: it shows that the output distribution induced by a capacity-achieving input must be close to a natural Beta-binomial reference output. The techniques used in this work are inspired by a recent result on the additive Gaussian channel with a peak-power constraint [ 17 ] , where improved lower bounds were obtained on the support size of the capacity-achieving input distribution. The main idea of [ 17 ] is to combine the golden formula with lower bounds from best-approximation theory, which quantify how well a target output distribution can be approximated by finite Gaussian mixtures [ 14 ] . In the present paper, we adapt this strategy to the binomial setting by replacing Gaussian-mixture approximation with approximation by finite binomial mixtures. I-A Main Contributions and Outline The main contribution of this paper is a new lower bound on the support size of the capacity-achieving input distribution for the binomial channel. In particular, we improve the previously known lower bound of order \sqrt{n} to a lower bound of order \sqrt{n\log\log n} , up to explicit constants; see Theorem 4 . The proof is based on several ingredients, which may also be of independent interest. First, in Section II we discuss the preliminaries we need in our proofs. Then, in Section III , we derive new explicit upper and lower bounds on the capacity. The lower bound is obtained by evaluating the mutual information at the reference input X_{r}\sim\mathrm{Beta}(1/2,1/2) , while the upper bound follows from the Xie–Barron minimax redundancy construction; see Theorems 1 and 2 . These bounds imply C(n)=\frac{1}{2}\log\!\left(\frac{n\pi}{2e}\right)+o(1), (3) and, more importantly for our purposes, the gap between the lower and upper bounds vanishes as n\to\infty ; see Proposition 1 . Second, we show that the output distribution P_{Y_{r}} induced by the reference input P_{X_{r}} is close to the capacity-achieving output distribution. More precisely, in Section III , we prove that the relative entropy {\mathsf{D}}\left(\left.P_{Y_{r}}\,\right\|P_{Y^{\ast}}\right) vanishes at the same rate as the capacity gap, and then convert this estimate into a \chi^{2} bound; see Theorem 3 and Proposition 2 . This step is what connects the capacity estimates to the support-size question. Third, in Section IV , we use a finite-mixture approximation lower bound for binomial mixtures; see Theorem 5 . This result shows that the reference Beta-binomial output P_{Y_{r}} cannot be approximated too well, in \chi^{2} divergence, by the output induced by an input with only K mass points. Combining this approximation lower bound with the upper bound on \chi^{2}(P_{Y^{\ast}}\|P_{Y_{r}}) forces the capacity-achieving input to have sufficiently many mass points. Finally, Section V contains the proofs, and Section VI concludes with several open questions. I-B Notation All logarithms are to base e . Deterministic quantities are denoted by lower-case letters and random variables by upper-case letters. For a random variable X and every measurable subset \mathcal{A}\subseteq\mathbb{R} the probability distribution is written as P_{X}(\mathcal{A})=\mathbb{P}[X\in\mathcal{A}] . The support set of P_{X} is \mathrm{supp}(P_{X})=\{x:\text{ $P_{X}(\mathcal{D})>0$ for every open set $\mathcal{D}\ni x$}\}. (4) When X is discrete, we write P_{X}(x) for P_{X}(\{x\}) , i.e., P_{X} is a probability mass

Read the complete text