🔢 mathematics

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

This paper establishes an improved lower bound of order $\sqrt{n\log\log n}$ on the support size of the capacity-achieving input distribution for the binomial channel by deriving precise capacity asymptotics and demonstrating that the Beta-binomial output, which is asymptotically optimal, cannot be well-approximated by distributions induced by inputs with fewer mass points.

Original authors: Mohammadamin Baniasadi, Luca Barletta, Alex Dytso

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammadamin Baniasadi, Luca Barletta, Alex Dytso

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message through a very noisy, tricky pipe. This pipe is what mathematicians call a Binomial Channel. It's a bit like a game where you drop a certain number of marbles (let's say $n$ marbles) into a machine. Depending on how you set the machine (a setting called $x$ ), the marbles come out the other side in a specific pattern.

Your goal is to figure out the best possible way to set that machine to send the most information possible. This "best setting" is called the capacity-achieving input.

The Big Mystery: How Many Settings Do We Need?

For a long time, scientists knew two things about this "best setting":

It's not a smooth, continuous dial. Instead, it's like a switchboard with only a few specific buttons you can press.
The number of buttons you need to press (the support size) is somewhere between a small number and a large number.

Previously, the best guess for the minimum number of buttons needed was roughly the square root of the total marbles ( $\sqrt{n}$ ). If you had 10,000 marbles, you needed at least 100 buttons. If you had 1 million, you needed 1,000.

This paper says: "We can do better."

The authors prove that you actually need more buttons than just the square root. You need roughly $\sqrt{n} \times \log(\log(n))$ .

The Analogy: Imagine you are trying to paint a perfect picture using a limited number of distinct colors.
- The old rule said: "You need at least as many colors as the square root of the canvas size."
- The new rule says: "Actually, you need that many colors plus a little extra 'fuzziness' factor that grows very slowly."
- While that extra factor ( $\log \log n$ ) sounds small, in the world of math, it's a significant upgrade. It proves the picture is more complex than we thought.

How Did They Solve It? (The Three-Step Recipe)

The authors didn't just guess; they built a mathematical bridge using three main steps:

1. Measuring the "Perfect" Signal
First, they needed to know exactly how much information the channel could carry. They calculated a very precise "speed limit" for this channel.

The Metaphor: Think of this as measuring the exact width of a highway. Before, we had a wide range: "It's between 50 and 100 miles wide." This paper narrowed it down to: "It's exactly 75 miles wide, give or take a tiny fraction that disappears as the road gets longer."
Why it matters: Knowing the exact speed limit allowed them to see how close a "good" guess was to the "perfect" solution.

2. The "Golden Standard" Reference
They picked a specific, well-known way of setting the machine (using a Beta distribution, which sounds fancy but is just a specific, smooth curve of probabilities). They called this the "Reference Input."

The Metaphor: Imagine you are trying to find the perfect recipe for a cake. You have a "Gold Standard" recipe that is almost perfect. The authors proved that the actual best recipe (the one that wins the competition) is incredibly similar to this Gold Standard. In fact, if you compare the two cakes, they taste almost identical.
The Catch: Even though they taste the same, the ingredients list (the number of distinct points) for the Gold Standard is infinite (a smooth curve), while the real winner must use a finite list of ingredients.

3. The "Approximation" Trap
This is the cleverest part. The authors asked: "How many ingredients (buttons) do you need to fake the Gold Standard recipe?"

The Metaphor: Imagine the Gold Standard is a high-resolution photo. You are trying to recreate it using a low-resolution printer that can only use a limited number of dots (mass points).
The authors proved a mathematical law: You cannot fake the Gold Standard well unless you use a LOT of dots. If you try to use too few, the picture looks blurry (mathematically, the error is too high).
Because the "Real Winner" must be very close to the "Gold Standard" (from Step 2), and the "Gold Standard" is hard to fake with few dots (from Step 3), the "Real Winner" is forced to have a lot of dots.

The Result

By combining these steps, the authors forced the math to admit that the number of buttons (the support size) must be larger than previously thought.

Old Bound: $\sqrt{n}$
New Bound: $\sqrt{n} \times \log(\log(n))$

What Does This Mean?

The paper doesn't claim this will immediately fix your Wi-Fi or improve your phone's battery. It is a pure mathematics paper about the fundamental structure of information.

It tells us that the "best" way to send data through this specific type of channel is more complex than we realized. The "optimal" strategy isn't just a simple set of switches; it requires a surprisingly large and intricate set of options to reach the absolute maximum efficiency.

In short: The universe of information is a bit more crowded and complex than we thought, and this paper put a new, higher floor on how many "buttons" we need to press to unlock it.

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

Problem Statement
This work investigates the structural properties of the capacity-achieving input distribution for the binomial channel, defined by the transition probability $P_{Y|X}(y|x) = \binom{n}{y} x^y (1-x)^{n-y}$ for $x \in [0, 1]$ and $y \in \{0, \dots, n\}$ . While it is established that the capacity-achieving input distribution $P_{X^*}$ is discrete and supported on a finite number of points, the precise growth rate of this support size as the number of trials $n$ increases remains a subject of study. Previous results by [10] established that the support size is lower-bounded by a term of order $\sqrt{n}$ and upper-bounded by a term of order $n/2$ . However, the gap between the known capacity bounds in [10] did not vanish as $n \to \infty$ , limiting the ability to derive sharper cardinality lower bounds.

Methodology
The authors employ a three-step analytical framework to derive a tighter lower bound on the support size:

Tight Capacity Bounds: The authors first derive new explicit upper and lower bounds on the channel capacity $C(n)$ . The lower bound is obtained by evaluating the mutual information at a reference input $X_r \sim \text{Beta}(1/2, 1/2)$ , while the upper bound utilizes the Xie–Barron minimax redundancy construction [8]. Crucially, these bounds are shown to have a gap that vanishes as $n \to \infty$ , yielding the asymptotic expansion $C(n) = \frac{1}{2} \log \frac{n\pi}{2e} + o(1)$ .
Optimality of the Reference Output: Using the vanishing capacity gap, the authors demonstrate that the output distribution induced by the reference input, $P_{Y_r}$ (a Beta-binomial distribution), is asymptotically optimal. Specifically, they prove that the relative entropy $D(P_{Y_r} \| P_{Y^*})$ and the $\chi^2$ divergence $\chi^2(P_{Y^*} \| P_{Y_r})$ between the reference output and the true capacity-achieving output $P_{Y^*}$ vanish at a rate proportional to the capacity gap.
Finite Mixture Approximation Lower Bound: The core of the argument relies on a quantitative lower bound for approximating the reference Beta-binomial output using a finite mixture of binomial distributions. Inspired by techniques used for the additive Gaussian channel [11] and best-approximation theory [12], the authors adapt the trigonometric moment method. They utilize orthogonal polynomials (shifted Chebyshev polynomials) associated with the Beta(1/2, 1/2) distribution to construct a moment matrix. By applying the Eckart-Young-Mirsky theorem to this matrix, they derive a lower bound on the $\chi^2$ divergence between an arbitrary $K$ -point input output and the reference output.

Key Contributions and Results
The primary contribution of this paper is an improved lower bound on the cardinality of the support of the capacity-achieving input distribution $P_{X^*}$ .

Improved Lower Bound: The authors prove that the support size $|\text{supp}(P_{X^*})|$ is lower-bounded by a term of order $\sqrt{n} \log \log n$ . Specifically, for sufficiently large $n$ :
$|\text{supp}(P_{X^*})| \geq \Omega\left(\sqrt{n} \log \log n\right)$
This improves upon the previous $\Omega(\sqrt{n})$ bound established in [10].
Capacity Characterization: The paper provides explicit upper and lower bounds on $C(n)$ with a vanishing gap, confirming the asymptotic behavior $C(n) = \frac{1}{2} \log \frac{n\pi}{2e} + o(1)$ .
Approximation Theory: The work establishes a specific lower bound on the $\chi^2$ divergence between a Beta-binomial distribution and any binomial mixture with $K$ components, showing that such an approximation cannot be arbitrarily close unless $K$ is sufficiently large.

Significance
The paper claims that the vanishing gap in the capacity estimates is the essential ingredient that allows the connection between the capacity value and the support size. By showing that the capacity-achieving output must be close to the Beta-binomial reference output in $\chi^2$ divergence, and by proving that this reference output cannot be well-approximated by a sparse mixture, the authors force the conclusion that the capacity-achieving input must possess a significantly larger support than previously proven.

The authors note that while the improvement from $\sqrt{n}$ to $\sqrt{n} \log \log n$ is asymptotic and the explicit constants are not optimized, the result narrows the gap between the known lower bound and the upper bound of order $n/2$ . The paper concludes by identifying open questions, including determining the exact asymptotic growth of the support size and refining the explicit constants and non-asymptotic estimates.

The Big Mystery: How Many Settings Do We Need?

How Did They Solve It? (The Three-Step Recipe)

The Result

What Does This Mean?

More like this