Multivariate Analytic Combinatorics for Cost Constrained Channels
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916843243962368 |
|---|---|
| author | Lenz, Andreas Melczer, Stephen Rashtchian, Cyrus Siegel, Paul H. |
| author_facet | Lenz, Andreas Melczer, Stephen Rashtchian, Cyrus Siegel, Paul H. |
| contents | Analytic combinatorics in several variables is a branch of mathematics that deals with deriving the asymptotic behavior of combinatorial quantities by analyzing multivariate generating functions. We study information-theoretic questions about sequences in a discrete noiseless channel under cost constraints. Our main contributions involve the relationship between the graph structure of the channel and the singularities of the bivariate generating function whose coefficients are the number of sequences satisfying the constraints. We use these new results to invoke theorems from multivariate analytic combinatorics to obtain the asymptotic behavior of the number of cost-limited strings that are admissible by the channel. This builds a new bridge between analytic combinatorics in several variables and labeled weighted graphs, bringing a new perspective and a set of powerful results to the literature of cost-constrained channels. Along the way, we show that the cost-constrained channel capacity is determined by a cost-dependent singularity of the bivariate generating function, generalizing Shannon's classical result for unconstrained capacity, and provide a new proof of the equivalence of the combinatorial and probabilistic definitions of the cost-constrained capacity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_06105 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Multivariate Analytic Combinatorics for Cost Constrained Channels Lenz, Andreas Melczer, Stephen Rashtchian, Cyrus Siegel, Paul H. Information Theory Computational Complexity Discrete Mathematics Combinatorics E.4 Analytic combinatorics in several variables is a branch of mathematics that deals with deriving the asymptotic behavior of combinatorial quantities by analyzing multivariate generating functions. We study information-theoretic questions about sequences in a discrete noiseless channel under cost constraints. Our main contributions involve the relationship between the graph structure of the channel and the singularities of the bivariate generating function whose coefficients are the number of sequences satisfying the constraints. We use these new results to invoke theorems from multivariate analytic combinatorics to obtain the asymptotic behavior of the number of cost-limited strings that are admissible by the channel. This builds a new bridge between analytic combinatorics in several variables and labeled weighted graphs, bringing a new perspective and a set of powerful results to the literature of cost-constrained channels. Along the way, we show that the cost-constrained channel capacity is determined by a cost-dependent singularity of the bivariate generating function, generalizing Shannon's classical result for unconstrained capacity, and provide a new proof of the equivalence of the combinatorial and probabilistic definitions of the cost-constrained capacity. |
| title | Multivariate Analytic Combinatorics for Cost Constrained Channels |
| topic | Information Theory Computational Complexity Discrete Mathematics Combinatorics E.4 |
| url | https://arxiv.org/abs/2111.06105 |