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]

Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Carolyn Mayer, Kathryn Haymaker, Christine A. Kelley. Channel decomposition for multilevel codes over multilevel and partial erasure channels. Advances in Mathematics of Communications, 2018, 12 (1) : 151-168. doi: 10.3934/amc.2018010

[16]

Marco Cabral, Ricardo Rosa, Roger Temam. Existence and dimension of the attractor for the Bénard problem on channel-like domains. Discrete & Continuous Dynamical Systems - A, 2004, 10 (1&2) : 89-116. doi: 10.3934/dcds.2004.10.89

[17]

Cheng Ma, Y. C. E. Lee, Chi Kin Chan, Yan Wei. Auction and contracting mechanisms for channel coordination with consideration of participants' risk attitudes. Journal of Industrial & Management Optimization, 2017, 13 (2) : 775-801. doi: 10.3934/jimo.2016046

[18]

Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179

[19]

Grigory Panasenko, Ruxandra Stavre. Asymptotic analysis of the Stokes flow with variable viscosity in a thin elastic channel. Networks & Heterogeneous Media, 2010, 5 (4) : 783-812. doi: 10.3934/nhm.2010.5.783

[20]

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

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (13)
  • HTML views (203)
  • Cited by (0)

Other articles
by authors

[Back to Top]