November 2017, 11(4): 813-835. doi: 10.3934/amc.2017060

Capacity of random channels with large alphabets

1. 

Automatic Control Laboratory, ETH Zurich, Switzerland

2. 

Institute for Theoretical Physics, ETH Zurich, Switzerland

Received  November 2016 Published  November 2017

Fund Project: TS and JL were supported by the ETH grant (ETH-15 12-2). DS acknowledges support by the Swiss National Science Foundation (SNSF) via the National Centre of Competence in Research QSIT and by the Air Force Office of Scientific Research (AFOSR) via grant FA9550-16-1-0245

We consider discrete memoryless channels with input alphabet size $n$ and output alphabet size $m$, where $m=\left\lceil{γ n}\right\rceil$ for some constant $γ>0$. The channel transition matrix consists of entries that, before being normalized, are independent and identically distributed nonnegative random variables $V$ and such that $\mathbb{E}{(V \log V)^2}<∞$. We prove that in the limit as $n{\to }∞$ the capacity of such a channel converges to $\text{Ent}(V) / \mathbb{E}[V]$ almost surely and in $\text{L}^{2}$, where $\text{Ent}(V):= \mathbb{E}[{V\log V}]-\mathbb{E}[{V}]\log \mathbb{E}[{V}]$ denotes the entropy of $V$. We further show that, under slightly different model assumptions, the capacity of these random channels converges to this asymptotic value exponentially in $n$. Finally, we present an application in the context of Bayesian optimal experiment design.

Citation: Tobias Sutter, David Sutter, John Lygeros. Capacity of random channels with large alphabets. Advances in Mathematics of Communications, 2017, 11 (4) : 813-835. doi: 10.3934/amc.2017060
References:
[1]

S. Arimoto, An algorithm for computing the capacity of arbitrary discrete memoryless channels, IEEE Transactions on Information Theory, 18 (1972), 14-20.

[2]

D. P. Bertsekas, Convex Optimization Theory Athena Scientific optimization and computation series, Athena Scientific, 2009.

[3]

E. BiglieriJ. Proakis and S. Shamai, Fading channels: Information-theoretic and communications aspects, IEEE Transactions on Information Theory, 44 (1998), 2619-2692. doi: 10.1109/18.720551.

[4]

R.E. Blahut, Computation of channel capacity and rate-distortion functions, IEEE Transactions on Information Theory, 18 (1972), 460-473.

[5]

S. Boucheron, G. Lugosi and P. Massart, Concentration Inequalities Oxford University Press, Oxford, 2013, URL http://dx.doi.org/10.1093/acprof:oso/9780199535255.001.0001, A nonasymptotic theory of independence.

[6]

A. G. Busetto, A. Hauser, G. Krummenacher, M. Sunnåker, S. Dimopoulos, C. S. Ong, J. Stelling and J. M. Buhmann, Near-optimal experimental design for model selection in systems biology., Bioinformatics, 29 (2013), 2625-2632, URL http://dblp.uni-trier.de/db/journals/bioinformatics/bioinformatics29.html#BusettoHKSDOSB13. doi: 10.1093/bioinformatics/btt436.

[7]

M. Chiang, Geometric programming for communication systems, Foundations and Trends in Communications and Information Theory, 2 (2005), 1-154. doi: 10.1561/0100000005.

[8]

M. Chiang and S. Boyd, Geometric programming duals of channel capacity and rate distortion, IEEE Transactions on Information Theory, 50 (2004), 245-258. doi: 10.1109/TIT.2003.822581.

[9]

T. M. Cover and J. A. Thomas, Elements of Information Theory Wiley Interscience, 2006.

[10]

L. Devroye, Nonuniform Random Variate Generation Springer-Verlag, New York, 1986, URL http://dx.doi.org/10.1007/978-1-4613-8643-8.

[11]

R. Durrett, Probability: Theory and Examples Cambridge University Press, 2010.

[12]

M.B. Hastings, Superadditivity of communication capacity using entangled inputs, Nature Physics, 5 (2009), 255-257. doi: 10.1038/nphys1224.

[13]

A. S. Holevo, Quantum Systems, Channels, Information De Gruyter Studies in Mathematical Physics 16,2012.

[14]

J. Huang and S.P. Meyn, Characterization and computation of optimal distributions for channel coding, IEEE Transactions on Information Theory, 51 (2005), 2336-2351. doi: 10.1109/TIT.2005.850108.

[15]

D.V. Lindley, On a measure of the information provided by an experiment, Ann. Math. Statist., 27 (1956), 986-1005. doi: 10.1214/aoms/1177728069.

[16]

M. Raginsky and I. Sason, Concentration of measure inequalities in information theory, communications, and coding, Foundations and Trends in Communications and Information Theory, 10 (2013), 1-246. doi: 10.1561/0100000064.

[17]

R. T. Rockafellar, Convex Analysis Princeton Landmarks in Mathematics and Physics Series, Princeton University Press, 1997.

[18]

W. Rudin, Principles of Mathematical Analysis 3rd edition, McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1976, International Series in Pure and Applied Mathematics.

[19]

C. E. Shannon, A mathematical theory of communication, Bell System Technical Journal, 27 (1948), 379-423,623-656, URL http://math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf. doi: 10.1002/j.1538-7305.1948.tb01338.x.

[20]

T. SutterD. SutterP. Mohajerin Esfahani and J. Lygeros, Efficient approximation of channel capacities, Information Theory, IEEE Transactions on, 61 (2015), 1649-1666. doi: 10.1109/TIT.2015.2401002.

[21]

A.M. Tulino and S. Verdú, Random matrix theory and wireless communications, Foundations and Trends in Communications and Information Theory, 1 (2014), 1-182. doi: 10.1561/0100000001.

show all references

References:
[1]

S. Arimoto, An algorithm for computing the capacity of arbitrary discrete memoryless channels, IEEE Transactions on Information Theory, 18 (1972), 14-20.

[2]

D. P. Bertsekas, Convex Optimization Theory Athena Scientific optimization and computation series, Athena Scientific, 2009.

[3]

E. BiglieriJ. Proakis and S. Shamai, Fading channels: Information-theoretic and communications aspects, IEEE Transactions on Information Theory, 44 (1998), 2619-2692. doi: 10.1109/18.720551.

[4]

R.E. Blahut, Computation of channel capacity and rate-distortion functions, IEEE Transactions on Information Theory, 18 (1972), 460-473.

[5]

S. Boucheron, G. Lugosi and P. Massart, Concentration Inequalities Oxford University Press, Oxford, 2013, URL http://dx.doi.org/10.1093/acprof:oso/9780199535255.001.0001, A nonasymptotic theory of independence.

[6]

A. G. Busetto, A. Hauser, G. Krummenacher, M. Sunnåker, S. Dimopoulos, C. S. Ong, J. Stelling and J. M. Buhmann, Near-optimal experimental design for model selection in systems biology., Bioinformatics, 29 (2013), 2625-2632, URL http://dblp.uni-trier.de/db/journals/bioinformatics/bioinformatics29.html#BusettoHKSDOSB13. doi: 10.1093/bioinformatics/btt436.

[7]

M. Chiang, Geometric programming for communication systems, Foundations and Trends in Communications and Information Theory, 2 (2005), 1-154. doi: 10.1561/0100000005.

[8]

M. Chiang and S. Boyd, Geometric programming duals of channel capacity and rate distortion, IEEE Transactions on Information Theory, 50 (2004), 245-258. doi: 10.1109/TIT.2003.822581.

[9]

T. M. Cover and J. A. Thomas, Elements of Information Theory Wiley Interscience, 2006.

[10]

L. Devroye, Nonuniform Random Variate Generation Springer-Verlag, New York, 1986, URL http://dx.doi.org/10.1007/978-1-4613-8643-8.

[11]

R. Durrett, Probability: Theory and Examples Cambridge University Press, 2010.

[12]

M.B. Hastings, Superadditivity of communication capacity using entangled inputs, Nature Physics, 5 (2009), 255-257. doi: 10.1038/nphys1224.

[13]

A. S. Holevo, Quantum Systems, Channels, Information De Gruyter Studies in Mathematical Physics 16,2012.

[14]

J. Huang and S.P. Meyn, Characterization and computation of optimal distributions for channel coding, IEEE Transactions on Information Theory, 51 (2005), 2336-2351. doi: 10.1109/TIT.2005.850108.

[15]

D.V. Lindley, On a measure of the information provided by an experiment, Ann. Math. Statist., 27 (1956), 986-1005. doi: 10.1214/aoms/1177728069.

[16]

M. Raginsky and I. Sason, Concentration of measure inequalities in information theory, communications, and coding, Foundations and Trends in Communications and Information Theory, 10 (2013), 1-246. doi: 10.1561/0100000064.

[17]

R. T. Rockafellar, Convex Analysis Princeton Landmarks in Mathematics and Physics Series, Princeton University Press, 1997.

[18]

W. Rudin, Principles of Mathematical Analysis 3rd edition, McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1976, International Series in Pure and Applied Mathematics.

[19]

C. E. Shannon, A mathematical theory of communication, Bell System Technical Journal, 27 (1948), 379-423,623-656, URL http://math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf. doi: 10.1002/j.1538-7305.1948.tb01338.x.

[20]

T. SutterD. SutterP. Mohajerin Esfahani and J. Lygeros, Efficient approximation of channel capacities, Information Theory, IEEE Transactions on, 61 (2015), 1649-1666. doi: 10.1109/TIT.2015.2401002.

[21]

A.M. Tulino and S. Verdú, Random matrix theory and wireless communications, Foundations and Trends in Communications and Information Theory, 1 (2014), 1-182. doi: 10.1561/0100000001.

Figure 1.  For different alphabet sizes $n$ we plot the capacity of five random channels, constructed as explained in Example 3.1. The method introduced in [20] is used to determine upper and lower bounds for the capacity for finite alphabet sizes $n$. The asymptotic capacity (for $n\to \infty$) is depicted by the dashed line
Figure 2.  For different alphabet sizes $n$, we plot in (a) the empirical mean of the maximum expected information gain (blue line) $\tfrac{1}{N} \sum_{i=1}^N \sup_{\lambda\in\Lambda} I(p, \mathsf{W}_i^{(\lambda, V, n)})$, where $(\mathsf{W}_i^{(\lambda, V, n)})_{i=1}^N$ are independent channels and $N=1000$. The red line represents the empirical mean of the suboptimal expected information gain, that is given by $\tfrac{1}{N} \sum_{i=1}^N I(p, \mathsf{W}_i^{(\hat{\lambda}, V, n)})$, where $\hat{\lambda}$ are the optimal parameters for the asymptotic capacity, derived in Proposition 4.3. (b) depicts the empirical variance of the maximum expected information gain (blue line) as well as the empirical variance of the suboptimal expected information gain (red line)
[1]

Lizhong Peng, Shujun Dang, Bojin Zhuang. Localization operator and digital communication capacity of channel. Communications on Pure & Applied Analysis, 2007, 6 (3) : 819-827. doi: 10.3934/cpaa.2007.6.819

[2]

Jae Man Park, Gang Uk Hwang, Boo Geum Jung. Design and analysis of an adaptive guard channel based CAC scheme in a 3G-WLAN integrated network. Journal of Industrial & Management Optimization, 2010, 6 (3) : 621-639. doi: 10.3934/jimo.2010.6.621

[3]

Didier Georges. Infinite-dimensional nonlinear predictive control design for open-channel hydraulic systems. Networks & Heterogeneous Media, 2009, 4 (2) : 267-285. doi: 10.3934/nhm.2009.4.267

[4]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881

[5]

Hayden Schaeffer, John Garnett, Luminita A. Vese. A texture model based on a concentration of measure. Inverse Problems & Imaging, 2013, 7 (3) : 927-946. doi: 10.3934/ipi.2013.7.927

[6]

Dandan Hu, Zhi-Wei Liu. Location and capacity design of congested intermediate facilities in networks. Journal of Industrial & Management Optimization, 2016, 12 (2) : 449-470. doi: 10.3934/jimo.2016.12.449

[7]

Julie Lee, J. C. Song. Spatial decay bounds in a linearized magnetohydrodynamic channel flow. Communications on Pure & Applied Analysis, 2013, 12 (3) : 1349-1361. doi: 10.3934/cpaa.2013.12.1349

[8]

Xavier Litrico, Vincent Fromion. Modal decomposition of linearized open channel flow. Networks & Heterogeneous Media, 2009, 4 (2) : 325-357. doi: 10.3934/nhm.2009.4.325

[9]

M. Petcu. Euler equation in a channel in space dimension 2 and 3. Discrete & Continuous Dynamical Systems - A, 2005, 13 (3) : 755-778. doi: 10.3934/dcds.2005.13.755

[10]

Sara D. Cardell, Joan-Josep Climent. An approach to the performance of SPC product codes on the erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 11-28. doi: 10.3934/amc.2016.10.11

[11]

Jae Deok Kim, Ganguk Hwang. Cross-layer modeling and optimization of multi-channel cognitive radio networks under imperfect channel sensing. Journal of Industrial & Management Optimization, 2015, 11 (3) : 807-828. doi: 10.3934/jimo.2015.11.807

[12]

Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003

[13]

Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697

[14]

Peter Hinow, Ami Radunskaya. Ergodicity and loss of capacity for a random family of concave maps. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2193-2210. doi: 10.3934/dcdsb.2016043

[15]

Anulekha Dhara, Aparna Mehra. Conjugate duality for generalized convex optimization problems. Journal of Industrial & Management Optimization, 2007, 3 (3) : 415-427. doi: 10.3934/jimo.2007.3.415

[16]

Gang Li, Lipu Zhang, Zhe Liu. The stable duality of DC programs for composite convex functions. Journal of Industrial & Management Optimization, 2017, 13 (1) : 63-79. doi: 10.3934/jimo.2016004

[17]

Makram Hamouda, Chang-Yeol Jung, Roger Temam. Asymptotic analysis for the 3D primitive equations in a channel. Discrete & Continuous Dynamical Systems - S, 2013, 6 (2) : 401-422. doi: 10.3934/dcdss.2013.6.401

[18]

Haruki Katayama, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Effect of spectrum sensing overhead on performance for cognitive radio networks with channel bonding. Journal of Industrial & Management Optimization, 2014, 10 (1) : 21-40. doi: 10.3934/jimo.2014.10.21

[19]

Claude Carlet, Sylvain Guilley. Complementary dual codes for counter-measures to side-channel attacks. Advances in Mathematics of Communications, 2016, 10 (1) : 131-150. doi: 10.3934/amc.2016.10.131

[20]

Weinan E, Jianchun Wang. A thermodynamic study of the two-dimensional pressure-driven channel flow. Discrete & Continuous Dynamical Systems - A, 2016, 36 (8) : 4349-4366. doi: 10.3934/dcds.2016.36.4349

2017 Impact Factor: 0.564

Article outline

Figures and Tables

[Back to Top]