Binomial Channel: Capacity-Achieving Distribution and Bounds on Capacity

Jul 16, 2026

Upload by Jiven

Binomial noise channel capacity is analyzed as a function of the number of trials n, with input X restricted to [0,1] and output Y taking values {0,...,n}. The work proves uniqueness of the capacity-achieving input distribution by leveraging total positivity of the binomial kernel, and establishes bounds on the support size: an improved upper bound of order n^2 (improving prior order n results) and a lower bound of order √n, along with statements about the support locations and probability values. Capacity bounds are also derived, showing capacity scales on the order of (1/2)log(n).

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages15

Reading Time38 min

Introduction

Literature Review

Outline and Contributions

Notation

Main Results: Capacity-Achieving Distributions

Symmetry of Capacity-Achieving Distributions

Discreteness and Mutual Information Properties

Support Point Locations and Probabilities

Support Cardinality Bounds

Main Results: Capacity Bounds

Binomial Channel: On the Capacity-Achieving Distribution and Bounds on the Capacity Ian Zieder􀀃 , Antonino Favano†, Luca Barletta†, and Alex Dytso􀀃􀀃 􀀃 New Jersey Institute of Technology, Newark, NJ 07102, USA. Email: [ihz3@njit.edu](ihz3@njit.edu)[ ](ihz3@njit.edu)† Politecnico di Milano, Milano, 20133, Italy. Email: {antonino.favano, [luca.barletta](luca.barletta}@polimi.it)[}](luca.barletta}@polimi.it)[@polimi.it](luca.barletta}@polimi.it)[ ](luca.barletta}@polimi.it)􀀃􀀃 Qualcomm Flarion Technologies, Bridgewater, NJ 08807, USA. Email: [odytso2@gmail.com](odytso2@gmail.com) arXiv :2401 . 128 18v 1 [ cs .IT] 23 Jan 2024 Abstract—This work considers a binomial noise channel. The paper can be roughly divided into two parts. The 􀀂rst part is concerned with the properties of the capacity-achieving distribution. In particular, for the binomial channel, it is not known if the capacity-achieving distribution is unique since the output space is 􀀂nite (i.e., supported on integers 0, . . . , n) and the input space is in􀀂nite (i.e., supported on the interval [0, 1]), and there are multiple distributions that induce the same output distribution. This paper shows that the capacity-achieving distribution is unique by appealing to the total positivity property of the binomial kernel. In addition, we provide upper and lower bounds on the cardinality of the support of the capacity-achieving distribution. Speci􀀂cally, an upper bound of order n2 is shown, which improves on the previous upper bound of order n due to Witsenhausen. Moreover, a lower bound of order √n is shown. Finally, additional information about the locations and probability values of the support points is established. The second part of the paper focuses on deriving upper and lower bounds on capacity. In particular, 􀀂rm bounds are established for all n that show that the capacity scales as 12 log(n). I. INTRODUCTION We consider a channel for which the relationship between the input X ∈ [0 , 1] and the output Y ∈ {0,..., n} is described by the binomial distribution: PY |X (y|x) = 􀀒 ny􀀓 xy (1 − x)n−y . (1) In this work, we are interested in studying the capacity of this channel as a function of the number of trials n, that is C (n) = max I (X;Y ) . (2) PX : X∈[0 , 1] In addition to studying capacity, we are also interested in studying properties of an optimal capacity-achieving distribution distribution denoted by PX ⋆ . A. Literature Review The binomial channel naturally arises in molecular communications and the interested reader is referred to [1]–[4] and references therein. The channel is also useful in the study of the deletion channel [5], [6] . The capacity of the binomial channel was 􀀂rst considered in [7] where the authors used minimax redundancy theorem in [8] to argue that asymptotically the capacity scales as ~~1~~2 log n. The exact capacity for the n = 1 case was computed in [1] where binary distribution with support on {0 , 1} was shown to be capacity-achieving. To the best of our knowledge, there are no 􀀂rm bounds on the capacity of the binomial channel. Properties of the capacity-achieving distribution have also been looked at. For example, the authors of [1] have designed an algorithm for computing capacity and a capacityachieving distribution by using a dual representation of the maximization problem. It is also known that, by using the Witsenhausen technique [9], there exists a capacity-achieving distribution with at most n+1 mass points. We note, however, that the Witsenhausen technique does not guarantee that the optimal input distribution is unique. In fact, for the binomial channel, uniqueness has not been shown; note that uniqueness is important not just for theoretical purposes, but also for algorithmic purposes. A conventional way to show that the capacity-achieving distribution is unique is by establishing that the mutual information is a strictly concave function of the input distribution. However, as will be shown by a

FAQs

What channel model does the paper study?

The paper studies a binomial noise channel where the conditional distribution is P_{Y|X}(y|x)=C(n,y)x^y(1-x)^{n-y} with input X∈[0,1] and output Y∈{0,...,n}.

How does the paper prove the capacity-achieving distribution is unique?

It establishes uniqueness by using the total positivity property of the binomial kernel, instead of relying on strict concavity of mutual information.

What are the established bounds on the capacity as n grows?

Upper and lower capacity bounds are derived for all n, showing that capacity scales on the order of (1/2)log(n).

Jul 16, 2026

Upload by Jiven