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. Google Scholar

[2]

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

[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. Google Scholar

[4]

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

[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. Google Scholar

[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. Google Scholar

[7]

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

[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. Google Scholar

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[17]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

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. Google Scholar

[2]

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

[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. Google Scholar

[4]

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

[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. Google Scholar

[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. Google Scholar

[7]

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

[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. Google Scholar

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[17]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

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]

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]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

2018 Impact Factor: 0.879

Metrics

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

Other articles
by authors

[Back to Top]