American Institute of Mathematical Sciences

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:

show all references

References:
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
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] Sheng Wang, Xue An, Chen Yang, Long Liu, Yongchang Yu. Design and experiment of seeding electromechanical control seeding system based on genetic algorithm fuzzy control strategy. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020210 [14] 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 [15] 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 [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] 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 [18] 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 [19] 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 [20] 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

2018 Impact Factor: 0.879